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 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 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 interaction of 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 has not been well justified in practice. But 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 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] and fluid/solid [AR], [RS1], [RS2] transitions in molecular materials. The structure that appears in the `solid' phase of dense networks is multipartite.

References

[AR] D. Aristoff and C. Radin, Emergent structures in large networks, arXiv:1110.1912, to appear in J. Appl. Probab..

[C] H.G. Callen, Thermodynamics, John Wiley, New York, 1960.

[CD] S. Chatterjee and P. Diaconis, Estimating and understanding exponential random graph models, arXiv: 1102.2650v3.

[FR] M. Fisher and C. Radin, Definition of Thermodynamic Phases and Phase Transitions, AIM workshop, (2006), http://www.aimath.org/WWN/phasetransition/Defs16.pdf.

[L] L. Lovász, Large networks and graph limits, American Mathematical Society, Providence, 2012.

[R] C. Radin, The "most probable" sphere packings, and models of soft matter, http://www.ma.utexas.edu/users/radin/papers/networks.pdf.

[RS1] C. Radin and L. Sadun, A mean field analysis of the fluid/solid phase transition, arXiv:1301.1256.

[RS2] C. Radin and L. Sadun, Singularities in the entropy of asymptotically large simple graphs, arXiv:1302.3531.

[RY] C. Radin and M. Yin, Phase transitions in exponential random graphs, arXiv:1108.0649, to appear in Ann. Appl. Probab.