×

Characterization of symmetry of complex networks. (English) Zbl 1425.05148

Summary: Recently, symmetry in complex network structures has attracted some research interest. One of the fascinating problems is to give measures of the extent to which the network is symmetric. In this paper, based on the natural action of the automorphism group \(\mathrm{Aut}(\Gamma)\) of \(\Gamma\) on the vertex set \(V\) of a given network \(\Gamma =\Gamma(V, E)\), we propose three indexes for the characterization of the global symmetry of complex networks. Using these indexes, one can get a quantitative characterization of how symmetric a network is and can compare the symmetry property of different networks. Moreover, we compare these indexes to some existing ones in the literature and apply these indexes to real-world networks, concluding that real-world networks are far from vertex symmetric ones.

MSC:

05C82 Small world graphs, complex networks (graph-theoretic aspects)
90B10 Deterministic network models in operations research

Software:

bliss

References:

[1] Albert, R.; Barabasi, A.L.; Statistical mechanics of complex networks; Rev. Mod. Phys.: 2002; Volume 74 ,47-97. · Zbl 1205.82086
[2] Watts, D.J.; Strogatz, S.H.; Collective dynamics of ‘small-world’ networks; Nature: 1998; Volume 393 ,440-442. · Zbl 1368.05139
[3] Barabasi, A.L.; Albert, R.; Emergence of scaling in random networks; Science: 1999; Volume 286 ,509-512. · Zbl 1226.05223
[4] Casterllani, E.; On the meaning of symmetry breaking; Symmetries in Physics: Philosophical Reflections: Cambridge, UK 2003; .
[5] Weyl, H.; ; Symmetry: Princeton, NJ, USA 1952; . · Zbl 0046.00406
[6] Xiao, Y.; Xiong, M.; Wang, W.; Wang, H.; Emergence of symmetry in complex networks; Phys. Rev. E: 2008; Volume 77 .
[7] Xiao, Y.; Wu, W.H.; Wang, H.; Xiong, M.; Wang, W.; Symmetry-based structure entropy of complex networks; Physica A: 2008; Volume 387 ,2611-2619.
[8] Holme, P.; Detecting degree symmetries in networks; Phys. Rev. E: 2006; Volume 74 .
[9] Holme, P.; Local Symmetries in Complex Networks; ; . · Zbl 1203.90047
[10] Garrido, A.; Symmetry in complex networks; Symmetry: 2011; Volume 3 ,1-15. · Zbl 1360.05162
[11] MacArthur, B.D.; Sánchez-García, R.J.; Anderson, J.W.; Symmetry in complex networks; Discret. Appl. Math.: 2008; Volume 156 ,3525-3531. · Zbl 1168.05058
[12] Akers, S.; Krishnamurthy, B.; A group-theoretic model for symmetric interconnection networks; IEEE Trans. Comp.: 1989; Volume 38 ,555-566. · Zbl 0678.94026
[13] MacArthur, B.D.; Anderson, J.W.; Symmetry and Self-Organization in Complex Systems; ; .
[14] Herstein, I.N.; ; Topics in Algebra: Hoboken, NJ, USA 1975; . · Zbl 1230.00004
[15] Humke, P.D.; Lagrange’s Theorem: Statement and Proof; ; .
[16] Junttila, T.; Kaski, P.; Engineering an efficient canonical labeling tool for large and sparse graphs; Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments and the Fourth Workshop on Analytic Algorithms and Combinatorics: ; . · Zbl 1325.05169
[17] Zachary, W.W.; An information flow model for conflict and fission in small groups; J. Anthropol. Res.: 1977; Volume 33 ,452-473.
[18] Lusseau, D.; Schneider, K.; Boisseau, O.J.; Haase, P.; Slooten, E.; Dawson, S.M.; The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations; Behav. Ecol. Sociobiol.: 2003; Volume 54 ,396-405.
[19] Newman, M.E.J.; Finding community structure in networks using the eigenvectors of matrices; Phys. Rev. E: 2006; Volume 74 ,036104.
[20] Girvan, M.; Newman, M.E.J.; Community structure in social and biological networks; Proc. Natl. Acad. Sci. USA: 2002; Volume 99 ,7821-7826. · Zbl 1032.91716
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.