Asymptotic structure and singularities in constrained directed graphs
arXiv:1405.2466 · doi:10.1016/j.spa.2015.06.004
Abstract
We study the asymptotics of large directed graphs, constrained to have certain densities of edges and/or outward -stars. Our models are close cousins of exponential random graph models (ERGMs), in which edges and certain other subgraph densities are controlled by parameters. The idea of directly constraining edge and other subgraph densities comes from Radin and Sadun. Such modeling circumvents a phenomenon first made precise by Chatterjee and Diaconis: that in ERGMs it is often impossible to independently constrain edge and other subgraph densities. In all our models, we find that large graphs have either uniform or bipodal structure. When edge density (resp. -star density) is fixed and -star density (resp. edge density) is controlled by a parameter, we find phase transitions corresponding to a change from uniform to bipodal structure. When both edge and -star density are fixed, we find only bipodal structures and no phase transition.
arXiv comment24 pages, 2 figures
References in corpus (12)
- Estimating and understanding exponential random graph models
- Solution of the 2-star model of a network
- Solution for the properties of a clustered network
- Phase transitions in a complex network
- The Asymptotics of Large Constrained Graphs
- Phase transitions in exponential random graphs
- Introduction to papers on the modeling and analysis of network data
- Singularities in the entropy of asymptotically large simple graphs
- Rigorous Proof of a Liquid-Vapor Phase Transition in a Continuum Particle System
- Critical phenomena in exponential random graphs
- On the phase transition curve in a directed exponential random graph model
- Introduction to papers on the modeling and analysis of network data---II
Cited by in corpus (9)
- On the phase transition curve in a directed exponential random graph model
- On the lower tail variational problem for random graphs
- Reciprocity in directed networks
- Asymptotics for Sparse Exponential Random Graph Models
- Asymptotic Structure of Constrained Exponential Random Graph Models
- Phase transitions in edge-weighted exponential random graphs
- Phase Transitions in Edge-Weighted Exponential Random Graphs: Near-Degeneracy and Universality
- Ground States for Exponential Random Graphs
- Lattice Gas Models with Long Range Interactions