Uniform generation of temporal graphs with given degrees
- Uniform sampling from the set G(d) of graphs with a given degree-sequence d=(d1,…,dn)∈Nn is a classical problem in the study of random graphs. We consider an analogue for temporal graphs in which the edges are labeled with integer timestamps. The input to this generation problem is a tuple D=(d,T)∈Nn×N>0 and the task is to output a uniform random sample from the set G(D) of temporal graphs with degree-sequence d and timestamps in the interval [1,T]. By allowing repeated edges with distinct timestamps, G(D) can be non-empty even if G(d) is, and as a consequence, existing algorithms are difficult to apply. We describe an algorithm for this generation problem which runs in expected time O(M) if Δ2+ϵ=O(M) for some constant ϵ>0 and T−Δ=Ω(T) where M=∑idi and Δ=maxidi. Our algorithm applies the switching method of McKay and Wormald [1] to temporal graphs: we first generate a random temporal multigraph and then remove self-loops and duplicated edges with switching operations which rewire the edges in a degree-preserving manner.
