Emergent Network Modularity

Abstract

We introduce a network growth model based on complete redirection: a new node randomly selects an existing target node, but attaches to a random neighbor of this target. For undirected networks, this simple growth rule generates unusual, highly modular networks. Individual network realizations typically contain multiple macrohubs---nodes whose degree scales linearly with the number of nodes $N$. The size of the network "nucleus"---the set of nodes of degree greater than one---grows sublinearly with $N$ and thus constitutes a vanishingly small fraction of the network. The network therefore consists almost entirely of leaves (nodes of degree one) as $N\to \infty$.

21 pages, 10 figures, 2 appendices. Minor corrections in version2. For publication in JSTAT

References in corpus (20)

• Catastrophic cascade of failures in interdependent networks
• Multilayer Networks
• The structure and dynamics of multilayer networks
• Organization of Growing Random Networks
• Growing networks with local rules: preferential attachment, clustering hierarchy and degree correlations
• Triadic closure as a basic generating mechanism of communities in complex networks
• Origins of power-law degree distribution in the heterogeneity of human activity in social networks
• Log-Networks
• Network geometry with flavor: from complexity to quantum geometry
• Exponential Random Simplicial Complexes
• Extremal Properties of Random Systems
• Spatially distributed social complex networks
• Scale Invariance and Lack of Self-Averaging in Fragmentation
• Scale-free networks as preasymptotic regimes of superlinear preferential attachment
• Stable Distributions in Stochastic Fragmentation
• Designer Nets from Local Strategies
• Sublinear but Never Superlinear Preferential Attachment by Local Network Growth
• Highly Dispersed Networks Generated by Enhanced Redirection
• Highly Dispersed Networks
• Random Ancestor Trees

Cited by in corpus (4)

• Network Geometry and Complexity
• Random Recursive Hypergraphs
• Sparse power-law network model for reliable statistical predictions based on sampled data
• The Magic of Networks Grown by Redirection