Mixing time of vertex-weighted exponential random graphs

[摘要] 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)). (C) 2018 Elsevier B.V. All rights reserved.

[发布日期] 2019-12-15

[效力级别]  Proceedings Paper

[关键词] Exponential random graphs;Mixing time;Glauber dynamics