Symmetry based Structure Entropy of Complex Networks

Abstract

Precisely quantifying the heterogeneity or disorder of a network system is very important and desired in studies of behavior and function of the network system. Although many degree-based entropies have been proposed to measure the heterogeneity of real networks, heterogeneity implicated in the structure of networks can not be precisely quantified yet. Hence, we propose a new structure entropy based on automorphism partition to precisely quantify the structural heterogeneity of networks. Analysis of extreme cases shows that entropy based on automorphism partition can quantify the structural heterogeneity of networks more precisely than degree-based entropy. We also summarized symmetry and heterogeneity statistics of many real networks, finding that real networks are indeed more heterogenous in the view of automorphism partition than what have been depicted under the measurement of degree based entropies; and that structural heterogeneity is strongly negatively correlated to symmetry of real networks.

7 pages, 6 figures

References in corpus (18)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• The structure and function of complex networks
• Error and attack tolerance of complex networks
• Assortative mixing in networks
• Mixing patterns in networks
• Specificity and stability in topology of protein networks
• Characterization of complex networks: A survey of measurements
• Self-similarity of complex networks
• Dynamical and correlation properties of the Internet
• Universal Behavior of Load Distribution in Scale-free Networks
• Heterogeneity in oscillator networks: Are smaller worlds easier to synchronize?
• Entropy Optimization of Scale-Free Networks Robustness to Random Failures
• Correlated random networks
• Self-similarity, small-world, scale-free scaling, disassortativity, and robustness in hierarchical lattices
• Emergence of Symmetry in Complex Networks
• Role-similarity based functional prediction in networked systems: Application to the yeast proteome
• Symmetry and Self-Organization in Complex Systems

Cited by in corpus (7)

• Emergence of Symmetry in Complex Networks
• Network Quotients: Structural Skeletons of Complex Systems
• Multifractal Characterization of Protein Contact Networks
• A betweenness structure entropy of complex networks
• A new structure entropy of complex networks based on Tsallis nonextensive statistical mechanics
• Tsallis entropy of complex networks
• Graph Iso/Auto-morphism: A Divide-&-Conquer Approach