Triangle switches, reconstruction and mixing

Abstract

In a uniformly random graph with a given degree sequence, if the maximum degree is constant then the number of triangles in the graph is asymptotically Poisson with constant mean. In particular, this implies that a uniformly random graph is not well-suited as a model for a network which contains many triangles, such as a social network.

The switch chain is a well-studied Markov chain on the set of all graphs with given degrees, with a uniform stationary distribution. I will discuss variations of the switch chain, called triangle switch chains, which only perform switches that change the set of triangles in the graph. We have proved that triangle switches connect the state space of graphs with a given degree sequence, whenever the minimum degree is at least 3.  We have also studied the mixing rate of a Metropolis implementation of the switch chain, in which a graph $G$ has stationary distribution proportional to $\lambda^{t(G)}$ for some $\lambda > 1$, where $t(G)$ is the number of triangles in $G$. Such a chain could be used to sample graphs with many more triangles than expected in a uniformly random graph with the same degree sequence. We have proved that this Metropolis triangle switch chain is rapidly mixing whenever the corresponding switch chain is rapidly mixing, so long as $\lambda$ and the maximum degree of the chain are not too large.

Joint work with Colin Cooper and Martin Dyer.