Spectral characteristics of network redundancy
- 19 August 2009
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review E
- Vol. 80 (2) , 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.Keywords
All Related Versions
This publication has 33 references indexed in Scilit:
- Classes of complex networks defined by role-to-role connectivity profilesNature Physics, 2006
- Rank clocksNature, 2006
- Towards a Theory of Scale-Free Graphs: Definition, Properties, and ImplicationsInternet Mathematics, 2005
- The Structure and Function of Complex NetworksSIAM Review, 2003
- Statistical mechanics of complex networksReviews of Modern Physics, 2002
- Exploring complex networksNature, 2001
- The large-scale organization of metabolic networksNature, 2000
- Emergence of Scaling in Random NetworksScience, 1999
- Diameter of the World-Wide WebNature, 1999
- Collective dynamics of ‘small-world’ networksNature, 1998