Network Quotients: Structural Skeletons of Complex Systems

Abstract

A defining feature of many large empirical networks is their intrinsic complexity. However, many networks also contain a large degree of structural repetition. An immediate question then arises: can we characterize essential network complexity while excluding structural redundancy? In this article we utilize inherent network symmetry to collapse all redundant information from a network, resulting in a coarse-graining which we show to carry the essential structural information of the `parent' network. In the context of algebraic combinatorics, this coarse-graining is known as the \emph{quotient}. We systematically explore the theoretical properties of network quotients and summarize key statistics of a variety of `real-world' quotients with respect to those of their parent networks. In particular, we find that quotients can be substantially smaller than their parent networks yet typically preserve various key functional properties such as complexity (heterogeneity and hubs vertices) and communication (diameter and mean geodesic distance), suggesting that quotients constitute the essential structural skeleton of their parent network. We summarize with a discussion of potential uses of quotients in analysis of biological regulatory networks and ways in which using quotients can reduce the computational complexity of network algorithms.

8 pages, 5 figures

References in corpus (19)

• 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
• Assortative mixing in networks
• Hierarchical organization of modularity in metabolic networks
• The large-scale organization of metabolic networks
• Classes of behavior of small-world networks
• Self-similarity of complex networks
• Universal Behavior of Load Distribution in Scale-free Networks
• Heterogeneity in oscillator networks: Are smaller worlds easier to synchronize?
• Size reduction of complex networks preserving modularity
• Skeleton and fractal scaling in complex networks
• Entropy Optimization of Scale-Free Networks Robustness to Random Failures
• Scale-free trees: the skeletons of complex networks
• Symmetry based Structure Entropy of Complex Networks
• Emergence of Symmetry in Complex Networks
• Symmetry and Self-Organization in Complex Systems

Cited by in corpus (15)

• Correlation of Automorphism Group Size and Topological Properties with Program-size Complexity Evaluations of Graphs and Complex Networks
• Spectral Characteristics of Network Redundancy
• 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
• The rigorous solution for the average distance of a Sierpinski network
• An alternative approach to determining average distance in a class of scale-free modular networks
• The Essential Synchronization Backbone Problem
• Approximate Network Symmetry
• Algebraic and Topological Indices of Molecular Pathway Networks in Human Cancers
• Graph Iso/Auto-morphism: A Divide-&-Conquer Approach
• Relations Between Graphs