Mixing time of vertex-weighted exponential random graphs

DOI10.1016/J.CAM.2018.07.038MaRDI QIDQ2315898zbMATH OpenOpenAlexWikidataFDO

Authors Ryan DeMuse, Terry Easlick, Mei Yin

Publication date 26 July 2019

Published in Journal of Computational and Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1712.07568

zbMATH Keywords

exponential random graphsGlauber dynamicsmixing time

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80)

Abstract: 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(nlogn)$ (the high temperature phase) and a complement region where the mixing time is exponentially slow on the order of $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})$.

Recommendations

• Mixing time of exponential random graphs
• A note on perfect simulation for exponential random graph models
• Perspectives on exponential random graphs
• Rapid mixing of Gibbs sampling on graphs that are sparse on average
• Critical phenomena in exponential random graphs

Cites work

• Critical phenomena in exponential random graphs
• Estimating and understanding exponential random graph models
• Glauber dynamics for the mean-field Ising model: cut-off, critical power law, and metastability
• scientific article; zbMATH DE number 3904630 (Why is no real title available?)
• Mixing time of exponential random graphs
• Networks. An introduction.
• Possible loss and recovery of Gibbsianness during the stochastic evolution of Gibbs measures
• Random graph dynamics
• Random graphs and complex networks. Volume 1

Cited in

(10)

• Dimension reduction in vertex-weighted exponential random graphs
• Logarithmic Sobolev inequalities for finite spin systems and applications
• Perspectives on exponential random graphs
• Mixing time of PageRank surfers on sparse random digraphs
• On the time to identify the nodes in a random graph
• Metastable mixing of Markov chains: efficiently sampling low temperature exponential random graphs
• Sub-critical exponential random graphs: concentration of measure and some applications
• Mixing time of exponential random graphs
• Concentration via metastable mixing, with applications to the supercritical exponential random graph model
• Mixing phases and metastability for the Glauber dynamics on the p-spin Curie-Weiss model

This page was built for publication: Mixing time of vertex-weighted exponential random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2315898)