×

Mixing time of vertex-weighted exponential random graphs. (English) Zbl 1416.05257

Summary: Exponential random graph models have become increasingly important in the study of modern networks ranging from social networks, economic networks, to biological networks. They seek to capture a wide variety of common network tendencies such as connectivity and reciprocity through local graph properties. Sampling from these exponential distributions is crucial for parameter estimation, hypothesis testing, as well as understanding the features of the network in question. We inspect the efficiency of a popular sampling technique, the Glauber dynamics, for vertex-weighted exponential random graphs. Letting \(n\) be the number of vertices in the graph, we identify a region in the parameter space where the mixing time for the Glauber dynamics is \(\Theta(n \log n)\) (the high-temperature phase) and a complementary region where the mixing time is exponentially slow of order \(e^{\Omega(n)}\) (the low-temperature phase). Lastly, we give evidence that along a critical curve in the parameter space the mixing time is \(O(n^{2 / 3})\).

MSC:

05C80 Random graphs (graph-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Bollobás, B., Random Graphs (1985), Academic Press: Academic Press New York · Zbl 0567.05042
[2] Durrett, R., Random Graph Dynamics (2007), Cambridge University Press: Cambridge University Press New York · Zbl 1116.05001
[3] R. van der Hofstad, Random Graphs and Complex Networks. http://www.win.tue.nl/ rhofstad/NotesRGCN.pdf; R. van der Hofstad, Random Graphs and Complex Networks. http://www.win.tue.nl/ rhofstad/NotesRGCN.pdf · Zbl 1361.05002
[4] Newman, M., Networks: An Introduction (2010), Oxford University Press: Oxford University Press New York
[5] Cranmer, S. J.; Desmarais, B. A., Inferential network analysis with exponential random graph models, Pol. Anal., 19, 66-86 (2011)
[6] Krioukov, D., Clustering implies geometry in networks, Phys. Rev. Lett., 116, 208302 (2016)
[7] A.D. Barbour, A. Röllin, Central limit theorems in the configuration model. arXiv:1710.02644; A.D. Barbour, A. Röllin, Central limit theorems in the configuration model. arXiv:1710.02644
[8] van Enter, A. C.D.; Fernández, R.; den Hollander, F.; Redig, F., Possible loss and recovery of Gibbsianness during the stochastic evolution of Gibbs measures, Comm. Math. Phys., 226, 101-130 (2002) · Zbl 0990.82018
[9] Bhamidi, S.; Bresler, G.; Sly, A., Mixing time of exponential random graphs, Ann. Appl. Probab., 21, 2146-2170 (2011) · Zbl 1238.60011
[10] Chatterjee, S.; Diaconis, P., Estimating and understanding exponential random graph models, Ann. Statist., 41, 2428-2461 (2013) · Zbl 1293.62046
[11] D. Aldous, J. Fill, Reversible Markov Chains and Random Walks on Graphs. http://www.stat.berkeley.edu/ aldous/RWG/book.html; D. Aldous, J. Fill, Reversible Markov Chains and Random Walks on Graphs. http://www.stat.berkeley.edu/ aldous/RWG/book.html
[12] Levin, D. A.; Peres, Y.; Wilmer, E. L., Markov Chains and Mixing Times (2008), American Mathematical Society: American Mathematical Society Providence
[13] R. Bubley, M. Dyer, Path coupling: A technique for proving rapid mixing in Markov chains, in: FOCS, 1997, pp. 223-231.; R. Bubley, M. Dyer, Path coupling: A technique for proving rapid mixing in Markov chains, in: FOCS, 1997, pp. 223-231.
[14] Griffiths, R. B.; Weng, C.-Y.; Langer, J. S., Relaxation times for metastable states in the mean-field model of a ferromagnet, Phys. Rev., 149, 301-305 (1966)
[15] Yin, M., Critical phenomena in exponential random graphs, J. Stat. Phys., 153, 1008-1021 (2013) · Zbl 1285.82024
[16] Levin, D. A.; Luczak, M. J.; Peres, Y., Glauber dynamics for the mean-field Ising model: Cut-off, critical power law, and metastability, Probab. Theory Related Fields, 146, 223-265 (2010) · Zbl 1187.82076
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.