Spectral Characteristics of Network Redundancy

Abstract

Many real-world complex networks contain a significant amount of structural redundancy, in which multiple vertices play identical topological roles. Such redundancy arises naturally from the simple growth processes which form and shape many real-world systems. Since structurally redundant elements may be permuted without altering network structure, redundancy may be formally investigated by examining network automorphism (symmetry) groups. Here, we use a group-theoretic approach to give a complete description of spectral signatures of redundancy in undirected networks. In particular, we describe how a network's automorphism group may be used to directly associate specific eigenvalues and eigenvectors with specific network motifs.

12 pages, 51 figures, significant improvements

References in corpus (3)

• Classes of complex networks defined by role-to-role connectivity profiles
• Network Quotients: Structural Skeletons of Complex Systems
• Spectral transitions in networks

Cited by in corpus (24)

• Symmetries, Cluster Synchronization, and Isolated Desynchronization in Complex Networks
• Complete Characterization of Stability of Cluster Synchronization in Complex Dynamical Networks
• Topological strata of weighted complex networks
• Symmetries and Cluster Synchronization in Multilayer Networks
• Stable Chimeras and Independently Synchronizable Clusters
• Dimensionality reduction and spectral properties of multilayer networks
• Exploiting symmetry in network analysis
• Complex Networks and Symmetry I: A Review
• Hidden Symmetries in Real and Theoretical Networks
• Partial Synchronization and Partial Amplitude Death in Mesoscale Network Motifs
• Does the brain behave like a (complex) network? I. Dynamics
• Complex Networks and Symmetry II: Reciprocity and Evolution of World Trade
• Sensitive Dependence of Optimal Network Dynamics on Network Structure
• Mesoscale symmetries explain dynamical equivalence of food webs
• Normalized Laplace Operators for Hypergraphs with Real Coefficients
• Symmetric motifs in random geometric graphs
• Stability of networks of delay-coupled delay oscillators
• Zoo Guide to Network Embedding
• Symmetry in Critical Random Boolean Network Dynamics
• Geometry and symmetry in biochemical reaction systems
• Estimating cellular redundancy in networks of genetic expression
• Symmetry-based coarse-graining of evolved dynamical networks
• An introduction to spectral distances in networks (extended version)
• Emergence of a spectral gap in a class of random matrices associated with split graphs