Measuring the Structural Similarity of Web-based Documents: A Novel Approach
Most known methods for measuring the structural similarity of document structures are based on, e.g., tag measures, path metrics and tree measures in terms of their DOM-Trees. Other methods measures the similarity in the framework of the well known vector space model. In contrast to these we present a new approach to measuring the structural similarity of web-based documents represented by so called generalized trees which are more general than DOM-Trees which represent only directed rooted trees.We will design a new similarity measure for graphs representing web-based hypertext structures. Our similarity measure is mainly based on a novel representation of a graph as strings of linear integers, whose components represent structural properties of the graph. The similarity of two graphs is then defined as the optimal alignment of the underlying property strings. In this paper we apply the well known technique of sequence alignments to solve a novel and challenging problem: Measuring the structural similarity of generalized trees. More precisely, we first transform our graphs considered as high dimensional objects in linear structures. Then we derive similarity values from the alignments of the property strings in order to measure the structural similarity of generalized trees. Hence, we transform a graph similarity problem to a string similarity problem. We demonstrate that our similarity measure captures important structural information by applying it to two different test sets consisting of graphs representing web-based documents.
[1] R. Bellman, Dynamic Programming. Princeton University Press, 1957
[2] R. A. Botafogo, B. Shneiderman: Structural analysis of hypertexts:
Identifying hierarchies and useful metrics, ACM Trans. Inf. Syst. 10
(2), 1992, 142-180
[3] S. Chakrabarti: Mining the Web. Discovering Knowledge from Hypertext
Data, Morgen and Kaufmann Publishers, 2003
[4] S. Chakrabarti: Integrating the document object model with hyperlinks
for enhanced topic distillation and information extraction, Proc. of the
10th International World Wide Web Conference, Hong Kong, 2001, 211-
220
[5] I. F. Cruz, S. Borisov, M. A. Marks, T. R. Webb: Measuring Structural
Similarity Among Web Documents: Preliminary Results , Lecture Notes
In Computer Science, Vol. 1375, 1998
[6] M. Dehmer, Strukturelle Analyse web-basierter Dokumente, Ph.D Thesis,
Department of Computer Science, Technische Universit¨at Darmstadt,
2005, unpublished
[7] M. Dehmer, R. Gleim, A. Mehler: Aspekte der Kategorisierung von
Webseiten, GI-Edition - Lecture Notes in Informatics (LNI) - Proceedings,
Jahrestagung der Gesellschaft f¨ur Informatik, Informatik 2004,
Ulm/Germany, 2004, 39-43
[8] R. Gleim: HyGraph - Ein Framework zur Extraktion, Repr¨asentation
und Analyse webbasierter Hypertextstrukturen, Beitr¨age zur GLDVTagung
2005, Bonn/Germany, 2005
[9] D. Gusfield: Algorithms on Strings, Trees, and Sequences: Computer
Science and Computational Biology, Cambridge University Press, 1997
[10] T. Jiang, L. Wang, K. Zhang: Alignment of trees - An alternative to tree
edit, Theoretical Computer Science, Elsevier, Vol. 143, 1995, 137-148
[11] S. Joshi, N. Agrawal, R. Krishnapuram, S. Negi,: Bag of Paths Model
for Measuring Structural Similarity in Web Documents, Proceedings of
the ACM International Conference on Knowledge Discovery and Data
Mining (SIGKDD), 2003, 577-582.
[12] Mehler A.: Textbedeutung. Zur prozeduralen Analyse und
Repr¨asentation struktureller ¨Ahnlichkeiten von Texten, Peter Lang,
Europ¨aischer Verlag der Wissenschaften, 2001
[13] A. Mehler, M. Dehmer, R. Gleim: Towards logical hypertext structure.
A graph-theoretic perspective, Proc. of I2CS-04, Guadalajara/Mexico,
Lecture Notes in Computer Science, Berlin-New York: Springer, 2004
[14] A. Mehler, R. Gleim, M. Dehmer: Towards structure-sensitive hypertext
categorization, to appear in: Proceedings of the 29-th Annual Conference
of the German Classification Society, 2005
[15] S. M. Selkow: The tree-to-tree editing problem, Information Processing
Letters, Vol. 6 (6), 1977, 184-186
[16] T. F. Smith, M. S. Waterman: Identification of common molecular
subsequences, Journal of Molecular Biology, Vol. 147 (1), 1981, 195-
197
[17] F. Sobik, Graphmetriken und Klassifikation strukturierter Objekte, ZKIInformationen,
Akad. Wiss. DDR, Vol. 2 (82), 1982, 63-122
[18] J. R. Ullman, An algorithm for subgraph isomorphism, J. ACM, Vol. 23
(1), 1976, 31-42
[19] P. H. Winne., L. Gupta, J. C. Nesbit: Exploring individual differences in
studying strategies using graph theoretic statistics, The Alberta Journal
of Educational Research, Vol. 40, 1994, 177-193
[20] A. Winter: Exchanching Graphs with GXL, http://www.gupro.
de/GXL
[21] Y. Yang, S. Slattery, R. Ghani: A study of approaches to hypertext
categorization, Journal of Intelligent Information Systems, Vol. 18 (2-3),
2002, 219-241
[22] K. Zhang, D. Shasha: Simple fast algorithms for the editing distance
between trees and related problems, SIAM Journal of Computing, Vol.
18 (6), 1989, 1245-1262
[23] B. Zelinka, On a certain distance between isomorphism classes of
graphs, ˇ Casopis pro ˇpest. Mathematiky, Vol. 100, 1975, 371-373
[1] R. Bellman, Dynamic Programming. Princeton University Press, 1957
[2] R. A. Botafogo, B. Shneiderman: Structural analysis of hypertexts:
Identifying hierarchies and useful metrics, ACM Trans. Inf. Syst. 10
(2), 1992, 142-180
[3] S. Chakrabarti: Mining the Web. Discovering Knowledge from Hypertext
Data, Morgen and Kaufmann Publishers, 2003
[4] S. Chakrabarti: Integrating the document object model with hyperlinks
for enhanced topic distillation and information extraction, Proc. of the
10th International World Wide Web Conference, Hong Kong, 2001, 211-
220
[5] I. F. Cruz, S. Borisov, M. A. Marks, T. R. Webb: Measuring Structural
Similarity Among Web Documents: Preliminary Results , Lecture Notes
In Computer Science, Vol. 1375, 1998
[6] M. Dehmer, Strukturelle Analyse web-basierter Dokumente, Ph.D Thesis,
Department of Computer Science, Technische Universit¨at Darmstadt,
2005, unpublished
[7] M. Dehmer, R. Gleim, A. Mehler: Aspekte der Kategorisierung von
Webseiten, GI-Edition - Lecture Notes in Informatics (LNI) - Proceedings,
Jahrestagung der Gesellschaft f¨ur Informatik, Informatik 2004,
Ulm/Germany, 2004, 39-43
[8] R. Gleim: HyGraph - Ein Framework zur Extraktion, Repr¨asentation
und Analyse webbasierter Hypertextstrukturen, Beitr¨age zur GLDVTagung
2005, Bonn/Germany, 2005
[9] D. Gusfield: Algorithms on Strings, Trees, and Sequences: Computer
Science and Computational Biology, Cambridge University Press, 1997
[10] T. Jiang, L. Wang, K. Zhang: Alignment of trees - An alternative to tree
edit, Theoretical Computer Science, Elsevier, Vol. 143, 1995, 137-148
[11] S. Joshi, N. Agrawal, R. Krishnapuram, S. Negi,: Bag of Paths Model
for Measuring Structural Similarity in Web Documents, Proceedings of
the ACM International Conference on Knowledge Discovery and Data
Mining (SIGKDD), 2003, 577-582.
[12] Mehler A.: Textbedeutung. Zur prozeduralen Analyse und
Repr¨asentation struktureller ¨Ahnlichkeiten von Texten, Peter Lang,
Europ¨aischer Verlag der Wissenschaften, 2001
[13] A. Mehler, M. Dehmer, R. Gleim: Towards logical hypertext structure.
A graph-theoretic perspective, Proc. of I2CS-04, Guadalajara/Mexico,
Lecture Notes in Computer Science, Berlin-New York: Springer, 2004
[14] A. Mehler, R. Gleim, M. Dehmer: Towards structure-sensitive hypertext
categorization, to appear in: Proceedings of the 29-th Annual Conference
of the German Classification Society, 2005
[15] S. M. Selkow: The tree-to-tree editing problem, Information Processing
Letters, Vol. 6 (6), 1977, 184-186
[16] T. F. Smith, M. S. Waterman: Identification of common molecular
subsequences, Journal of Molecular Biology, Vol. 147 (1), 1981, 195-
197
[17] F. Sobik, Graphmetriken und Klassifikation strukturierter Objekte, ZKIInformationen,
Akad. Wiss. DDR, Vol. 2 (82), 1982, 63-122
[18] J. R. Ullman, An algorithm for subgraph isomorphism, J. ACM, Vol. 23
(1), 1976, 31-42
[19] P. H. Winne., L. Gupta, J. C. Nesbit: Exploring individual differences in
studying strategies using graph theoretic statistics, The Alberta Journal
of Educational Research, Vol. 40, 1994, 177-193
[20] A. Winter: Exchanching Graphs with GXL, http://www.gupro.
de/GXL
[21] Y. Yang, S. Slattery, R. Ghani: A study of approaches to hypertext
categorization, Journal of Intelligent Information Systems, Vol. 18 (2-3),
2002, 219-241
[22] K. Zhang, D. Shasha: Simple fast algorithms for the editing distance
between trees and related problems, SIAM Journal of Computing, Vol.
18 (6), 1989, 1245-1262
[23] B. Zelinka, On a certain distance between isomorphism classes of
graphs, ˇ Casopis pro ˇpest. Mathematiky, Vol. 100, 1975, 371-373
@article{"International Journal of Information, Control and Computer Sciences:64915", author = "Matthias Dehmer and Frank Emmert Streib and Alexander Mehler and Jürgen Kilian", title = "Measuring the Structural Similarity of Web-based Documents: A Novel Approach", abstract = "Most known methods for measuring the structural similarity of document structures are based on, e.g., tag measures, path metrics and tree measures in terms of their DOM-Trees. Other methods measures the similarity in the framework of the well known vector space model. In contrast to these we present a new approach to measuring the structural similarity of web-based documents represented by so called generalized trees which are more general than DOM-Trees which represent only directed rooted trees.We will design a new similarity measure for graphs representing web-based hypertext structures. Our similarity measure is mainly based on a novel representation of a graph as strings of linear integers, whose components represent structural properties of the graph. The similarity of two graphs is then defined as the optimal alignment of the underlying property strings. In this paper we apply the well known technique of sequence alignments to solve a novel and challenging problem: Measuring the structural similarity of generalized trees. More precisely, we first transform our graphs considered as high dimensional objects in linear structures. Then we derive similarity values from the alignments of the property strings in order to measure the structural similarity of generalized trees. Hence, we transform a graph similarity problem to a string similarity problem. We demonstrate that our similarity measure captures important structural information by applying it to two different test sets consisting of graphs representing web-based documents.
", keywords = "Graph similarity, hierarchical and directed graphs, hypertext, generalized trees, web structure mining.", volume = "1", number = "10", pages = "3338-7", }
