Publications Mathématiques de Besançon

Algèbre et Théorie des Nombres
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.

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.

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

Received:
Published online:
DOI: 10.5802/pmb.o-7
Classification: 05C50, 15A18
Keywords: Labeled graphs, Graph spectrum, Dissimilarity, Bridge effect. 
@article{PMB_2016____85_0,
     author = {Nicolas Wicker and Canh Hao Nguyen and Hiroshi Mamitsuka},
     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 = {https://pmb.centre-mersenne.org/articles/10.5802/pmb.o-7/}
}
TY  - JOUR
AU  - Nicolas Wicker
AU  - Canh Hao Nguyen
AU  - Hiroshi Mamitsuka
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  - https://pmb.centre-mersenne.org/articles/10.5802/pmb.o-7/
UR  - https://zbmath.org/?q=an%3A1408.05085
UR  - https://doi.org/10.5802/pmb.o-7
DO  - 10.5802/pmb.o-7
LA  - en
ID  - PMB_2016____85_0
ER  - 
%0 Journal Article
%A Nicolas Wicker
%A Canh Hao Nguyen
%A Hiroshi Mamitsuka
%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 https://doi.org/10.5802/pmb.o-7
%R 10.5802/pmb.o-7
%G en
%F PMB_2016____85_0
Nicolas Wicker; Canh Hao Nguyen; Hiroshi Mamitsuka. 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. https://pmb.centre-mersenne.org/articles/10.5802/pmb.o-7/

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

[2] A. Ghosh; S. Boyd; A. Saberi 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] H. Kashima; K Tsuda; A. Inokuchi Marginalized Kernels Between Labeled Graphs, ICML (2003), pp. 321-328

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

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

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

[7] A. Sanfeliu; K. S. Fu 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] R. Sharan; T. Ideker Modeling cellular machinery through biological network comparison, Nature Biotechnology, Volume 24 (2006) no. 4, pp. 427-433 | DOI

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

Cited by Sources: