Some properties of a dissimilarity measure for labeled graphs
Wicker, Nicolas1 ; Nguyen, Canh Hao2 ; Mamitsuka, Hiroshi2
1 Laboratoire Painlevé, Université de Lille 1, 59655 Villeneuve d’Ascq, France, +0(33)320434226
2 Bioinformatics Center, ICR, Kyoto University, Gokasho, Uji, Kyoto, 611-0011, Japan
Publications mathématiques de Besançon. Algèbre et théorie des nombres (2016), pp. 85-94.

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

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.

Reçu le :
Publié le :
DOI : 10.5802/pmb.o-7
Classification : 05C50, 15A18
Mots clés : Labeled graphs, Graph spectrum, Dissimilarity, Bridge effect.
Wicker, Nicolas 1 ; Nguyen, Canh Hao 2 ; Mamitsuka, Hiroshi 2

1 Laboratoire Painlevé, Université de Lille 1, 59655 Villeneuve d’Ascq, France, +0(33)320434226
2 Bioinformatics Center, ICR, Kyoto University, Gokasho, Uji, Kyoto, 611-0011, Japan 
@article{PMB_2016____85_0,
     author = {Wicker, Nicolas and Nguyen, Canh Hao and Mamitsuka, Hiroshi},
     title = {Some properties of a dissimilarity measure for labeled graphs},
     journal = {Publications math\'ematiques de Besan\c{c}on. Alg\`ebre et th\'eorie des nombres},
     pages = {85--94},
     publisher = {Presses universitaires de Franche-Comt\'e},
     year = {2016},
     doi = {10.5802/pmb.o-7},
     zbl = {1408.05085},
     language = {en},
     url = {http://archive.numdam.org/articles/10.5802/pmb.o-7/}
}
TY  - JOUR
AU  - Wicker, Nicolas
AU  - Nguyen, Canh Hao
AU  - Mamitsuka, Hiroshi
TI  - Some properties of a dissimilarity measure for labeled graphs
JO  - Publications mathématiques de Besançon. Algèbre et théorie des nombres
PY  - 2016
SP  - 85
EP  - 94
PB  - Presses universitaires de Franche-Comté
UR  - http://archive.numdam.org/articles/10.5802/pmb.o-7/
DO  - 10.5802/pmb.o-7
LA  - en
ID  - PMB_2016____85_0
ER  - 
%0 Journal Article
%A Wicker, Nicolas
%A Nguyen, Canh Hao
%A Mamitsuka, Hiroshi
%T Some properties of a dissimilarity measure for labeled graphs
%J Publications mathématiques de Besançon. Algèbre et théorie des nombres
%D 2016
%P 85-94
%I Presses universitaires de Franche-Comté
%U http://archive.numdam.org/articles/10.5802/pmb.o-7/
%R 10.5802/pmb.o-7
%G en
%F PMB_2016____85_0
Wicker, Nicolas; Nguyen, Canh Hao; Mamitsuka, Hiroshi. Some properties of a dissimilarity measure for labeled graphs. Publications mathématiques de Besançon. Algèbre et théorie des nombres (2016), pp. 85-94. doi : 10.5802/pmb.o-7. http://archive.numdam.org/articles/10.5802/pmb.o-7/

[1] Chung, F.R.K. Spectral Graph Theory, American Mathematical Society, 1997

[2] Ghosh, A.; Boyd, S.; Saberi, A. Minimizing effective resistance of a graph, Proceedings of the 17th International Symposium on Mathematical Theory of Networks and Systems, Kyoto, Japan (2006), pp. 1185-1196

[3] Kashima, H.; Tsuda, K; Inokuchi, A. Marginalized Kernels Between Labeled Graphs, ICML (2003), pp. 321-328

[4] Koyuturk, M.; Grama, A.; Szpankowski, W. An efficient algorithm for detecting frequent subgraphs in biological networks., ISMB/ECCB (Supplement of Bioinformatics) (2004), pp. 200-207 | DOI

[5] Nguyen, C. H.; Wicker, N.; Mamitsuka, H. Selecting Graph Cut Solutions via Global Graph Similarity, IEEE Transactions on Neural Networks and Learning Systems, Volume 25 (2014), pp. 1407-1412 | DOI

[6] Pržulj, N. Biological Network Comparison Using Graphlet Degree Distribution, Bioinformatics, Volume 26 (2010) no. 6, pp. 853-854 | DOI

[7] Sanfeliu, A.; Fu, K. S. A distance measure between attributed relational graphs for pattern recognition, IEEE Transactions on Systems, Man and Cybernetics, Volume 13 (1983), pp. 353-362 | DOI | Zbl

[8] Sharan, R.; Ideker, T. Modeling cellular machinery through biological network comparison, Nature Biotechnology, Volume 24 (2006) no. 4, pp. 427-433 | DOI

[9] Wicker, N.; Nguyen, C. H.; Mamitsuka, H. A new dissimilarity measure for labeled graphs, Linear Algebra and its Applications, Volume 483 (2013), pp. 2331-2338 | DOI | MR | Zbl

Cité par Sources :