Clustering Phase Transitions and Hysteresis: Pitfalls in Constructing Network Ensembles

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.

13 pages, 11 figures

References in corpus (8)

• Modularity and community structure in networks
• Community detection in graphs
• Random graphs with clustering
• Scale free networks of earthquakes and aftershocks
• Clustering in complex networks. I. General formalism
• Solution for the properties of a clustered network
• Graph animals, subgraph sampling and motif search in large networks
• Link and subgraph likelihoods in random undirected networks with fixed and partially fixed degree sequence

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