Exploiting symmetry in network analysis
arXiv:1803.06915 · doi:10.1038/s42005-020-0345-z
Abstract
Virtually all network analyses involve structural measures between pairs of vertices, or of the vertices themselves, and the large amount of symmetry present in real-world complex networks is inherited by such measures. This has practical consequences which have not yet been explored in full generality, nor systematically exploited by network practitioners. Here we study the effect of network symmetry on arbitrary network measures, and show how this can be exploited in practice in a number of ways, from redundancy compression, to computational reduction. We also uncover the spectral signatures of symmetry for an arbitrary network measure such as the graph Laplacian. Computing network symmetries is very efficient in practice, and we test real-world examples up to several million nodes. Since network models are ubiquitous in the Applied Sciences, and typically contain a large degree of structural redundancy, our results are not only significant, but widely applicable.
arXiv commentAuthor name updated (accents added)
References in corpus (14)
- Emergence of scaling in random networks
- Statistical mechanics of complex networks
- Subgraph Centrality in Complex Networks
- Communicability in complex networks
- Symmetries, Cluster Synchronization, and Isolated Desynchronization in Complex Networks
- Remote synchronization reveals network symmetries and functional modules
- Complete Characterization of Stability of Cluster Synchronization in Complex Dynamical Networks
- On Automorphism Groups of Networks
- Symmetry- and Input-Cluster Synchronization in Networks
- Spectral Characteristics of Network Redundancy
- Emergence of Symmetry in Complex Networks
- Network Quotients: Structural Skeletons of Complex Systems
- Network-complement transitions, symmetries, and cluster synchronization
- Symmetry-based coarse-graining of evolved dynamical networks
Cited by in corpus (20)
- Synchronization in Network Geometries with Finite Spectral Dimension
- Multiscale dynamical embeddings of complex networks
- Complex Quantum Networks: a Topical Review
- Does the brain behave like a (complex) network? I. Dynamics
- Hierarchical community structure in networks
- Collective dynamics on higher-order networks
- Normalized Laplace Operators for Hypergraphs with Real Coefficients
- Modal Decomposition of the Linear Swing Equation in Networks with Symmetries
- Zoo Guide to Network Embedding
- Structured networks and coarse-grained descriptions: a dynamical perspective
- Quasi-symmetries in complex networks: a dynamical model approach
- Geometry and symmetry in biochemical reaction systems
- Pinning control of networks: dimensionality reduction through simultaneous block-diagonalization of matrices
- Estimating cellular redundancy in networks of genetic expression
- A3: An Automatic Topology-Aware Malfunction Detection and Fixation System in Data Center Networks
- Topologically protected synchronization in networks
- Blind Extraction of Equitable Partitions from Graph Signals
- Notes on Resonant and Synchronized States in Complex Networks
- Designing topological cluster synchronization patterns with the Dirac operator
- Partitioning networks into clusters of synchronized nodes via the message-passing algorithm: an unbiased scalable approach