Publications Mathématiques de Besançon
Algèbre et Théorie des Nombres
Avec cedram.org english version
Table des matières de ce volume | Article précédent | Article suivant
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
Mots clés: Labeled graphs, Graph spectrum, Dissimilarity, Bridge effect.

Résumé

Nous nous intéressons au problème de la comparaison de graphes sur un même ensemble de sommets. C’est un problème apparaissant dans l’étude de réseaux biologiques lorsqu’on veut comprendre le fonctionnement de processus cellulaires. L’objectif est de lier leur similarité ou différence, par une mesure consciente de la connectivité du graphe sur un même ensemble de sommets. Nous étendons un résultat antérieur et présentons de nouveaux résultats sur l’ordre de grandeur de la dissimilarité lorsque la taille des graphes tend vers l’infini. En particulier, nous montrons que la suppression d’une arête qui joue une grande importance dans la connectivité d’un graphe, comme un pont, peut avoir un effet dramatique sur la dissimilarité par rapport à la suppression d’une arête « ordinaire ».

Bibliographie

[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

UFC LMB PUFC