A new method of measuring similarity for a special class of directed graphs

Rok, strany: 2007, 39 - 59

The problem of graph similarity is challenging and important in many areas of science, e.g., mathematics [Sobik, F.: {it Graphmetriken und Klassifikation strukturierter Objekte}, ZKI-Informationen, Akad. Wiss. DDR, {f 2}, (1982), 63--122]; [Zelinka, B.: {it On a certain distance between isomorphism classes of graphs}, v{C}as. Pv est. Mat., {f 100}, (1975), 371--373], biology [Koch, I., Lengauer, T.; Wanke, E.: {it An algorithm for finding maximal common subtopologies in a set of protein structures}, J. Comput. Biology, {f 3}, (1996), 289--306], and chemistry [Skvortsova, M. I., Baskin, I. I., Stankevich, I. V., Palyulin, V. A., Zerirow, N. S.: {it Molecular similarity in structure-property relationship studies. Analytical description of the complete set of graph similarity measures}, International Symposium CACR,'96, (1996) pp. 542--646]. In this paper, we design a new method, which uses sequence alignment techniques [Altschul, S. F., Gish, W., Miller, V., Myers, E. W., Lipman, D. J.: {it Basic local alignment search tool}, J. Molecular Biology {f 125}, (1991), 403--410]; [Altschul, S. F., Madden, T. L., Miller, W., Schaffer,~A.~A., Zhang, J., Zhang, Z., Lipman, D. J.: {it Gapped BLAST and PSI--BLAST: a new generation of protein database search programs}, Nucleic Acids Res. {f 25}, (1997), 3389--3402], [Kilian, J., Hoos, H. H.: {it MusicBLAST--gapped sequence alignment for MIR}, in: Proceedings of the 5th International Conference on Music Information Retrieval (ISMIR), (2004)], to measure the structural similarity of unlabeled, hierarchical, and directed graphs. More precisely, if $h$ denotes the maximal length of a path from the root to a leaf of a given hierarchical and directed graph $hat{Cal H}$, we align out-degree and in-degree sequences induced by the vertex sequences on a level $i$, $0 leqslant ileqslant h$. On the basis of the level alignments, we construct measured values and prove that they are similarity measures. In our algorithm, which uses the well-known technique of dynamic programming, the alignments of out-degree and in-degree sequences are decoupled. Therefore, we obtain a family $(d_i(hat{Cal{H}}_{1}, hat{Cal{H}}_{2}))_{1leqslant i leqslant 3}$ of graph similarity measures. As an application, we examine the measures on a graph corpus of 464 graphs, where the graphs represent web-based hypertext structures (websites).

ISO 690:

Dehmer, M., Mehler, A. 2007. A new method of measuring similarity for a special class of directed graphs. In Tatra Mountains Mathematical Publications, vol. 36, no.2, pp. 39-59. 1210-3195.

APA:

Dehmer, M., Mehler, A. (2007). A new method of measuring similarity for a special class of directed graphs. Tatra Mountains Mathematical Publications, 36(2), 39-59. 1210-3195.