Measuring similarity of graph nodes by neighbor matching

Article type: Research Article

Authors: Nikolić, Mladen^{; 1}

Affiliations: Faculty of Mathematics, University of Belgrade, Studentski Trg 16, Belgrade 11000, Serbia. Tel.: +381 648 650 064; E-mail: nikolic@matf.bg.ac.rs

Note: [1] This work was partially supported by Serbian Ministry of Science grant 174021 and by SNF grant SCOPES IZ73Z0_ 127979/1.

Abstract: The problem of measuring similarity of graph nodes is important in a range of practical problems. There is a number of proposed measures, usually based on iterative calculation of similarity and the principle that two nodes are as similar as their neighbors are. In our work, we propose one novel method of that sort, with a refined concept of similarity of nodes that involves matching their neighbors. We prove convergence of the proposed method and show that it has some additional desirable properties that, to our knowledge, the existing methods lack. In addition, we construct a measure of similarity of whole graphs based on the similarities of nodes. We illustrate the proposed method on several specific problems and empirically compare it to other methods.

Keywords: Graph node similarity, graph similarity, similarity measure

DOI: 10.3233/IDA-2012-00556

Journal: Intelligent Data Analysis, vol. 16, no. 6, pp. 865-878, 2012