Hostname: page-component-cd9895bd7-jkksz Total loading time: 0 Render date: 2024-12-28T15:02:58.390Z Has data issue: false hasContentIssue false
  • English
  • Français

On the phase transition curve in a directed exponential random graph model

Part of: Equilibrium statistical mechanics Graph theory

Published online by Cambridge University Press:  20 March 2018

David Aristoff  and
Lingjiong Zhu
David Aristoff*
Affiliation:
Colorado State University
Lingjiong Zhu*
Affiliation:
Florida State University
*
* Postal address: Department of Mathematics, Colorado State University, 1874 Campus Delivery, Fort Collins, CO-80523, USA. Email address: [email protected]
** Postal address: Department of Mathematics, Florida State University, 1017 Academic Way, Tallahassee, FL-32306, USA. Email address: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We consider a family of directed exponential random graph models parametrized by edges and outward stars. Much of the important statistical content of such models is given by the normalization constant of the models, and, in particular, an appropriately scaled limit of the normalization, which is called the free energy. We derive precise asymptotics for the normalization constant for finite graphs. We use this to derive a formula for the free energy. The limit is analytic everywhere except along a curve corresponding to a first-order phase transition. We examine unusual behavior of the model along the phase transition curve.

Keywords

Dense random graphexponential random graphgraph limitentropyphase transition

MSC classification

Primary: 05C80: Random graphs 82B26: Phase transitions (general)
Type
Original Article
Information
Advances in Applied Probability , Volume 50 , Issue 1 , March 2018 , pp. 272 - 301
Copyright
Copyright © Applied Probability Trust 2018 

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] Aristoff, D. and Radin, C. (2013). Emergent structures in large networks. J. Appl. Prob. 50, 883–888. Google Scholar
[2] Aristoff, D. and Zhu, L. (2015). Asymptotic structure and singularities in constrained directed graphs. Stoch. Process. Appl. 125, 4154–4177. Google Scholar
[3] Badev, A. (2013). Discrete games in endogenous networks: theory and policy. Working paper. University of Pennsylvania. Google Scholar
[4] Besag, J. (1975). Statistical analysis of non-lattice data. J. R. Statist. Soc. D 24, 179–195. Google Scholar
[5] Chandrasekhar, A. G. and Jackson, M. O. (2014). Tractable and consistent random graph models. Preprint. Available at https://arxiv.org/abs/1210.7375. Google Scholar
[6] Chatterjee, S. and Diaconis, P. (2013). Estimating and understanding exponential random graph models. Ann. Statist. 41, 2428–2461. Google Scholar
[7] Chatterjee, S. and Varadhan, S. R. S. (2011). The large deviation principle for the Erdős–Rényi random graph. Europ. J. Combin. 32, 1000–1017. Google Scholar
[8] Cheng, J., Romero, D. M., Meeder, B. and Kleinberg, J. (2011). Predicting reciprocity in social networks. In Proc. IEEE Third International Conference on Social Computing, IEEE, pp. 49–56. Google Scholar
[9] Fienberg, S. E. (2010). Introduction to papers on the modeling and analysis of network data. Ann. Appl. Statist. 4, 1–4. Google Scholar
[10] Fienberg, S. E. (2010). Introduction to papers on the modeling and analysis of network data–II. Ann. Appl. Statist. 4, 533–534. Google Scholar
[11] Fisher, M. E. and Radin, C. (2006). Definition of thermodynamic phases and phase transitions. In Proc. Phase Transitions. Available at http://www.aimath.org/pastworkshops/phasetransition.html. Google Scholar
[12] Gallavotti, G. (1999). Statistical Mechanics: A Short Treatise. Springer, Berlin. Google Scholar
[13] Häggström, O. and Jonasson, J. (1999). Phase transition in the random triangle model. J. Appl. Prob. 36, 1101–1115. Google Scholar
[14] Holland, P. W. and Leinhardt, S. (1981). An exponential family of probability distributions for directed graphs. J. Amer. Statist. Assoc. 76, 33–65. Google Scholar
[15] Lebowitz, J. L., Mazel, A. E. and Presutti, E. (1998). Rigorous proof of a liquid-vapor phase transition in a continuum particle system. Phys. Rev. Lett. 80, 4701–4704. Google Scholar
[16] Lovász, L. (2009). Very large graphs. In Current Developments in Mathematics, 2008, International Press, Somerville, MA, pp. 67–128. Google Scholar
[17] Mele, A. (2017). A structural model of dense network formation. Econometrica 85, 825–850. Google Scholar
[18] Mele, A. and Zhu, L. (2017). Approximate variational estimation for a model of network formation. Preprint. Available at https://arxiv.org/abs/1702.00308. Google Scholar
[19] Newman, M. E. J. (2010). Networks: An Introduction. Oxford University Press. Google Scholar
[20] Newman, M. E. J., Forrest, S. and Balthrop, J. (2002). Email networks and the spread of computer viruses. Phys. Rev. E 66, 035101. CrossRefGoogle ScholarPubMed
[21] Park, J. and Newman, M. E. J. (2004). Solution of the two-star model of a network. Phys. Rev. E 70, 066146. CrossRefGoogle ScholarPubMed
[22] Park, J. and Newman, M. E. J. (2005). Solution for the properties of a clustered network. Phys. Rev. E 72, 026136. Google Scholar
[23] Radin, C. and Yin, M. (2013). Phase transitions in exponential random graphs. Ann. Appl. Prob. 23, 2458–2471. Google Scholar
[24] Rinaldo, A., Fienberg, S. and Zhou, Y. (2009). On the geometry of discrete exponential families with application to exponential random graph models. Electron. J. Statist. 3, 446–484. Google Scholar
[25] Snijders, T. A. B. (2002). Markov chain Monte Carlo estimation of exponential random graph models. J. Social Structure 3, 40pp. Google Scholar
[26] Snijders, T. A. B., Pattison, P. E., Robins, G. L. and Handcock, M. S. (2006). New specifications for exponential random graph models. Sociological Methodol. 36, 99–153. Google Scholar
[27] Train, K. E. (2009). Discrete Choice Methods with Simulation, 2nd edn. Cambridge University Press. Google Scholar
[28] Wasserman, S. and Faust, K. (1994). Social Network Analysis: Methods and Applications. Cambridge University Press. CrossRefGoogle Scholar
[29] Yang, C. N. and Lee, T. D. (1952). Statistical theory of equations of state and phase transitions. I. Theory of condensation. Phys. Rev. (2) 87, 404–409. Google Scholar
[30] Yin, M. (2013). Critical phenomena in exponential random graphs. J. Statist. Phys. 153, 1008–1021. CrossRefGoogle Scholar