Large, Dense Networks
Consider a network or graph G consisting of a large number N of nodes,
each distinct pair of which may or may not be connected by an
undirected edge. Think of each of the (N[N-1]/2 unordered) pairs of
nodes as a point in a space which may or may not be `occupied' by an
edge. We will treat edges as one treats particles in equilibrium
statistical mechanics: we will assume that a graph G is a random
object in a fixed space of `volume' N(N-1)/2, and will study a two-parameter
family of sets of graphs G in analogy with the microcanonical ensemble in
statistical mechanics.
In the microcanonical ensemble of statistical mechanics the two
parameters are (the dynamical invariants) particle density and energy density, and one studies
the partition function Z(d,h;V) which is the volume of the set
of configurations of particle density d and energy density h, in a
space of fixed volume V [FR]. Z is appropriately normalized as the entropy
density s(d,h;V) = (1/V)ln(Z).
The analogue of the particle density for networks will be the edge density d(G) of
G. We will take as the energy of G the count of some subgraph; the
Strauss model would use the number of triangles in G, though any
subgraph H with 2 or more edges would be acceptable. We normalize this
energy so that the `energy density' h(G) of the complete graph is 1.
So after choosing some finite graph H for use as an energy, we study
the entropy s(d,h;N)=[2/N(N-1)]ln(Z).
The interesting features of statistical mechanics come from the
interference or tension between the two parameters or densities. For
instance, if at constant energy density the particle density is raised
high enough, it is typical that the system of particles comes to
represent a highly structured crystal, while at low density it
represents a disordered gas; see our discussion on
hard sphere models [R]. The physical properties of the material
are computable from partial derivatives of the entropy [C], so there is
obvious interest in parameter values where such derivatives
are discontinuous or diverge, which are hallmarks of
phase transitions [FR]. Thinking of a large network as a material,
one might model it as above if indeed the choice of H for `energy' is
reasonable. This is presumably not the case for such
networks, so we think of these models as purely mathematical, determining what a typical
large, constrained graph is like and exploring the
world of phases and phase transitions more generally. Assuming
this we have carried out the above to some extent, following the
pioneering work of Chatterjee and Diaconis [CD]. More specifically, we
have worked in both the grand canonical ensemble and the
microcanonical ensemble, and used the large deviation principle of
Chatterjee and Varadhan [CV] and
formalism of limit graphs
developed by Lovász et al [L] to prove various phase transitions in dense
networks similar to the liquid/gas [RY],
[KRRS1],
[KRRS2],
and fluid/solid
[AR],
[RRS1],
[RS1],
[RS2],
[KRRS1],
[KRRS3],
[NRS1],
[NRS2],
[NRS3]
[NRS4]
transitions in molecular materials. (As opposed to statistical
mechanics here the microcanonical ensemble plays a privileged role,
with a loss of information in the grand canonical ensemble
[RS1].)
The structure that appears in the `solid' phase
of dense networks is balanced multipartite, and the analogue of the
`fluid' phase seems to be a monotone state
[KRRS1].
The solid/fluid transition is discussed in some depth in
[RRS2],
[KRRS3],
and indirectly in
[RRS3],
[NRS4].
There is a less-advanced analogue of the above ideas, concerning large
permutations, in
[KKRW],
and an expository article on all the above in
[R2].
References
[AR] D. Aristoff and C. Radin,
Emergent structures in large networks,
J. Appl. Probab. 50(2013) 883-888.
[C] H.G. Callen,
Thermodynamics,
John Wiley, New York, 1960.
[CD] S. Chatterjee and P. Diaconis,
Estimating and understanding exponential random graph models,
Ann. Statist. 41 (2013) 2428-2461.
[CV] S. Chatterjee and S.R.S. Varadhan, The large deviation principle
for the Erdos-R{e}nyi random graph, Eur. J. Comb. 32 (2011)
1000-1017.
[FR] M. Fisher and C. Radin,
Definition of Thermodynamic Phases and Phase Transitions,
AIM workshop, (2006),
http://www.aimath.org/WWN/phasetransition/Defs16.pdf.
[KRRS1] R. Kenyon, C. Radin, K. Ren and L. Sadun,
Multipodal structure and phase transitions in large constrained
graphs,
J. Stat. Phys. (2017) 233-258 doi:10.1007/s10955-017-1804-0
[KRRS2] R. Kenyon, C. Radin, K. Ren and L. Sadun,
Bipodal structure in oversaturated random graphs,
Int. Math. Res. Notices 2018(2016) 1009-1044
[KRRS3] R. Kenyon, C. Radin, K. Ren and L. Sadun,
The phases of large networks with edge and triangle
constraints,
J. Phys. A: Math. Theor. 50(2017) 435001.
[KKRW] R. Kenyon, D. Král’, C. Radin and P. Winkler
Permutations with fixed pattern densities,
Random Structures Algorithms,
DOI: 10.1002/rsa.20882.
[L] L. Lovász,
Large networks and graph limits, American Mathematical Society, Providence, 2012.
[NRS1] J. Neeman, C. Radin and L. Sadun,
Phase transitions in finite random networks,
J Stat Phys 181 (2020) 305-328.
[NRS2] J. Neeman, C. Radin and L. Sadun,
Moderate deviations in cycle count,
arxiv:2101.08249.
[NRS3] J. Neeman, C. Radin and L. Sadun,
Typical large graphs with given edge and triangle densities,
arxiv:2110.14052,
online first, in Probab. Theory Relat. Fields.
[NRS4] J. Neeman, C. Radin and L. Sadun,
Existence of a symmetric bipodal phase in the edge-triangle model,
arxiv:2211.10498.
[R] C. Radin,
The "most probable" sphere packings, and models of soft matter,
http://www.ma.utexas.edu/users/radin/spheres.html.
[R2] C. Radin,
Phases in large combinatorial systems,
Ann. Inst. H. Poincaré D 5(2018) 287-308.
[RRS1] C. Radin, K. Ren and L. Sadun,
The asymptotics of large constrained graphs,
J. Phys. A: Math. Theor. 47 (2014) 175001
color.pdf
grayscale.pdf
[RS1] C. Radin and L. Sadun,
Phase transitions in a complex network,
J. Phys. A: Math. Theor. 46 (2013) 305002.
[RS2] C. Radin and L. Sadun,
Singularities in the entropy of asymptotically large simple graphs,
J. Stat. Phys. 158 (2015) 853-865.
[RY] C. Radin and M. Yin,
Phase transitions in exponential random graphs,
Ann. Appl. Probab. 23(2013) 2458-2471.
[RRS2] C. Radin, K. Ren and L. Sadun,
A symmetry breaking transition in the edge/triangle network model,
Ann. Inst. H. Poincaré D 5(2018) 251-286.
[RRS3] C. Radin, K. Ren and L. Sadun,
Surface effects in dense random graphs with sharp edge constraint,
arXiv:1709.01036v1
preprint