Spectral Characteristics of Network Redundancy
arXiv:0904.3192 · doi:10.1103/PhysRevE.80.026117
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.
arXiv comment12 pages, 51 figures, significant improvements
References in corpus (15)
- 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
- Lethality and centrality in protein networks
- The diameter of the world wide web
- The large-scale organization of metabolic networks
- Spectra of "Real-World" Graphs: Beyond the Semi-Circle Law
- Classes of complex networks defined by role-to-role connectivity profiles
- Spectra of complex networks
- Spectra and eigenvectors of scale-free networks
- On Automorphism Groups of Networks
- Network Quotients: Structural Skeletons of Complex Systems
- Spectral Analysis of Protein-Protein Interactions in Drosophila melanogaster
- 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