Approximate Network Symmetry

Abstract

We define a new measure of network symmetry that is capable of capturing approximate global symmetries of networks. We apply this measure to different networks sampled from several classic network models, as well as several real-world networks. We find that among the network models that we have examined, Erdös-Rényi networks have the least levels of symmetry, and Random Geometric Graphs are likely to have high levels of symmetry. We find that our network symmetry measure can capture properties of network structure, and help us gain insights on the structure of real-world networks. Moreover, our network symmetry measure is capable of capturing imperfect network symmetry, which would have been undetected if only perfect symmetry is considered.

arXiv comment15 pages, 14 figures

References in corpus (12)

• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Symmetries, Cluster Synchronization, and Isolated Desynchronization in Complex Networks
• Complete Characterization of Stability of Cluster Synchronization in Complex Dynamical Networks
• On Automorphism Groups of Networks
• Hiding Quiet Solutions in Random Constraint Satisfaction Problems
• Stable Chimeras and Independently Synchronizable Clusters
• Emergence of Symmetry in Complex Networks
• Evolution and development of Brain Networks: From Caenorhabditis elegans to Homo sapiens
• Fibration symmetries uncover the building blocks of biological networks
• Network Quotients: Structural Skeletons of Complex Systems
• Circuits with broken fibration symmetries perform core logic computations in biological networks
• Symmetry and Self-Organization in Complex Systems