Hostname: page-component-78c5997874-g7gxr Total loading time: 0 Render date: 2024-11-07T13:28:08.315Z Has data issue: false hasContentIssue false
  • English
  • Français

On the asymptotics of constrained exponential random graphs

Part of: Equilibrium statistical mechanics Graph theory

Published online by Cambridge University Press:  04 April 2017

Richard Kenyon  and
Mei Yin
Richard Kenyon*
Affiliation:
Brown University
Mei Yin*
Affiliation:
University of Denver
*
* Postal address: Department of Mathematics, Brown University, Providence, RI 02912, USA. Email address: [email protected]
** Postal address: Department of Mathematics, University of Denver, Denver, CO 80208, USA. Email address: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

The unconstrained exponential family of random graphs assumes no prior knowledge of the graph before sampling, but it is natural to consider situations where partial information about the graph is known, for example the total number of edges. What does a typical random graph look like, if drawn from an exponential model subject to such constraints? Will there be a similar phase transition phenomenon (as one varies the parameters) as that which occurs in the unconstrained exponential model? We present some general results for this constrained model and then apply them to obtain concrete answers in the edge-triangle model with fixed density of edges.

Keywords

Constrained exponential random graphphase transition

MSC classification

Primary: 05C80: Random graphs
Secondary: 82B26: Phase transitions (general)
Type
Research Papers
Information
Journal of Applied Probability , Volume 54 , Issue 1 , March 2017 , pp. 165 - 180
Copyright
Copyright © Applied Probability Trust 2017 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1] Aldous, D. J. (1981).Representations for partially exchangeable arrays of random variables.J. Multivariate Anal. 11,581–598.CrossRefGoogle Scholar
[2] Aristoff, D. and Radin, C. (2013).Emergent structures in large networks.J. Appl. Prob. 50,883–888.CrossRefGoogle Scholar
[3] Bollobás, B. (2001).Random Graphs, 2nd edn. (Camb. Stud. Adv. Math. 73).Cambridge University Press.CrossRefGoogle Scholar
[4] Borgs, C., Chayes, J. T., Cohn, H. and Zhao, Y. (2014).An L p theory of sparse graph convergence I. Limits, sparse random graph models, and power law distributions. Preprint. Available at https://arxiv.org/pdf/1401.2906./pdf.Google Scholar
[5] Borgs, C. et al. (2006).Counting graph homomorphism. In Topics in Discrete Mathematics (Algorithms Combin. 26).Springer,Berlin, pp.315–371.CrossRefGoogle Scholar
[6] Borgs, C. et al. (2008).Convergent sequences of dense graphs I: subgraph frequencies, metric properties and testing.Adv. Math. 219,1801–1851.CrossRefGoogle Scholar
[7] Borgs, C. et al. (2012).Convergent sequences of dense graphs II. Multiway cuts and statistical physics.Ann. Math. 176,151–219.CrossRefGoogle Scholar
[8] Chaterjee, S. and Diaconis, P. (2013).Estimating and understanding exponential random graph models.Ann. Statist. 41,2428–2461.CrossRefGoogle Scholar
[9] Chaterjee, S., Diaconis, P. and Sly, A. (2011).Random graphs with a given degree sequence.Ann. Appl. Prob. 21,1400–1435.CrossRefGoogle Scholar
[10] Chaterjee, S. and Varadham, S. R. S. (2011).The large deviation principle for the Erdős-Rényi random graph.Europ. J. Combinatronics 32,1000–1017.CrossRefGoogle Scholar
[11] Frank, O. and Strauss, D. (1986).Markov graphs.J. Amer. Statist. Assoc. 81,832–842.CrossRefGoogle Scholar
[12] Häggström, O. and Jonasson, J. (1999).Phase transition in the random triangle model.J. Appl. Prob. 36,1101–1115.CrossRefGoogle Scholar
[13] Hoover, D. (1982).Row-column exchangeability and a generalized model for probability. In Exchangeability in Probability and Statistics, eds G. Koch and F. Spizzichino.North-Holland,Amsterdam, pp.281–291.Google Scholar
[14] Lovász, L. (2012). Large Networks and Graph Limits.American Mathematical Society,Providence.CrossRefGoogle Scholar
[15] Lovász, L. and Szegedy, B. (2006).Limits of dense graph sequences.J. Combinatorial Theory B 96,933–957.CrossRefGoogle Scholar
[16] Lubetzky, E. and Zhao, Y. (2016).On the variational problem for upper tails in sparse random graphs. To appear inStructures Algorithms. Available at http://arxiv.org/abs/1402.6011.Google Scholar
[17] Newman, M. (2010).Networks.Oxford University Press.CrossRefGoogle Scholar
[18] Radin, C. and Sadun, L. (2013).Phase transitions in a complex network.J. Phys. A 46, 305002.CrossRefGoogle Scholar
[19] Radin, C. and Sadun, L. (2013).Singularities in the entropy of asymptotically large simple graphs.J. Statist. Phys. 158,853–865.CrossRefGoogle Scholar
[20] Radin, C. and Yin, M. (2013).Phase transitions in exponential random graphs.Ann. Appl. Prob. 23,2458–2471.CrossRefGoogle Scholar
[21] Radin, C., Ren, K. and Sadun, L. (2014).The asymptotics of large constrained graphs.J. Phys. A 47, 175001.CrossRefGoogle Scholar
[22] Razborov, A. (2008).On the minimal density of triangles in graphs.Combin. Prob. Comput. 17,603–618.CrossRefGoogle Scholar
[23] Touchette, H., Ellis, R. S. and Turkington, B. (2004).An introduction to the thermodynamic and macrostate levels of nonequivalent ensembles.Physica A 340,138–146.CrossRefGoogle Scholar
[24] Van der Hofstad, R. (2014).Random Graphs and Complex Networks.Cambridge University Press.Google Scholar
[25] Wasserman, S. and Faust, K. (2010). Social Network Analysis.Cambridge University Press.Google Scholar
[26] Yin, M. (2013).Critical phenomena in exponential random graphs.J. Statist. Phys. 153,1008–1021.CrossRefGoogle Scholar
[27] Yin, M., Rinaldo, A. and Fadnavis, S. (2013).Asymptotic quantization of exponential random graphs.Ann. Appl. Prob. 26,3251–3285.Google Scholar