Clustering Phase Transitions and Hysteresis: Pitfalls in Constructing Network Ensembles
arXiv:0911.2055 · doi:10.1103/PhysRevE.81.046115
Abstract
Ensembles of networks are used as null models in many applications. However, simple null models often show much less clustering than their real-world counterparts. In this paper, we study a model where clustering is enhanced by means of a fugacity term as in the Strauss (or "triangle") model, but where the degree sequence is strictly preserved -- thus maintaining the quenched heterogeneity of nodes found in the original degree sequence. Similar models had been proposed previously in [R. Milo et al., Science 298, 824 (2002)]. We find that our model exhibits phase transitions as the fugacity is changed. For regular graphs (identical degrees for all nodes) with degree k > 2 we find a single first order transition. For all non-regular networks that we studied (including Erdos - Renyi and scale-free networks) we find multiple jumps resembling first order transitions, together with strong hysteresis. The latter transitions are driven by the sudden emergence of "cluster cores": groups of highly interconnected nodes with higher than average degrees. To study these cluster cores visually, we introduce q-clique adjacency plots. We find that these cluster cores constitute distinct communities which emerge spontaneously from the triangle generating process. Finally, we point out that cluster cores produce pitfalls when using the present (and similar) models as null models for strongly clustered networks, due to the very strong hysteresis which effectively leads to broken ergodicity on realistic time scales.
arXiv comment13 pages, 11 figures
References in corpus (35)
- Emergence of scaling in random networks
- Finding and evaluating community structure in networks
- Modularity and community structure in networks
- Community detection in graphs
- Finding community structure in very large networks
- Fast algorithm for detecting community structure in networks
- Assortative mixing in networks
- Hierarchical organization of modularity in metabolic networks
- The large-scale organization of metabolic networks
- Random graphs with arbitrary degree distributions and their applications
- Specificity and stability in topology of protein networks
- Hierarchical Organization in Complex Networks
- Self-similar community structure in organisations
- Why social networks are different from other types of networks
- Growing Scale-Free Networks with Tunable Clustering
- Vertex similarity in networks
- The statistical mechanics of networks
- Random graphs with clustering
- Properties of highly clustered networks
- Scale free networks of earthquakes and aftershocks
- Emergence of a small world from local interactions: Modeling acquaintance networks
- Generic scale of the "scale-free" growing networks
- Avalanches, Barkhausen Noise, and Plain Old Criticality
- Correlated random networks
- Clustering in complex networks. I. General formalism
- Dynamics of a ferromagnetic domain wall and the Barkhausen effect
- Tuning clustering in random networks with arbitrary degree distributions
- Solution for the properties of a clustered network
- Rate equation approach for correlations in growing network models
- Random Networks with Tunable Degree Distribution and Clustering
- Network Transitivity and Matrix Models
- Solar Flares as Cascades of Reconnecting Magnetic Loops
- Earthquake recurrence as a record breaking process
- Link and subgraph likelihoods in random undirected networks with fixed and partially fixed degree sequence
- Graph animals, subgraph sampling and motif search in large networks
Cited by in corpus (16)
- The Statistical Physics of Real-World Networks
- Explosive Phenomena in Complex Networks
- Quantifying randomness in real networks
- Entropy of stochastic blockmodel ensembles
- Discontinuous Percolation Transitions in Epidemic Processes, Surface Depinning in Random Media and Hamiltonian Random Graphs
- Clustering implies geometry in networks
- Deciphering the global organization of clustering in real complex networks
- Clustering Drives Assortativity and Community Structure in Ensembles of Networks
- Phase transitions in random Potts systems and the community detection problem: spin-glass type and dynamic perspectives
- Disentangling homophily, community structure and triadic closure in networks
- Sampling motif-constrained ensembles of networks
- Interacting Thermofield Doubles and Critical Behavior in Random Regular Graphs
- Scaling relations and finite-size scaling in gravitationally correlated lattice percolation models
- Random degree-degree correlated networks
- Relaxation dynamics of maximally clustered networks
- Free-energy density functional for Strauss's model of transitive networks