TY  - INPR
A1  - Allendorf, Daniel
T1  - Uniform generation of temporal graphs with given degrees
T2  - arXiv
N2  - 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.
KW  - Random Graph
KW  - Temporal Graph
KW  - Uniform Sampling
KW  - Degree Sequence
KW  - Switching Algorithm
Y1  - 2023
UR  - http://publikationen.ub.uni-frankfurt.de/frontdoor/index/index/docId/86124
UR  - https://nbn-resolving.org/urn:nbn:de:hebis:30:3-861240
UR  - https://arxiv.org/abs/2304.09654v2
IS  - 2304.09654v2
PB  - arXiv
ER  -