×
den Hollander, F.; Mandjes, M.; Roccaverde, A.; Starreveld, N. J.

Ensemble equivalence for dense graphs. (English) Zbl 1387.05240

Electron. J. Probab. 23, Paper No. 12, 26 p. (2018).
Summary: In this paper we consider a random graph on which topological restrictions are imposed, such as constraints on the total number of edges, wedges, and triangles. We work in the dense regime, in which the number of edges per vertex scales proportionally to the number of vertices \(n\). Our goal is to compare the micro-canonical ensemble (in which the constraints are satisfied for every realisation of the graph) with the canonical ensemble (in which the constraints are satisfied on average), both subject to maximal entropy. We compute the relative entropy of the two ensembles in the limit as \(n\) grows large, where two ensembles are said to be equivalent in the dense regime if this relative entropy divided by \(n^2\) tends to zero. Our main result, whose proof relies on large deviation theory for graphons, is that breaking of ensemble equivalence occurs when the constraints are frustrated. Examples are provided for three different choices of constraints.

Cited in 10 Documents

MSC:

05C80 Random graphs (graph-theoretic aspects)
05C42 Density (toughness, etc.)
60K35 Interacting random processes; statistical mechanics type models; percolation theory
82B20 Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics

Keywords:

random graph; canonical ensemble; microcanonical ensemble; constraint; ensemble equivalence; relative entropy; graphon; variational representation
Cite Review PDF
Full Text: DOI arXiv Euclid

References:

