With cedram.org  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. 8594 Article PDF Class. Math.: 05C50, 15A18 Keywords: Labeled graphs, Graph spectrum, Dissimilarity, Bridge effect. Abstract 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 connectivityaware 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. Bibliography [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. 11851196 [3] H. Kashima, K Tsuda & A. Inokuchi, Marginalized Kernels Between Labeled Graphs, in ICML, 2003, p. 321328 [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. 200207 [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. 14071412 [6] N. Pržulj, “Biological Network Comparison Using Graphlet Degree Distribution”, Bioinformatics 26 (2010) no. 6, p. 853854 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. 353362 Zbl 0511.68060 [8] R. Sharan & T. Ideker, “Modeling cellular machinery through biological network comparison”, Nature Biotechnology 24 (2006) no. 4, p. 427433 Article [9] N. Wicker, C. H. Nguyen & H. Mamitsuka, “A new dissimilarity measure for labeled graphs”, Linear Algebra and its Applications 483 (2013), p. 23312338 MR 3005294  Zbl 1258.05076 