January 7, 2013
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.
Similar papers 1
April 27, 2016
Our general subject is the emergence of phases, and phase transitions, in large networks subjected to a few variable constraints. Our main result is the analysis, in the model using edge and triangle subdensities for constraints, of a sharp transition between two phases with different symmetries, analogous to the transition between a fluid and a crystalline solid.
January 16, 2017
Based on numerical simulation and local stability analysis we describe the structure of the phase space of the edge/triangle model of random graphs. We support simulation evidence with mathematical proof of continuity and discontinuity for many of the phase transitions. All but one of themany phase transitions in this model break some form of symmetry, and we use this model to explore how changes in symmetry are related to discontinuities at these transitions.
March 7, 2007
We present a statistical mechanics approach for the description of complex networks. We first define an energy and an entropy associated to a degree distribution which have a geometrical interpretation. Next we evaluate the distribution which extremize the free energy of the network. We find two important limiting cases: a scale-free degree distribution and a finite-scale degree distribution. The size of the space of allowed simple networks given these distribution is evaluat...
May 25, 2004
We study the family of network models derived by requiring the expected properties of a graph ensemble to match a given set of measurements of a real-world network, while maximizing the entropy of the ensemble. Models of this type play the same role in the study of networks as is played by the Boltzmann distribution in classical statistical mechanics; they offer the best prediction of network properties subject to the constraints imposed by a given set of observations. We giv...
October 11, 2018
In the last 15 years, statistical physics has been a very successful framework to model complex networks. On the theoretical side, this approach has brought novel insights into a variety of physical phenomena, such as self-organisation, scale invariance, emergence of mixed distributions and ensemble non-equivalence, that display unconventional features on heterogeneous networks. At the same time, thanks to their deep connection with information theory, statistical physics and...
September 24, 2003
We provide a phenomenological theory for topological transitions in restructuring networks. In this statistical mechanical approach energy is assigned to the different network topologies and temperature is used as a quantity referring to the level of noise during the rewiring of the edges. The associated microscopic dynamics satisfies the detailed balance condition and is equivalent to a lattice gas model on the edge-dual graph of a fully connected network. In our studies -- ...
February 19, 2019
We analyze the 3-parameter family of random networks which are uniform on networks with fixed number of edges, triangles, and nodes (between 33 and 66). We find precursors of phase transitions which are known to be present in the asymptotic node regime as the edge and triangle numbers are varied, and focus on one of the discontinuous ones. By use of a natural edge flip dynamics we determine nucleation barriers as a random network crosses the transition, in analogy to the proc...
July 9, 2009
The quantification of the complexity of networks is, today, a fundamental problem in the physics of complex systems. A possible roadmap to solve the problem is via extending key concepts of information theory to networks. In this paper we propose how to define the Shannon entropy of a network ensemble and how it relates to the Gibbs and von Neumann entropies of network ensembles. The quantities we introduce here will play a crucial role for the formulation of null models of n...
October 10, 2011
We consider a large class of exponential random graph models and prove the existence of a region of parameter space corresponding to multipartite structure, separated by a phase transition from a region of disordered graphs.
June 15, 2021
Clustering $\unicode{x2013}$ the tendency for neighbors of nodes to be connected $\unicode{x2013}$ quantifies the coupling of a complex network to its latent metric space. In random geometric graphs, clustering undergoes a continuous phase transition, separating a phase with finite clustering from a regime where clustering vanishes in the thermodynamic limit. We prove this geometric-to-nongeometric phase transition to be topological in nature, with anomalous features such as ...