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.

15 pages, 14 figures

References in corpus (7)

• Hiding Quiet Solutions in Random Constraint Satisfaction Problems
• Stable Chimeras and Independently Synchronizable Clusters
• Emergence of Symmetry in Complex Networks
• 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