[1] D. Aristoff and L. Zhu, On the phase transition curve in a directed exponential random graph model, arXiv:1404.6514. · Zbl 1327.05299
[2] J.W. Gibbs, Elementary Principles of Statistical Mechanics, Yale University Press, New Haven, Connecticut, 1902. · Zbl 1230.05259
[3] R. van der Hofstad, Random Graphs and Complex Networks, Volume I, Cambridge University Press, Cambridge, 2017. · Zbl 1238.60011
[4] H. Touchette, General equivalence and nonequivalence of ensembles: Thermodynamic, macrostate, and measure levels, J. Stat. Phys. 159 (2015) 987-1016. · Zbl 1213.05161 · doi:10.1007/s10955-015-1212-2
[5] H. Touchette, General equivalence and nonequivalence of ensembles: Thermodynamic, macrostate, and measure levels, J. Stat. Phys. 159 (2015) 987-1016. · Zbl 1247.05124 · doi:10.1007/s10955-015-1212-2
[6] S. Chatterjee, An introduction to large deviations for random graphs, Bull. Amer. Math. Soc. 53 (2016) 617-642. · Zbl 1356.60044 · doi:10.1090/bull/1539
[7] S. Chatterjee, Large deviations for Random Graphs, École d’ Été de Probabilités de Saint-Flour XLV, Springer Lecture Notes in Mathematics, 2015. · Zbl 1375.60009
[8] S. Chatterjee and A. Dembo, Non linear large deviations, Adv. Math. 299 (2016) 396-450. · Zbl 1356.60045 · doi:10.1016/j.aim.2016.05.017
[9] S. Chatterjee and P. Diaconis, Estimating and understanding exponential random graph models, Ann. Stat. 41 (2013) 2428-2461. · Zbl 1293.62046 · doi:10.1214/13-AOS1155
[10] S. Chatterjee, P. Diaconis and A. Sly, Random graphs with a given degree sequence, Ann. Appl. Probab. 21 (2011) 1400-1435. · Zbl 1234.05206 · doi:10.1214/10-AAP728
[11] S. Chatterjee and S.R.S. Varadhan, The large deviation principle for the Erdős-Rényi random graph, European J. Comb. 32 (2011) 1000-1017. · Zbl 1230.05259 · doi:10.1016/j.ejc.2011.03.014
[12] P. Diao, D. Guillot, A. Khare and B. Rajaratnam, Differential calculus on graphon space, J. Combin. Theory Ser. A 133 (2015) 183-227. · Zbl 1315.05081 · doi:10.1016/j.jcta.2015.02.006
[13] P. Erdős, D.J. Kleitman and B.L. Rothschild, Asymptotic enumeration of \(K_n\)-free graphs, Colloquio Internationale sulle Teorie Combinatorie, 1973, Rome. · Zbl 0358.05027
[14] J.W. Gibbs, Elementary Principles of Statistical Mechanics, Yale University Press, New Haven, Connecticut, 1902. · JFM 33.0708.01
[15] G. Garlaschelli, F. den Hollander and A. Roccaverde, Ensemble equivalence in random graphs with modular structure, J. Phys. A: Math. Theor. 50 (2017). · Zbl 1358.82014 · doi:10.1088/1751-8113/50/1/015001
[16] R. van der Hofstad, Random Graphs and Complex Networks, Volume I, Cambridge University Press, Cambridge, 2017. · Zbl 1361.05002
[17] E.T. Jaynes, Information theory and statistical mechanics, Phys. Rev. 106 (1957) 620-630. · Zbl 0084.43701 · doi:10.1103/PhysRev.106.620
[18] R. Kenyon, C. Radin, K. Ren and L. Sadun, Multipodal structure of phase transitions in large constrained graphs, J. Stat. Phys. 168 (2017) 233-258. · Zbl 1376.82029 · doi:10.1007/s10955-017-1804-0
[19] R. Kenyon and M. Yin, On the asymptotics of constrained exponential random graphs, J. Appl. Prob. 54 (2017) 165-180. · Zbl 1396.05101
[20] L. Lovász and B. Szegedy, Limits of dense graph sequences, J. Combin. Theory Ser. B 96 (2006) 933-957. · Zbl 1113.05092 · doi:10.1016/j.jctb.2006.05.002
[21] E. Lubetzky and Y. Zhao, On replica symmetry of large deviations in random graphs, Random Structures and Algorithms 47 (2015) 109-146. · Zbl 1348.05195 · doi:10.1002/rsa.20536
[22] J. Park and M.E.J. Newman, Statistical mechanics of networks, Phys. Rev. E 70 (2014) 066117.
[23] C. Radin and L. Sadun, Phase transitions in a complex network, J. Phys. A: Math. Theor. 46 (2013) 305002. · Zbl 1314.82011 · doi:10.1088/1751-8113/46/30/305002
[24] C. Radin and L. Sadun, Singularities in the entropy of asymptotically large simple graphs, J. Stat. Phys. 158 (2015) 853-865. · Zbl 1320.05064 · doi:10.1007/s10955-014-1151-3
[25] C. Radin and M. Yin, Phase transitions in exponential random graphs, Ann. Appl. Probab. 23 (2013) 2458-2471. · Zbl 1278.05225 · doi:10.1214/12-AAP907
[26] O. Pikhurko and A. Razborov, Asymptotic structure of graphs with the minimum number of triangles, Comb. Prob. Comp. 26 (2017) 138-160. · Zbl 1371.05147 · doi:10.1017/S0963548316000110
[27] T. Squartini, J. de Mol, F. den Hollander and D. Garlaschelli, Phys. Rev. Lett. 115 (2015) 268701.
[28] H. Touchette, General equivalence and nonequivalence of ensembles: Thermodynamic, macrostate, and measure levels, J. Stat. Phys. 159 (2015) 987-1016. · Zbl 1329.82050 · doi:10.1007/s10955-015-1212-2
[29] M. Yin, Critical Phenomena in Exponential Random Graphs, J. Stat. Phys. 153 (2013) 1008-1021. · Zbl 1285.82024 · doi:10.1007/s10955-013-0874-x
[30] M. Yin, Large deviations and exact asymptotics for constrained exponential random graphs, Electron. Commun. Probab. 20 (2015) 14 pp. · Zbl 1325.60029 · doi:10.1214/ECP.v20-4010
[31] M. Yin and L. Zhu, Asymptotics for sparse exponential random graph models, Braz. J. Probab. Stat. 31 (2017) 394-412. · Zbl 1365.05264 · doi:10.1214/16-BJPS319
[32] L. Zhu, Asymptotic Structure of constrained exponential random graph models, J. Stat. Phys. 166 (2017) 1464-1482. · Zbl 1372.05205 · doi:10.1007/s10955-017-1733-y
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.