Phase Transitions in Finite Random Networks
- PDF / 7,769,704 Bytes
- 24 Pages / 439.37 x 666.142 pts Page_size
- 47 Downloads / 180 Views
Phase Transitions in Finite Random Networks Joe Neeman1
· Charles Radin1 · Lorenzo Sadun1
Received: 2 March 2020 / Accepted: 29 May 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract We analyze ensembles of random networks with fixed numbers of edges, triangles, and nodes. In the limit as the number of nodes goes to infinity, this model is known to exhibit sharp phase transitions as the density of edges and triangles is varied. In this paper we study finite size effects in ensembles where the number of nodes is between 30 and 66. Despite the small number of nodes, the phases and phase transitions are clearly visible. Concentrating on 54 nodes and one particular phase transition, we use spectral data to examine the structure of a typical graph in each phase, and see that is it very similar to the graphon that describes the system as n diverges. We further investigate how graphs change their structure from that of one phase to the other under a natural edge flip dynamics in which the number of triangles is either forced downwards or allowed to drift upwards. In each direction, spectral data shows that the change occurs in three stages: a very fast stage of about 100 edge flips, in which the triangle count reaches the targeted value, a slower second stage of several thousand edge flips in which the graph adopts the qualitative features of the new phase, and a very slow third stage, requiring hundreds of thousands of edge flips, in which the fine details of the structure equilibrate. Keywords Random graph · Phase transition · Finite size effect · Markov Chain Monte Carlo · Graphon
1 Introduction We analyze the ‘edge/triangle’ random network model popularized by Strauss in 1986 [21], focusing on the emergence of phases and phase transitions as system size increases. Such transitions have been found in a variety of parametric random network models (see [8,14]
Communicated by Federico Ricci-Tersenghi.
B
Joe Neeman [email protected] Charles Radin [email protected] Lorenzo Sadun [email protected]
1
Department of Mathematics, The University of Texas at Austin, Austin, TX 78712, USA
123
J. Neeman et al.
and references therein). n Specifically, consider a graph with n vertices, where n is large. Fix the fraction e of the 2 possible edges that are actually present, and fix the fraction t of the n 3 triples of vertices that form triangles. How many such graphs exist? What is the structure of a typical graph? Especially, how does this structure change as the parameters e and t are varied? In the n → ∞ limit, large deviations theory reformulates these questions into questions about optimal graphons. Fixing the values of e and t is equivalent to applying integral constraints to the graphon, and finding the structure of a typical graph is equivalent to maximizing an entropy functional subject to those constraints. The entropy and the optimizing graphons are piecewise analytic functions of (e, t). We call each region of analyticity in the (e, t) plane a phase, and the b
Data Loading...
