In: Tatra Mountains Mathematical Publications, vol. 36, no. 2

Matthias Dehmer - Alexander Mehler

## Details:

Year, pages: 2007, 39 - 59

Keywords:

digraphs, similarity measures, sequence alignments, degree
sequences

About article:

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).

How to cite:

*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.