The Asymptotics of Large Constrained Graphs
arXiv:1401.1170 · doi:10.1088/1751-8113/47/17/175001
Abstract
We show, through local estimates and simulation, that if one constrains simple graphs by their densities of edges and of triangles, then asymptotically (in the number of vertices) for over of the possible range of those densities there is a well-defined typical graph, and it has a very simple structure: the vertices are decomposed into two subsets and of fixed relative size and , and there are well-defined probabilities of edges, , between , and . Furthermore the four parameters and are smooth functions of except at two smooth `phase transition' curves.
References in corpus (7)
- Estimating and understanding exponential random graph models
- An Introduction to the Thermodynamic and Macrostate Levels of Nonequivalent Ensembles
- Phase transitions in a complex network
- Phase transitions in exponential random graphs
- Asymptotic Structure of Graphs with the Minimum Number of Triangles
- Critical phenomena in exponential random graphs
- Minimum Number of k-Cliques in Graphs with Bounded Independence Number
Cited by in corpus (19)
- Clustering implies geometry in networks
- The phases of large networks with edge and triangle constraints
- Asymptotic Structure of Graphs with the Minimum Number of Triangles
- On the lower tail variational problem for random graphs
- Asymptotic structure and singularities in constrained directed graphs
- On the asymptotics of constrained exponential random graphs
- Asymptotics for Sparse Exponential Random Graph Models
- Reciprocity in directed networks
- The birth of geometry in exponential random graphs
- Elusive extremal graphs
- Asymptotic Structure of Constrained Exponential Random Graph Models
- Large deviations and exact asymptotics for constrained exponential random graphs
- Simple evolving random graphs
- Phase Transitions in Edge-Weighted Exponential Random Graphs: Near-Degeneracy and Universality
- Regular graphs with linearly many triangles
- Nucleation during phase transitions in random networks
- Surface effects in dense random graphs with sharp edge constraint
- Lattice Gas Models with Long Range Interactions
- Ground States for Exponential Random Graphs