Switch chain mixing times through triangle counts

arXiv1711.06137MaRDI QIDQ6294053FDOQ6294053

Authors: Tom Bannink, Remco van der Hofstad, Clara Stegehuis 

Publication date: 16 November 2017

Abstract: Sampling uniform simple graphs with power-law degree distributions with degree exponent $auin(2,3)$ is a non-trivial problem. We propose a method to sample uniform simple graphs that uses a constrained version of the configuration model together with a Markov Chain switching method. We test the convergence of this algorithm numerically in the context of the presence of small subgraphs. We then compare the number of triangles in uniform random graphs with the number of triangles in the erased configuration model. Using simulations and heuristic arguments, we conjecture that the number of triangles in the erased configuration model is larger than the number of triangles in the uniform random graph, provided that the graph is sufficiently large.

This page was built for publication: Switch chain mixing times through triangle counts

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