The birth of geometry in exponential random graphs. (English) Zbl 1520.05085
Summary: Inspired by the prospect of having discretized spaces emerge from random graphs, we construct a collection of simple and explicit exponential random graph models that enjoy, in an appropriate parameter regime, a roughly constant vertex degree and form very large numbers of simple polygons (triangles or squares). The models avoid the collapse phenomena that plague naive graph Hamiltonians based on triangle or square counts. More than that, statistically significant numbers of other geometric primitives (small pieces of regular lattices, cubes) emerge in our ensemble, even though they are not in any way explicitly pre-programmed into the formulation of the graph Hamiltonian, which only depends on properties of paths of length 2. While much of our motivation comes from hopes to construct a graph-based theory of random geometry (Euclidean quantum gravity), our presentation is completely self-contained within the context of exponential random graph theory, and the range of potential applications is considerably more broad.
MSC:
| 05C80 | Random graphs (graph-theoretic aspects) |
Keywords:
random geometry; triangulations; graph transitivity; Boltzmann-Gibbs ensemble; graph diameterSoftware:
GephiReferences:
| [1] | Surya, S., The causal set approach to quantum gravity, Living Rev. Relativ., 22, 5 (2019) · Zbl 1442.83029 · doi:10.1007/s41114-019-0023-1 |
| [2] | Wolfram, S., A New Kind of Science (2002), Champaign, IL: Wolfram Media, Champaign, IL · Zbl 1022.68084 |
| [3] | Wolfram, S., A class of models with the potential to represent fundamental physics, Complex Syst., 29, 107 (2020) · doi:10.25088/complexsystems.29.1.2 |
| [4] | Ambjørn, J.; Durhuus, B.; Jonsson, T., Quantum Geometry: A Statistical Field Theory Approach (2008), Cambridge: Cambridge University Press, Cambridge |
| [5] | Ambjørn, J.; Görlich, A.; Jurkiewicz, J.; Loll, R., Nonperturbative quantum gravity, Phys. Rep., 519, 127 (2012) · doi:10.1016/j.physrep.2012.03.007 |
| [6] | Dartois, S.; Gurau, R.; Rivasseau, V., Double scaling in tensor models with a quartic interaction, J. High Energy Phys. (2013) · Zbl 1342.83079 · doi:10.1007/jhep09(2013)088 |
| [7] | Trugenberger, C. A., Combinatorial quantum gravity: geometry from random bits, J. High Energy Phys. (2017) · Zbl 1382.83046 · doi:10.1007/jhep09(2017)045 |
| [8] | Kelly, C.; Trugenberger, C. A., Combinatorial quantum gravity: emergence of geometric space from random graphs, J. Phys.: Conf. Ser., 1275 (2019) · doi:10.1088/1742-6596/1275/1/012016 |
| [9] | Kelly, C.; Trugenberger, C. A.; Biancalana, F.; Kelly, C.; Trugenberger, C. A.; Biancalana, F., Self-assembly of geometric space from random graphs. Convergence of combinatorial gravity, Class. Quantum Grav., 36 (2021) · Zbl 1503.83005 · doi:10.1088/1361-6382/ab1c7d |
| [10] | Trugenberger, C. A.; Trugenberger, C. A., Quantum gravity as an information network: self-organization of a 4D universe. Random holographic ‘large worlds’ with emergent dimensions, Phys. Rev. D. Phys. Rev. E, 94 (2016) · doi:10.1103/physreve.94.052305 |
| [11] | Newman, M., Networks: An Introduction (2010), Oxford: Oxford University Press, Oxford · Zbl 1195.94003 |
| [12] | Coolen, T.; Annibale, A.; Roberts, E., Generating Random Networks and Graphs (2017), Oxford: Oxford University Press, Oxford · Zbl 1365.05003 |
| [13] | Jaynes, E. T., On the rationale of maximum-entropy methods, Proc. IEEE, 70, 939 (1982) · doi:10.1109/proc.1982.12425 |
| [14] | Strauss, D., On a general class of models for interaction, SIAM Rev., 28, 513 (1986) · Zbl 0612.60066 · doi:10.1137/1028156 |
| [15] | Bizhani, G.; Paczuski, M.; Grassberger, P., Discontinuous percolation transitions in epidemic processes, surface depinning in random media, and Hamiltonian random graphs, Phys. Rev. E, 86 (2012) · doi:10.1103/physreve.86.011128 |
| [16] | Krioukov, D., Clustering implies geometry in networks, Phys. Rev. Lett., 116 (2016) · doi:10.1103/physrevlett.116.208302 |
| [17] | Snijders, T. A B.; Pattison, P. E.; Robins, G. L.; Handcock, M. S., New specifications for exponential random graph models, Socio. Methodol., 36, 99 (2006) · doi:10.1111/j.1467-9531.2006.00176.x |
| [18] | Burda, Z.; Jurkiewicz, J.; Krzywicki, A., Network transitivity and matrix models, Phys. Rev. E, 69 (2004) · doi:10.1103/physreve.69.026106 |
| [19] | Park, J.; Newman, M. E J., Solution of the two-star model of a network, Phys. Rev. E, 70 (2004) · doi:10.1103/physreve.70.066146 |
| [20] | Park, J.; Newman, M. E J., Solution for the properties of a clustered network, Phys. Rev. E, 72 (2005) · doi:10.1103/physreve.72.026136 |
| [21] | Annibale, A.; Courtney, O. T., The two-star model: exact solution in the sparse regime and condensation transition, J. Phys. A: Math. Theor., 48 (2015) · Zbl 1329.82040 · doi:10.1088/1751-8113/48/36/365001 |
| [22] | Gorsky, A.; Valba, O.; Gorsky, A.; Valba, O., Finite-size effects in exponential random graphs. Interacting thermofield doubles and critical behavior in random regular graphs, J. Compl. Net.. Phys. Rev. D, 103 (2021) · doi:10.1103/physrevd.103.106013 |
| [23] | Bolfe, M.; Metz, F. L.; Guzmán-González, E.; Pérez Castillo, I., Analytic solution of the two-star model with correlated degrees (2021) |
| [24] | Chatterjee, S.; Diaconis, P., Estimating and understanding exponential random graph models, Ann. Stat., 41, 2428 (2013) · Zbl 1293.62046 · doi:10.1214/13-aos1155 |
| [25] | Radin, C.; Yin, M., Phase transitions in exponential random graphs, Ann. App. Prob., 23, 2458 (2013) · Zbl 1278.05225 · doi:10.1214/12-aap907 |
| [26] | Radin, C.; Sadun, L., Phase transitions in a complex network, J. Phys. A: Math. Theor., 46 (2013) · Zbl 1314.82011 · doi:10.1088/1751-8113/46/30/305002 |
| [27] | Robins, G.; Pattison, P.; Kalish, Y.; Lusher, D., An introduction to exponential random graph (p^*) models for social networks, Soc. Network., 29, 173 (2007) · doi:10.1016/j.socnet.2006.08.002 |
| [28] | Harary, F.; Manvel, B., On the number of cycles in a graph, Mat. Čas. Sloven. Akad. Vied, 21, 55 (1971) · Zbl 0209.55404 |
| [29] | Weisstein, E. W., Graph cycle at MathWorld (2021) |
| [30] | Snijders, T. A B., Markov chain Monte Carlo estimation of exponential random graph models, J. Soc. Struct., 3, 2 (2002) |
| [31] | Neeman, J.; Radin, C.; Sadun, L., Phase transitions in finite random networks, J. Stat. Phys., 181, 305 (2020) · Zbl 1454.82013 · doi:10.1007/s10955-020-02582-4 |
| [32] | Ambjørn, J.; Jurkiewicz, J.; Loll, R., Emergence of a 4D world from causal quantum gravity, Phys. Rev. Lett., 93 (2004) · Zbl 1246.83059 · doi:10.1103/physrevlett.93.131301 |
| [33] | Glaser, L.; Steinhaus, S., Quantum gravity on the computer: impressions of a workshop, Universe, 5, 35 (2019) · doi:10.3390/universe5010035 |
| [34] | Durhuus, B., Hausdorff and spectral dimension of infinite random graphs, Acta Phys. Pol. B, 40, 3509 (2009) · Zbl 1371.05262 |
| [35] | Ollivier, Y., Ricci curvature of Markov chains on metric spaces, J. Funct. Anal., 256, 810 (2009) · Zbl 1181.53015 · doi:10.1016/j.jfa.2008.11.001 |
| [36] | Lin, Y.; Lu, L.; Yau, S-T, Ricci curvature of graphs, Tohoku Math. J., 63, 605 (2011) · Zbl 1237.05204 · doi:10.2748/tmj/1325886283 |
| [37] | Cushing, D.; Kamtue, S., Long-scale Ollivier Ricci curvature of graphs, Anal. Geometry Metr. Spaces, 7, 22 (2019) · Zbl 1415.05036 · doi:10.1515/agms-2019-0003 |
| [38] | van der Hoorn, P.; Cunningham, W. J.; Lippner, G.; Trugenberger, C.; Krioukov, D., Ollivier-Ricci curvature convergence in random geometric graphs (2020) |
| [39] | van der Hoorn, P.; Lippner, G.; Trugenberger, C.; Krioukov, D., Ollivier curvature of random geometric graphs converges to Ricci curvature of their Riemannian manifolds (2020) |
| [40] | Tee, P.; Trugenberger, C. A., Enhanced Forman curvature and its relation to Ollivier curvature (2021) |
| [41] | Łuczak, T., Random trees and random graphs, Random Struct. Algorithm, 13, 485 (1998) · Zbl 0959.05111 · doi:10.1002/(sici)1098-2418(199810/12)13:3/4<485::aid-rsa16>3.0.co;2-y |
| [42] | Hartmann, A. K.; Mézard, M., Distribution of diameters for Erdős-Rényi random graphs, Phys. Rev. E, 97 (2018) · doi:10.1103/physreve.97.032128 |
| [43] | Katzav, E.; Nitzan, M.; ben-Avraham, D.; Krapivsky, P. L.; Kühn, R.; Ross, N.; Biham, O., Analytical results for the distribution of shortest path lengths in random networks, Europhys. Lett., 111 (2015) · doi:10.1209/0295-5075/111/26006 |
| [44] | Nitzan, M.; Katzav, E.; Kühn, R.; Biham, O., Distance distribution in configuration model networks, Phys. Rev. E, 93 (2016) · doi:10.1103/physreve.93.062309 |
| [45] | Katzav, E.; Biham, O.; Hartmann, A. K., The distribution of shortest path lengths in subcritical Erdős-Rényi networks, Phys. Rev. E, 98 (2018) · doi:10.1103/physreve.98.012301 |
| [46] | Chung, F. R K., Spectral Graph Theory (1997), Providence, RI: American Mathematical Society, Providence, RI · Zbl 0867.05046 |
| [47] | Seidel, R., On the all-pairs-shortest-path problem in unweighted undirected graphs, J. Comput. Syst. Sci., 51, 400 (1995) · Zbl 1295.05240 · doi:10.1006/jcss.1995.1078 |
| [48] | Bollobás, B.; Fernandez de la Vega, W., The diameter of random regular graphs, Combinatorica, 2, 125 (1982) · Zbl 0505.05053 · doi:10.1007/bf02579310 |
| [49] | Bastian, M.; Heymann, S.; Jacomy, M., Gephi: an open source software for exploring and manipulating networks (2009) |
| [50] | Chen, S.; Plotkin, S. S., Statistical mechanics of graph models and their implications for emergent spacetime manifolds, Phys. Rev. D, 87 (2013) · doi:10.1103/physrevd.87.084011 |
| [51] | Lovász, L., Large Networks and Graph Limits (2012), Providence, RI: American Mathematical Society, Providence, RI · Zbl 1292.05001 |
| [52] | Radin, C.; Sadun, L., Singularities in the entropy of asymptotically large simple graphs, J. Stat. Phys., 158, 853 (2015) · Zbl 1320.05064 · doi:10.1007/s10955-014-1151-3 |
| [53] | Radin, C.; Ren, K.; Sadun, L., The asymptotics of large constrained graphs, J. Phys. A: Math. Theor., 47 (2014) · Zbl 1290.05139 · doi:10.1088/1751-8113/47/17/175001 |
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.
