Publications Mathématiques de Besançon
Algèbre et Théorie des Nombres
With version française
Table of contents for this volume | Previous article | Next article
Nicolas Wicker; Canh Hao Nguyen; Hiroshi Mamitsuka
Some properties of a dissimilarity measure for labeled graphs
Publications mathématiques de Besançon (2016), p. 85-94
Article PDF
Class. Math.: 05C50, 15A18
Keywords: Labeled graphs, Graph spectrum, Dissimilarity, Bridge effect.


We investigate the problem of comparing different graphs on the same set of vertices. It is a problem arising when using different biological networks to elucidate cellular processes. We wish to see their similarity and difference via connectivity-aware graph dissimilarity for graphs with the same node set. We extend a previous result and present some results concerning the orders of magnitude of the dissimilarity as the graphs’ sizes grow to infinity. We find that removing an edge playing a very important role in graph connectivity, such as a bridge between two fully connected subgraphs, can have a dramatic effect on the dissimilarity compared to the removal of any “ordinary” edge.


[1] F.R.K. Chung, Spectral Graph Theory, American Mathematical Society, 1997  MR 1421568 |  Zbl 0867.05046
[2] A. Ghosh, S. Boyd & A. Saberi, Minimizing effective resistance of a graph, in Proceedings of the 17th International Symposium on Mathematical Theory of Networks and Systems, Kyoto, Japan, 2006, p. 1185-1196
[3] H. Kashima, K Tsuda & A. Inokuchi, Marginalized Kernels Between Labeled Graphs, in ICML, 2003, p. 321-328
[4] M. Koyuturk, A. Grama & W. Szpankowski, An efficient algorithm for detecting frequent subgraphs in biological networks., in ISMB/ECCB (Supplement of Bioinformatics), 2004, p. 200-207
[5] C. H. Nguyen, N. Wicker & H. Mamitsuka, “Selecting Graph Cut Solutions via Global Graph Similarity”, IEEE Transactions on Neural Networks and Learning Systems 25 (2014), p. 1407-1412
[6] N. Pržulj, “Biological Network Comparison Using Graphlet Degree Distribution”, Bioinformatics 26 (2010) no. 6, p. 853-854 Article
[7] A. Sanfeliu & K. S. Fu, “A distance measure between attributed relational graphs for pattern recognition”, IEEE Transactions on Systems, Man and Cybernetics 13 (1983), p. 353-362  Zbl 0511.68060
[8] R. Sharan & T. Ideker, “Modeling cellular machinery through biological network comparison”, Nature Biotechnology 24 (2006) no. 4, p. 427-433 Article
[9] N. Wicker, C. H. Nguyen & H. Mamitsuka, “A new dissimilarity measure for labeled graphs”, Linear Algebra and its Applications 483 (2013), p. 2331-2338  MR 3005294 |  Zbl 1258.05076