Phase transitions in a complex network

DOI10.1088/1751-8113/46/30/305002MaRDI QIDQ2843754zbMATH OpenOpenAlexFDO

Authors Charles Radin, Lorenzo Sadun

Publication date 26 August 2013

Published in Journal of Physics A: Mathematical and Theoretical (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1301.1256

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80) Phase transitions (general) in equilibrium statistical mechanics (82B26)

Abstract: We study a mean field model of a complex network, focusing on edge and triangle densities. Our first result is the derivation of a variational characterization of the entropy density, compatible with the infinite node limit. We then determine the optimizing graphs for small triangle density and a range of edge density, though we can only prove they are local, not global, maxima of the entropy density. With this assumption we then prove that the resulting entropy density must lose its analyticity in various regimes. In particular this implies the existence of a phase transition between distinct heterogeneous multipartite phases at low triangle density, and a phase transition between these phases and the disordered phase at high triangle density.

Review text

This article approaches the study of phase transitions in complex networks, more concretely, in exponential random graphs. The authors pursue their objective employing the formalism of graphons, a useful methodology that allows the application of powerful techniques from different fields, such as mathematical analysis, in a problem which is combinatoric in origin. In particular, this formalism allows the use of large deviation theory within this context. This theory is used to prove a variational characterization of the entropy density. This variational characterization is used in turn to find graphons which are local maximizers of the entropy density. This gives some evidence of the presence of phase transitions; nevertheless, the full proof requires establishing that these maximizers are in fact global. This is postponed by the authors to a forthcoming article.

Recommendations

• The phases of large networks with edge and triangle constraints
• A symmetry breaking transition in the edge/triangle network model
• Phase transitions in finite random networks
• Phase transitions in social networks
• Singularities in the entropy of asymptotically large simple graphs

Cited in

(43)

• Phase transitions in networks of chaotic elements with short and long range interactions
• Ferromagnetic phase transition in Barabási-Albert networks
• Reciprocity in directed networks
• A symmetry breaking transition in the edge/triangle network model
• Ensemble equivalence for dense graphs
• Phase transitions in edge-weighted exponential random graphs: near-degeneracy and universality
• A large deviation principle for the Erdős-Rényi uniform random graph
• Regular graphs with many triangles are structured
• Topological transition in a coupled dynamics in random networks
• Large deviation for uniform graphs with given degrees
• Phase transitions in finite random networks
• Approximating the cumulant generating function of triangles in the Erdös-Rényi random graph
• Singularities in the entropy of asymptotically large simple graphs
• Asymptotic structure of constrained exponential random graph models
• Multipodal structure and phase transitions in large constrained graphs
• Estimating and understanding exponential random graph models
• An introduction to large deviations for random graphs
• Ensemble nonequivalence in random graphs with modular structure
• Lattice gas models with long range interactions
• Driven transitions at the onset of ergodicity breaking in gauge-invariant complex networks
• Ground states for exponential random graphs
• A detailed investigation into near degenerate exponential random graphs
• Vertex order in some large constrained random graphs
• Ensemble inequivalence and absence of quasi-stationary states in long-range random networks
• PHASE TRANSITION IN THE ISING MODEL ON LOCAL-WORLD EVOLVING NETWORKS
• The phases of large networks with edge and triangle constraints
• On the asymptotics of constrained exponential random graphs
• Asymptotic structure and singularities in constrained directed graphs
• Phase transition in information propagation on high-order networks
• Asymptotic structure of graphs with the minimum number of triangles
• On the lower tail variational problem for random graphs
• Phase transitions in optimized network models
• The birth of geometry in exponential random graphs
• Moderate deviations in cycle count
• Complexity, scaling, and a phase transition
• Limits of multi-relational graphs
• Typical large graphs with given edge and triangle densities
• Connectivity of Poissonian inhomogeneous random multigraphs
• Existence of a symmetric bipodal phase in the edge-triangle model
• Typical structure of sparse exponential random graph models
• Optimal graphons in the edge-2star model
• Tripodal structure in undersaturated random graphs
• Concentration via metastable mixing, with applications to the supercritical exponential random graph model

This page was built for publication: Phase transitions in a complex network

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2843754)