×

Symmetry in complex networks. (English) Zbl 1168.05058

Summary: We consider the size and structure of the automorphism groups of a variety of empirical ‘real-world’ networks and find that, in contrast to classical random graph models, many real-world networks are richly symmetric. We construct a practical network automorphism group decomposition, relate automorphism group structure to network topology and discuss generic forms of symmetry and their origin in real-world networks. We also comment on how symmetry can affect network redundancy and robustness.

MSC:

05C90 Applications of graph theory
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
20B25 Finite automorphism groups of algebraic, geometric, or combinatorial structures

Software:

Pajek; GAP; BioGRID
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

References:

[1] L.A. Adamic, N. Glance, The political blogosphere and the 2004 US election: Divided they blog, in: Proceedings of the 3rd International Workshop on Link Discovery, 2005, pp. 36-43; L.A. Adamic, N. Glance, The political blogosphere and the 2004 US election: Divided they blog, in: Proceedings of the 3rd International Workshop on Link Discovery, 2005, pp. 36-43
[2] Albert, R.; Barabási, A.-L., Statistical mechanics of complex networks, Rev. Modern Phys., 74, 1, 47-97 (2002) · Zbl 1205.82086
[3] Albert, R.; Jeong, H.; Barabási, A.-L., Error and attack tolerance of complex networks, Nature, 406, 6794, 378-382 (2000)
[4] Barabási, A.-L.; Albert, R., Emergence of scaling in random networks, Science, 286, 5439, 509-512 (1999) · Zbl 1226.05223
[5] Basso, K.; Margolin, A. A.; Stolovitzky, G.; Klein, U.; Dalla-Favera, R.; Califano, A., Reverse engineering of regulatory networks in human b cells, Nat. Genet., 37, 4, 382-390 (2005)
[6] Batagelj, V.; Mrvar, A., Pajek — program for large network analysis, Connections, 21, 2, 47-57 (1998)
[7] Batagelj, V.; Mrvar, A., Some analyses of Erdös collaboration graph, Social Networks, 22, 2, 173-186 (2000)
[8] V. Batagelj, M. Zaveršnik, The collaboration network in computational geometry. http://vlado.fmf.uni-lj.si/pub/networks/data/collab/geom.htm; V. Batagelj, M. Zaveršnik, The collaboration network in computational geometry. http://vlado.fmf.uni-lj.si/pub/networks/data/collab/geom.htm
[9] Biggs, N., Algebraic Graph Theory (1974), Cambridge University Press: Cambridge University Press London · Zbl 0284.05101
[10] Boguñá, M.; Pastor-Satorras, R.; Díaz-Guilera, A.; Arenas, A., Models of social networks based on social distance attachment, Phys. Rev. E, 70, 5, 056122 (2004)
[11] Bollobás, B., (Modern Graph Theory. Modern Graph Theory, Graduate Texts in Mathematics, vol. 184 (1998), Springer-Verlag: Springer-Verlag New York) · Zbl 0902.05016
[12] Bollobás, B., (Random Graphs. Random Graphs, Cambridge Studies in Advanced Mathematics, vol. 73 (2001), Cambridge University Press: Cambridge University Press Cambridge) · Zbl 0979.05003
[13] Cameron, P. J., (Permutation Groups. Permutation Groups, London Mathematical Society Student Texts, vol. 45 (1999), Cambridge University Press: Cambridge University Press Cambridge) · Zbl 0922.20003
[14] Chung, F.; Lu, L.; Dewey, T. G.; Galas, D. J., Duplication models for biological networks, J. Comput. Biol., 10, 5, 677-687 (2003)
[15] de Nooy, W.; Mrvar, A.; Batagelj, V., Exploratory Social Network Analysis with Pajek (2005), Cambridge University Press
[16] Duch, J.; Arenas, A., Community detection in complex networks using extremal optimization, Phys. Rev. E, 72, 027104 (2005)
[17] Feng, Y. Q., Automorphism groups of Cayley graphs on symmetric groups with generating transposition sets, J. Combin. Theor. B, 96, 1, 67-72 (2006) · Zbl 1079.05037
[18] P. Foggia, C. Sansone, M. Vento, A performance comparison of five algorithms for graph isomorphism, in: Proc. of the 3rd IAPR TC-15 Workshop on Graph-based Representations in Pattern Recognition, 2001, pp. 188-199; P. Foggia, C. Sansone, M. Vento, A performance comparison of five algorithms for graph isomorphism, in: Proc. of the 3rd IAPR TC-15 Workshop on Graph-based Representations in Pattern Recognition, 2001, pp. 188-199
[19] The GAP Group, Gap-groups, algorithms, and programming, version 4.4. http://www.gap-system.org, 2006; The GAP Group, Gap-groups, algorithms, and programming, version 4.4. http://www.gap-system.org, 2006
[20] Golubitsky, M.; Stewart, I., Nonlinear dynamics of networks: The groupiod formalism, Bull. Amer. Math. Soc., 43, 3, 305-364 (2006) · Zbl 1119.37036
[21] The CAIDA Group, The CAIDA AS relationships dataset, 19/06/2006. http://www.caida.org/data/active/as-relationships; The CAIDA Group, The CAIDA AS relationships dataset, 19/06/2006. http://www.caida.org/data/active/as-relationships
[22] Guimerà, R.; Danon, L.; Díaz-Guilera, A.; Giralt, F.; Arenas, A., Self-similar community structure in a network of human interactions, Phys. Rev. E, 68, 6, 065103 (2003)
[23] Harary, F.; Palmer, E. M., The probability that a point of a tree is fixed, Math. Proc. Cambridge Philos. Soc., 85, 3, 407-415 (1979) · Zbl 0445.05056
[24] Holme, P., Detecting degree symmetries in networks, Phys. Rev. E, 74, 3, 036107 (2006)
[25] Jeong, H.; Mason, S. P.; Barabási, A.-L.; Oltvai, Z. N., Lethality and centrality in protein networks, Nature, 411, 41-42 (2001)
[26] Jeong, H.; Tombor, B.; Albert, R.; Oltvai, Z. N.; Barabási, A. L., The large-scale organization of metabolic networks, Nature, 407, 651-654 (2000)
[27] J.M. Kleinberg, Pages linking to epa.gov. http://www.cs.cornell.edu/courses/cs685/2002fa; J.M. Kleinberg, Pages linking to epa.gov. http://www.cs.cornell.edu/courses/cs685/2002fa
[28] J.M. Kleinberg, Pages matching the query ‘California’. http://www.cs.cornell.edu/courses/cs685/2002fa; J.M. Kleinberg, Pages matching the query ‘California’. http://www.cs.cornell.edu/courses/cs685/2002fa
[29] Lakshmivarahan, S.; Jwo, J. S.; Dhall, S. K., Symmetry in interconnection networks based on Cayley graphs of permutation groups: A survey, Parallel Comput., 19, 4, 361-407 (1993) · Zbl 0777.05064
[30] Lauri, J.; Scapellato, R., (Topics in Graph Automorphisms and Reconstruction. Topics in Graph Automorphisms and Reconstruction, London Mathematical Society Student Texts, vol. 54 (2003), Cambridge University Press: Cambridge University Press Cambridge) · Zbl 1038.05025
[31] McKay, B. D., Practical graph isomorphism, Congr. Numer., 30, 45-87 (1981)
[32] Milo, R.; Shen-Orr, S.; Itzkovitz, S.; Kashtan, N.; Chklovskii, D.; Alon, U., Network motifs: Simple building blocks of complex networks, Science, 298, 5594, 824-827 (2002)
[33] Newman, M. E.J., Scientific collaboration networks I: Network construction and fundamental results, Phys. Rev. E, 64, 1, 016131 (2001)
[34] Newman, M. E.J., Scientific collaboration networks. II: Shortest paths, weighted networks, and centrality, Phys. Rev. E, 64, 1, 016132 (2001)
[35] Newman, M. E.J., The structure and function of complex networks, SIAM Rev., 45, 2, 167-256 (2003) · Zbl 1029.68010
[36] K. Norlen, G. Lucas, M. Gebbie, J. Chuang, EVA: Extraction, visualization and analysis of the telecommunications and media ownership network, in: Proceedings of International Telecommunications Society 14th Biennial Conference, ITS2002, 2002; K. Norlen, G. Lucas, M. Gebbie, J. Chuang, EVA: Extraction, visualization and analysis of the telecommunications and media ownership network, in: Proceedings of International Telecommunications Society 14th Biennial Conference, ITS2002, 2002
[37] Bureau of Transportation Statistics, North american transportation atlas data. http://www.bts.gov, 1997; Bureau of Transportation Statistics, North american transportation atlas data. http://www.bts.gov, 1997
[38] Rotman, J. J., (An Introduction to the Theory of Groups. An Introduction to the Theory of Groups, Graduate Texts in Mathematics, vol. 148 (1994), Springer-Verlag: Springer-Verlag New York) · Zbl 0810.20001
[39] SIGACT, The theoretical computer science genealogy. http://sigact.acm.org/genealogy; SIGACT, The theoretical computer science genealogy. http://sigact.acm.org/genealogy
[40] Siganos, G.; Faloutsos, M.; Faloutsos, P.; Faloutsos, C., Power laws and the as-level internet topology, IEEE/ACM Trans. Netw., 11, 4, 514-524 (2003)
[41] Stark, C.; Breitkreutz, B.-J.; Reguly, T.; Boucher, L.; Breitkreutz, A.; Tyers, M., BioGRID: A general repository for interaction datasets, Nucleic Acids Res., 34, D535-D539 (2006)
[42] Stewart, I., Networking opportunity, Nature, 427, 601-604 (2004)
[43] Stewart, I.; Martin Golubitsky, M.; Pivato, M., Symmetry groupoids and patterns of synchrony in coupled cell networks, SIAM J. Appl. Dynam. Syst., 2, 4, 609-646 (2003) · Zbl 1089.34032
[44] Strogatz, S. H., Exploring complex networks, Nature, 410, 268-276 (2001) · Zbl 1370.90052
[45] Tononi, G.; Sporns, O.; Edelman, G. M., Measures of degeneracy and redundancy in biological networks, Proc. Natl. Acad. Sci. USA, 96, 6, 3257-3262 (1999)
[46] Watts, D. J.; Strogatz, S. H., Collective dynamics of ‘small-world’ networks, Nature, 393, 6684, 440-442 (1998) · Zbl 1368.05139
[47] Zhong, W.; Sternberg, P. W., Genome-wide prediction of c. elegans genetic interactions, Science, 311, 5766, 1481-1484 (2006)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.