TY - JOUR

T1 - Switch chain mixing times and triangle counts in simple random graphs with given degrees

AU - Bannink, Tom

AU - van der Hofstad, Remco

AU - Stegehuis, Clara

A2 - Mateos, Jose

PY - 2019/8/16

Y1 - 2019/8/16

N2 - Sampling uniform simple graphs with power-law degree distributions with degree exponent τ(2,3) is a non-trivial problem. Firstly, 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 and we estimate the mixing time to be at most O(n log2n). Secondly, we compare the number of triangles in uniform random graphs with the number of triangles in the erased configuration model where double edges and self-loops of the configuration model are removed. 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. Lastly, we argue that certain switch-chain-based proof methods can not be used in the regime τ(2,3) due to the possibility of creating many triangles with a single switch.

AB - Sampling uniform simple graphs with power-law degree distributions with degree exponent τ(2,3) is a non-trivial problem. Firstly, 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 and we estimate the mixing time to be at most O(n log2n). Secondly, we compare the number of triangles in uniform random graphs with the number of triangles in the erased configuration model where double edges and self-loops of the configuration model are removed. 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. Lastly, we argue that certain switch-chain-based proof methods can not be used in the regime τ(2,3) due to the possibility of creating many triangles with a single switch.

KW - clustering

KW - configuration model

KW - switch chain

KW - triangles

UR - http://www.scopus.com/inward/record.url?scp=85071118952&partnerID=8YFLogxK

U2 - 10.1093/comnet/cny013

DO - 10.1093/comnet/cny013

M3 - Article

AN - SCOPUS:85071118952

VL - 7

SP - 210

EP - 225

JO - Journal of Complex Networks

JF - Journal of Complex Networks

SN - 2051-1310

IS - 2

ER -