Goethe University Frankfurt<EMAIL_ADDRESS>frankfurt.dehttps://orcid.org/0000-0002-0549-7576 Daniel Allendorf
[500]Mathematics of computing Random graphs

# Uniform Generation of Temporal Graphs with Given Degrees

Daniel Allendorf

###### Abstract

Uniform sampling from the set $\mathcal{G}(\mathbf{d})$ of graphs with a given
degree-sequence $\mathbf{d}=(d_{1},\dots,d_{n})\in\mathbb{N}^{n}$ 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
$\mathbf{D}=(\mathbf{d},T)\in\mathbb{N}^{n}\times\mathbb{N}_{>0}$ and the task
is to output a uniform random sample from the set $\mathcal{G}(\mathbf{D})$ of
temporal graphs with degree-sequence $\mathbf{d}$ and timestamps in the
interval $[1,T]$. By allowing repeated edges with distinct timestamps,
$\mathcal{G}(\mathbf{D})$ can be non-empty even if $\mathcal{G}(\mathbf{d})$
is, and as a consequence, existing algorithms are difficult to apply.

We describe an algorithm for this generation problem which runs in expected
linear time $O(M)$ if $\Delta^{2+\epsilon}=O(M)$ for some constant
$\epsilon>0$ and $T-\Delta=\Omega(T)$ where $M=\sum_{i}d_{i}$ and
$\Delta=\max_{i}d_{i}$. 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.

###### keywords:

Random Graph, Temporal Graph, Uniform Sampling, Degree Sequence, Switching
Algorithm

##  1 Introduction

A common problem in network science is the sampling of a graph matching a
given degree-sequence. Formally, given a sequence of integers
$\mathbf{d}=(d_{1},\dots,d_{n})$, we say that a graph $G=(V,E)$ with nodes
$V=\\{v_{1},\dots,v_{n}\\}$ matches $\mathbf{d}$ if the number of incident
edges at node $v_{i}$ equals $d_{i}$ for each $1\leq i\leq n$. We then define
$\mathcal{G}(\mathbf{d})$ as the set of all simple graphs (e.g. without loops
or multi-edges) matching $\mathbf{d}$ and ask for a uniform random sample
$G\in\mathcal{G}(\mathbf{d})$. Such a sample is useful as it allows us to
construct null models for testing the influence of the degrees on other graph
properties of interest [2, 3]. In addition, this sampling problem is tightly
related to the task of estimating $|\mathcal{G}(\mathbf{d})|$ [4, 1].

_Temporal graphs_ are capable of modeling not only the topology but also the
time structure of networks (see [5] or [6] for an overview). Possibly the most
common type of temporal graph augments each edge of a classical graph with an
integer timestamp. Here, we work by the following definition.

######  Definition 1.1 (Temporal Graph).

A temporal (multi-)graph $G=(V,E)$ consists of a set of nodes
$V=\\{v_{1},\dots,v_{n}\\}$ and a (multi-)set of edges
$E=\\{e_{1},\dots,e_{m}\\}$ where each edge is a tuple
$(\\{u,v\\},t)\in\\{\\{u,v\\}:u,v\in V\\}\times\mathbb{N}_{>0}$.

In terms of semantics, the presence of an edge $(\\{u,v\\},t)$ indicates that
the nodes $u$ and $v$ are connected at time $t$. For the purpose of modeling
networks, it additionally makes sense to restrict ourselves to _simple_
temporal graphs which exclude certain types of edges. To this end, we call a
temporal graph $G=(V,E)$ _simple_ if the edge set $E$ contains no loops and no
edges between the same nodes with the same timestamp, i.e. iff $u\neq v$ for
all $(\\{u,v\\},t)\in E$ and $E$ is a set.

Given its prominence in classical graph theory, it is reasonable to assume
that parameterizing temporal graphs by the degrees can yield a similarly
useful model. For instance, the distribution of active times of nodes and
edges in real-world temporal graphs has been observed to follow a power-law
[7, 8, 5], which can be reproduced by sampling a uniform random temporal graph
with power-law degrees. Still, to the best of our knowledge, the problem of
generating such graphs has not been considered so far. In this paper, we study
algorithmic techniques of sampling simple temporal graphs uniformly at random,
and in particular, focus on the task of providing an exact uniform sample.

###  1.1 Related Work

Conditions for the realizability of a sequence of integers
$\mathbf{d}=(d_{1},\dots,d_{n})$ as a graph were given by Havel [9] and Hakimi
[10]. While the provided proofs can be used to construct a realization
$G\in\mathcal{G}(\mathbf{d})$, the resulting graph is deterministic.

A simple way to obtain a uniform random sample $G\in\mathcal{G}(\mathbf{d})$
is to use the _configuration model_ of Bender and Canfield [11] or Bollobás
[12] to sample random _multigraphs_ with sequence $\mathbf{d}$ until a simple
graph is found. Unfortunately, this simple rejection scheme is not efficient
as its run time is exponential in the largest degree $\Delta=\max_{i}d_{i}$
[13].

Efficient algorithms have been obtained by using the _switching_ method of
McKay and Wormald [1] which arose from the use of switchings for enumeration
in McKay [14]. The approach is to again start from a random multigraph but
instead of rejecting non-simple graphs outright, loops and multi-edges are
removed with switching operations which rewire the edges while preserving the
degrees of the nodes. In addition to an algorithm with expected runtime $O(m)$
for generating graphs with $m$ edges and bounded degrees $\Delta^{4}=O(m)$ [1,
15], efficient algorithms which use this method have been given for generating
$d$-regular graphs in expected time $O(nd+d^{4})$ if $d=o(\sqrt{n})$ [16, 15],
and graphs with power-law degrees in expected time $O(n)$ if the exponent
satisfies $\gamma>(21+\sqrt{61})/10$ [17, 15].

Finally, there exist efficient solutions to various relaxations of the
problem. For instance, we may allow the graph to match the sequence only in
expectation [18, 19], or use a Markov chain to approximate the uniform
distribution [20, 21, 22, 23]. See also [24] for a survey of the most relevant
techniques and results.

###  1.2 Our Contribution

We give results on sampling temporal graphs with given degrees and lifetime.
Formally, given a tuple $\mathbf{D}=(\mathbf{d},T)$, we say that a temporal
multigraph $G$ with nodes $V=\\{v_{1},\dots,v_{n}\\}$ matches $\mathbf{D}$ if
the sum of the numbers of incident edges at node $v_{i}$ over all $T$
timestamps equals $d_{i}$ for each $1\leq i\leq n$. If at least one simple
graph matches $\mathbf{D}$, we call $\mathbf{D}$ _realizable_. The temporal
graph generation problem now asks to output a sample
$G\in\mathcal{G}(\mathbf{D})$ uniformly at random from the set
$\mathcal{G}(\mathbf{D})$ of matching simple temporal graphs. Note that by
allowing repeated connections, a given tuple $\mathbf{D}=(\mathbf{d},T)$ can
be realizable as a simple temporal graph even if $\mathbf{d}$ is not
realizable as a classical simple graph. More severely, consider the sequence
$\mathbf{d}_{t},1\leq t\leq T$ of degree-sequences induced by the individual
timestamps, then there exist sequences which satisfy
$\sum_{t}\mathbf{d}_{t}=\mathbf{d}$ but are not realizable as a sequence of
simple graphs due to loops or multi-edges which cannot be rewired with
switchings which preserve $\mathbf{d}_{t},1\leq t\leq T$. In other words, even
distributing the degrees among the timestamps is not trivial, and existing
algorithms are difficult to apply to sampling temporal graphs. Instead,
switchings are required which operate on the temporal graph as a whole and re-
assign timestamps where necessary, and this is the key feature of the
algorithm which we describe here. This algorithm, called T-Gen, generates
simple temporal graphs with bounded degrees. Our main result is as follows
(see section 4 for proof details).

######  Theorem 1.2.

Given a realizable tuple $\mathbf{D}=(\mathbf{d},T)$ which satisfies
$\Delta^{2+\epsilon}=O(M)$ for a constant $\epsilon>0$ and
$T-\Delta=\Omega(T)$, T-Gen outputs a uniform random sample
$G\in\mathcal{G}(\mathbf{D})$ in expected time $O(M)$.

As customary, we assume an underlying sequence of tuples
$(\mathbf{D}_{M})_{M\in\mathbb{N}}$ and give the asymptotic runtime as
$M\to\infty$. In particular, the conditions on the input tuple can be
understood as being imposed on functions $\Delta(M)$, $T(M)$.

###  1.3 Overview

The general idea of T-Gen is to apply the switching method of [1] to temporal
graphs. To this end, we define a _temporal configuration model_ (see section
2) which samples a random temporal multigraph with the property that the
probability of a given graph only depends on the contained loops and temporal
multi-edges, i.e. multiple edges between the same nodes and with the same
timestamp. In particular, a simple temporal graph output by this model has the
uniform distribution. Usually, the obtained graph is not simple, but if the
input tuple $\mathbf{D}$ satisfies the conditions imposed in Theorem 1.2, then
the number of non-simple edges is sufficiently small to allow for efficient
removal via switchings. An interesting property of the random model in this
context is that the expected number of loops is not affected by the desired
lifetime $T$, whereas the expected number of temporal double-edges scales with
$O(1/T)$ (see 2.3). This allows for a looser bound on the degrees in terms of
the number of edges (e.g. $\Delta^{2+\epsilon}=O(M)$ as opposed to
$\Delta^{4}=O(m)$ for classical graphs with general bounded degrees). As
discussed, a challenging aspect of generating simple temporal graphs is that
the degree-sequences $\mathbf{d}_{t},1\leq t\leq T$ implied by a random
temporal multigraph may not be realizable as a sequence of classical simple
graphs. This necessitates switchings which rewire edges across different time
slices of the graph and re-assign timestamps (see 3.2 and Figure 1 for an
example). As a consequence, the number of timestamps we can assign to an edge
without creating a temporal multi-edge affects the distribution of the graphs,
and to preserve uniformity, it becomes necessary to account for the available
timestamps. To discuss this matter, we briefly describe the technique used in
[1] to correct the distribution.

Generally speaking, when analyzing a switching operation $\theta$ we fix
subsets $\mathcal{S},\mathcal{S^{\prime}}\subseteq\mathcal{M}(\mathbf{d})$ of
the set $\mathcal{M}(\mathbf{d})$ of multigraphs matching the sequence
$\mathbf{d}$. Considering the edges rewired by $\theta$ then associates each
graph $G\in\mathcal{S}$ with a subset
$\mathcal{F}(G)\subseteq\mathcal{S^{\prime}}$ of graphs in
$\mathcal{S^{\prime}}$ which can be produced by performing a type $\theta$
switching on $G$, and each graph $G^{\prime}\in\mathcal{S^{\prime}}$ with a
subset $\mathcal{B}(G^{\prime})\subseteq\mathcal{S}$ of graphs on which we can
perform a type $\theta$ switching which produces $G^{\prime}$. Given this
setup, the goal is to start from a uniform random graph $G\in\mathcal{S}$ and
perform a type $\theta$ switching to obtain a uniform random graph
$G^{\prime}\in\mathcal{S^{\prime}}$. To this end, let $f(G)=|\mathcal{F}(G)|$,
$b(G^{\prime})=|\mathcal{B}(G^{\prime})|$, and assume that
$\mathcal{F}(G)\neq\emptyset$ for every $G\in\mathcal{S}$ and
$\mathcal{B}(G^{\prime})\neq\emptyset$ for every
$G^{\prime}\in\mathcal{S^{\prime}}$. Then, if we start from a graph $G$
uniformly distributed in $\mathcal{S}$, and perform a uniform random type
$\theta$ switching on $G$, the probability of producing a given graph
$G^{\prime}\in\mathcal{S^{\prime}}$ is

$\hfill\sum_{G\in\mathcal{B}(G^{\prime})}\frac{1}{|\mathcal{S}|f(G)}\hfill$

which depends on $G^{\prime}$ if $\mathcal{F}(G)$ and
$\mathcal{B}(G^{\prime})$ vary over different choices of $G$ and $G^{\prime}$.
To correct this, _rejection_ steps can be used which restart the algorithm
with a certain probability. Before performing the switching, we _f-reject_
(forward reject) with probability $1-f(G)/\overline{f}(\mathcal{S})$ where
$\overline{f}(\mathcal{S})$ is an upper bound on $f(G)$ over all graphs
$G\in\mathcal{S}$, and after performing the switching, we _b-reject_ (backward
reject) with probability $1-\underline{b}(\mathcal{S^{\prime}})/b(G^{\prime})$
where $\underline{b}(\mathcal{S^{\prime}})$ is a lower bound on
$b(G^{\prime})$ over all graphs $G^{\prime}\in\mathcal{S^{\prime}}$. The
probability of producing $G^{\prime}$ is now

$\hfill\sum_{G\in\mathcal{B}(G^{\prime})}\frac{1}{|\mathcal{S}|f(G)}\frac{f(G)}{\overline{f}(\mathcal{S})}\frac{\underline{b}(\mathcal{S^{\prime}})}{b(G^{\prime})}=\frac{b(G^{\prime})}{|\mathcal{S}|\overline{f}(\mathcal{S})}\frac{\underline{b}(\mathcal{S^{\prime}})}{b(G^{\prime})}=\frac{\underline{b}(\mathcal{S^{\prime}})}{|\mathcal{S}|\overline{f}(\mathcal{S})}\hfill$

which only depends on $\mathcal{S}$ and $\mathcal{S^{\prime}}$, implying that
$G^{\prime}$ has the uniform distribution if $G$ does.

Still, correcting the distribution in this way is efficient only if the
typical values of $f(G)$ and $b(G^{\prime})$ do not deviate too much from
$\overline{f}(\mathcal{S})$ and $\underline{b}(\mathcal{S^{\prime}})$. To
avoid a high probability of restarting in cases where this does not hold, Gao
and Wormald [16] first used the idea of using additional switchings which
partially equalize the probabilities by mapping graphs of higher probability
to graphs of lower probability. This is implemented via a Markov chain which
either chooses a main switching to remove a non-simple edge or an additional
switching to equalize the probabilities.

T-Gen similarly uses additional switchings but without the use of a Markov
chain. Instead, we always perform the main kind of switching first and then an
additional switching which targets a specified set of edges involved in the
main kind of switching performed. The issue we address in this way is that the
typical number of available timestamps for an edge is $\Omega(T)$, whereas the
corresponding lower bound must be set to $T-(\Delta-1)$ due to the possibility
of a graph in which the edge has multiplicity $\Delta-1$. This would imply a
high probability of restarting unless we place a harsher restriction on
$\Delta$. Fortunately, the conditions imposed in Theorem 1.2 suffice to ensure
that the highest multiplicity of any edge in the initial graph is bound by a
constant $\eta=O(1)$ with high probability (see 2.5, section 2), and we can
also show that any edges created by the algorithm itself only increase the
multiplicity up to a constant $\mu=O(1)$ (3.1, section 3). Now, after
performing a main kind of switching, we partition the subset
$\mathcal{S^{\prime}}$ which contains the obtained graph into the subsets
$\mathcal{S^{\prime}}_{\mathbf{m}<\mu}$ and
$\mathcal{S^{\prime}}\setminus\mathcal{S^{\prime}}_{\mathbf{m}<\mu}$ where
$\mathcal{S^{\prime}}_{\mathbf{m}<\mu}$ contains all graphs in which all
specified edges have multiplicity less than $\mu$. We then equalize the
probabilities of producing the graphs in
$\mathcal{S^{\prime}}_{\mathbf{m}<\mu}$ via switchings which involve the
specified edges with the standard rejection step (which is efficient by
$\mu=O(1)$), and reset the probability of graphs in
$\mathcal{S^{\prime}}\setminus\mathcal{S^{\prime}}_{\mathbf{m}<\mu}$ to zero
by rejecting these graphs. To equalize the probabilities between the graphs in
$\mathcal{S^{\prime}}_{\mathbf{m}<\mu}$ and
$\mathcal{S^{\prime}}\setminus\mathcal{S^{\prime}}_{\mathbf{m}<\mu}$, we
define auxiliary switching operations which map the graphs in
$\mathcal{S^{\prime}}_{\mathbf{m}<\mu}$ to graphs in
$\mathcal{S^{\prime}}\setminus\mathcal{S^{\prime}}_{\mathbf{m}<\mu}$ and an
identity switching which maps any graph in
$\mathcal{S^{\prime}}_{\mathbf{m}<\mu}$ to itself, and specify a probability
distribution over these two kinds of switchings which ensures that all graphs
in $\mathcal{S^{\prime}}$ are produced with the same probability via
switchings which involve the specified edges. It then only remains to equalize
the probabilities over different choices of the specified edges via standard
rejection steps which finally results in the obtained graph being uniformly
distributed in $\mathcal{S^{\prime}}$.

##  2 Temporal Configuration Model

The temporal configuration model samples a random temporal multigraph matching
a given tuple
$\textbf{D}=(\mathbf{d},T)\in\mathbb{N}^{n}\times\mathbb{N}_{>0}$ (provided
that $M=\sum_{i}d_{i}$ is even). It can be implemented as follows. First, for
each node index $i\in\\{1,\dots,n\\}$, put $d_{i}$ marbles labeled $i$ into an
urn. Then, starting from the empty graph $G=(V,\emptyset)$ on the node set
$V=\\{v_{1},\dots,v_{n}\\}$, add edges by iteratively performing the following
steps until the urn is empty:

  1. 1.

Draw two marbles from the urn uniformly at random (without replacement), and
let $i,j$ denote the labels of those marbles.

  2. 2.

Draw a timestamp $t$ uniformly at random from the set of timestamps $[1,T]$.

  3. 3.

Add the temporal edge $(\\{v_{i},v_{j}\\},t)$ to the graph $G$.

In the following, we analyze the output distribution of this random model. To
this end, we first give some definitions to characterize the edges in a
temporal multigraph. Given two nodes $v_{i},v_{j}\in V$ and a timestamp
$t\in[1,T]$, we define $w_{i,j,t}$ as the number of edges between $v_{i}$ and
$v_{j}$ with timestamp $t$ in the graph, and call $w_{i,j,t}$ the _temporal
multiplicity_ of the edge $(\\{v_{i},v_{j}\\},t)$. Then, if $w_{i,j,t}\geq 2$,
we say that the edge is contained in a _temporal multi-edge_ , and in the
special cases $w_{i,j,t}=2$ and $w_{i,j,t}=3$, refer to the multi-edge as a
_double-edge_ and _triple-edge_ , respectively. In addition, we define
$m_{i,j}=\sum_{t}w_{i,j,t}$ as the total number of edges between $v_{i}$ and
$v_{j}$ over all timestamps and call $m_{i,j}$ the _multiplicity_ of
$\\{v_{i},v_{j}\\}$. Finally, we call an edge $(\\{v_{i}\\},t)$ which connects
a node $v_{i}$ to itself a _loop_ at $v_{i}$, and in the cases where
$w_{i,t}=1$ and $w_{i,t}=2$, refer to the edge as a _temporal single-loop_ and
_temporal double-loop_ , respectively.

Now, for a given temporal multigraph $G$, let $\mathbf{W}(G)$ denote the
$n\times n\times T$ tensor such that the entries $\mathbf{W}_{i,j,t}(G)$ where
$i\neq j$ contain $w_{i,j,t}$ if $w_{i,j,t}\geq 2$ and $0$ if otherwise, and
the entries $\mathbf{W}_{i,i,t}(G)$ contain $w_{i,t}$. In other words,
$\mathbf{W}(G)$ specifies the temporal multiplicities of all temporal multi-
edges and loops in $G$. In addition, let $\mathcal{M}(\mathbf{D})$ denote the
set of temporal multigraphs matching a given tuple $\mathbf{D}$, and for a
given tensor $\mathbf{W}$, let $\mathcal{S}(\mathbf{W})$ denote the subset of
temporal multigraphs $G\in\mathcal{M}(\mathbf{D})$ such that
$\mathbf{W}(G)=\mathbf{W}$. Then, the following holds.

######  Theorem 2.1.

Let $G$ be a temporal multigraph output by the temporal configuration model on
an input tuple $\mathbf{D}$. Then, $G$ is uniformly distributed in the set
$\mathcal{S}(\mathbf{W}(G))\subseteq\mathcal{M}(\mathbf{D})$.

######  Proof 2.2.

For a given tuple $\textbf{D}=(\mathbf{d},T)$, let
$P_{i}=\\{i_{1},\dots,i_{d_{i}}\\}$ where $1\leq i\leq n$, $P=\bigcup_{1\leq
i\leq n}P_{i}$, and define a _temporal configuration_ of D as a partition of
the set $P$ into $M/2$ subsets of size two in which each subset is assigned an
integer $t\in[1,T]$. Then, the temporal configuration model samples a temporal
configuration uniformly at random and outputs the corresponding temporal
multigraph (by identifying the nodes corresponding to the labels and replacing
the subsets together with the assigned integers by temporal edges). Thus, the
probability of a given graph $G$ is proportional to the number of temporal
configurations corresponding to $G$, which equals the number of ways to label
the edges in $G$ with the labels in $P$ which give a distinct temporal
configuration. Denote this number by $C_{P}(G)$, and observe that if
$H_{1}=(V,E_{1})$, $H_{2}=(V,E_{2})$ are the subgraphs of the non-simple edges
and simple edges in $G=(V,E)$, respectively, then as $E_{1}\cap
E_{2}=\emptyset$ and $E_{1}\cup E_{2}=E$, we have
$C_{P}(G)=C_{P_{1}}(H_{1})C_{P_{2}}(H_{2})\prod_{i}\binom{d_{i}}{k_{i}}$ where
$\mathbf{k}$ denotes the degree-sequence of $H_{2}$ (arbitrarily),
$P_{1}=\bigcup_{i}\\{i_{1},\dots,i_{d_{i}-k_{i}}\\}$ and
$P_{2}=\bigcup_{i}\\{i_{1},\dots,i_{k_{i}}\\}$. In addition, we have
$C_{P_{2}}(H_{2})=\prod_{i}k_{i}!$ as all edges incident at the nodes in the
simple temporal graph $H_{2}$ are distinct, which implies that all possible
labelings result in a distinct temporal configuration. Finally, observe that
$\mathbf{W}(G)$ determines both $H_{1}$ and $\mathbf{k}$, and thus $C_{P}(G)$
only depends on $\mathbf{W}(G)$.

Note that the set of _simple_ temporal graphs matching $\mathbf{D}$
corresponds to the special case
$\mathcal{G}(\mathbf{D})=\mathcal{S}(\mathbf{0}^{n\times n\times
T})\subseteq\mathcal{M}(\mathbf{D})$. Thus, Theorem 2.1 implies that a simple
temporal graph output by the random model is uniformly distributed in the set
$\mathcal{G}(\mathbf{D})$. In general, the probability of obtaining a simple
temporal graph is small (see 2.3 below). Still, there are conditions under
which the numbers and multiplicities of non-simple edges are manageable. We
state these conditions in terms of the following properties of a degree-
sequence $\mathbf{d}$:

$\hfill\Delta=\max_{1\leq i\leq n}d_{i},\hfill M=\sum_{1\leq i\leq
n}d_{i},\hfill M_{2}=\sum_{\begin{subarray}{c}1\leq i\leq n\\\
d_{i}>0\end{subarray}}d_{i}(d_{i}-1).\hfill$

######  Lemma 2.3.

Let $\mathbf{D}=(\mathbf{d},T)$ be a tuple which satisfies $\Delta^{2}=o(M)$
and $\Delta=O(T)$, and $G$ a graph output by the temporal configuration model
when given $\mathbf{D}$ as input. Then, the expected number of temporal
double-edges in $G$ is $O(M_{2}^{2}/M^{2}T)$, the expected number of temporal
single-loops is $O(M_{2}/M)$, and with high probability there are no temporal
double-loops or temporal triple-edges.

######  Proof 2.4.

It is straightforward to check that the probability that $G$ contains $m$
given temporal edges is $O(M^{-m}T^{-m})$. Thus, the expected number of
temporal double-edges in a graph output by the temporal configuration model is

$\hfill O\left(\sum_{1\leq i,j\leq n}\sum_{1\leq t\leq
T}\frac{4\binom{d_{i}}{2}\binom{d_{j}}{2}}{M^{2}T^{2}}\right)=O\left(\frac{M_{2}^{2}}{M^{2}T}\right),\hfill$

the expected number of temporal single-loops is

$\hfill O\left(\sum_{1\leq i\leq n}\sum_{1\leq t\leq
T}\frac{\binom{d_{i}}{2}}{MT}\right)=O\left(\frac{M_{2}}{M}\right),\hfill$

the expected number of temporal triple-edges is

$\hfill O\left(\sum_{1\leq i,j\leq n}\sum_{1\leq t\leq
T}\frac{6\binom{d_{i}}{3}\binom{d_{j}}{3}}{M^{3}T^{3}}\right)=O\left(\frac{\Delta^{2}M_{2}^{2}}{M^{3}T^{2}}\right)=O\left(\frac{\Delta^{2}}{M}\right)=o(1),\hfill$

and the expected number of temporal double-loops is

$\hfill O\left(\sum_{1\leq i\leq n}\sum_{1\leq t\leq
T}\frac{3\binom{d_{i}}{4}}{M^{2}T^{2}}\right)=O\left(\frac{\Delta^{2}M_{2}}{M^{2}T}\right)=O\left(\frac{\Delta^{2}}{M}\right)=o(1).\hfill\qed$

######  Lemma 2.5.

Let $\mathbf{D}=(\mathbf{d},T)$ be a tuple which satisfies
$\Delta^{2+\epsilon}=O(M)$ for a constant $\epsilon>0$ and $\Delta=O(T)$, and
$G$ a graph output by the temporal configuration model when given $\mathbf{D}$
as input. Then, with high probability, the number of incident temporal double-
edges at any node in $G$ is at most $\kappa=\lfloor 1+1/\epsilon\rfloor$, the
number of incident temporal single-loops at any node is at most
$\lambda=\lfloor 1+1/\epsilon\rfloor$, and the highest multiplicity of any
edge is at most $\eta=\lfloor 2+2/\epsilon\rfloor$.

######  Proof 2.6.

Define $\delta=\frac{\epsilon}{2+\epsilon}$ and note that
$\Delta^{2+\epsilon}=O(M)\implies\Delta=O(M^{\delta/\epsilon})$, and if
$\epsilon>0$, then $\Delta^{2}/M=O(M^{-\delta})=o(1)$. Let $K_{m}$ denote the
number of nodes incident with $m$ temporal double-edges in a graph output by
the temporal configuration model. Then

$\displaystyle\quad\quad\quad\quad\mathbb{E}[K_{m}]$
$\displaystyle=O\left(\sum_{1\leq i\leq n}\sum_{1\leq j_{1},\dots,j_{m}\leq
n}\sum_{1\leq t_{1},\dots,t_{m}\leq
T}\frac{\binom{2m}{2,\dots,2}\binom{d_{i}}{2m}\prod_{k=1}^{m}\binom{d_{j_{k}}}{2}}{M^{2m}T^{2m}}\right)$
$\displaystyle=O\left(\frac{M_{2m}M_{2}^{m}}{M^{2m}T^{m}}\right)=O\left(\frac{\Delta^{2m-1}}{M^{m-1}}\right).$

where $M_{k}=\sum_{1\leq i\leq n}\prod_{1\leq j\leq k}(d_{i}-j+1)$ and the
last equality follows by $M_{k+1}<\Delta M_{k}$. Thus, if
$\Delta^{2+\epsilon}=O(M)$ for some constant $\epsilon>0$, the probability of
at least one node incident with more than $\kappa=\lfloor 1+1/\epsilon\rfloor$
temporal double-edges is at most

$\displaystyle\quad\quad\sum_{m=\kappa+1}^{\lfloor\Delta/2\rfloor}\mathbb{E}[K_{m}]$
$\displaystyle=O\left(\sum_{m=\kappa+1}^{\lfloor\Delta/2\rfloor}\frac{\Delta^{2m-1}}{M^{m-1}}\right)$
$\displaystyle=O\left(\sum_{m=\kappa+1}^{\lfloor\Delta/2\rfloor}M^{-\delta(m-1-1/\epsilon)}\right)$
$\displaystyle=O\left(\sum_{m=\kappa+2}^{\lfloor\Delta/2\rfloor}M^{-\delta(m-1-1/\epsilon)}\right)+O\left(M^{-\delta(\underbrace{\kappa+1}_{=\lfloor
1+1/\epsilon\rfloor+1>1+1/\epsilon}-1-1/\epsilon)}\right)$
$\displaystyle=O\left(\sum_{i=1}^{\lfloor\Delta/2\rfloor-(\kappa+1)}M^{-\delta
i}\right)+o(1)$ $\displaystyle=O\left(M^{-\delta}\right)+o(1)$
$\displaystyle=o(1).$

Similarly, let $L_{m}$ denote the number of nodes incident with $m$ temporal
single-loops, then

$\hfill\mathbb{E}[L_{m}]=O\left(\sum_{1\leq i\leq n}\sum_{1\leq
t_{1},\dots,t_{m}\leq
T}\frac{\binom{2m}{2,\dots,2}\binom{d_{i}}{2m}}{M^{m}T^{m}}\right)=O\left(\frac{M_{2m}}{M^{m}}\right)=O\left(\frac{\Delta^{2m-1}}{M^{m-1}}\right)\hfill$

which if $\Delta^{2+\epsilon}=O(M)$ implies that the probability of at least
one node incident with more than $\lambda=\lfloor 1+1/\epsilon\rfloor$
temporal single-loops is $o(1)$ by the same argument as above. Finally, let
$H_{m}$ denote the number of ordinary multi-edges of multiplicity $m$, then

$\hfill\mathbb{E}[H_{m}]=O\left(\sum_{1\leq i,j\leq
n}\frac{m!\binom{d_{i}}{m}\binom{d_{j}}{m}}{M^{m}}\right)=O\left(\frac{M_{m}^{2}}{M^{m}}\right)=O\left(\frac{\Delta^{2m-2}}{M^{m-2}}\right)\hfill$

which if $\Delta^{2+\epsilon}=O(M)$ implies that the probability of at least
one ordinary multi-edge of multiplicity higher than $\eta=\lfloor
2+2/\epsilon\rfloor$ is $o(1)$ by the same argument as above.

##  3 Algorithm T-Gen

T-Gen takes a realizable tuple $\mathbf{D}$ as input and outputs a uniform
random sample $G\in\mathcal{G}(\mathbf{D})$ from the set of matching simple
temporal graphs. The algorithm starts by sampling a random temporal multigraph
$G\in\mathcal{M}(\mathbf{D})$ via the temporal configuration model (see
section 2). It then checks if $G$ satisfies initial conditions on the numbers
and multiplicities of non-simple edges (see subsection 3.1). In particular,
the initial graph $G$ is not allowed to contain temporal triple-edges, or
temporal double-loops (or any higher multiplicities). If $G$ satisfies these
conditions, then the algorithm proceeds to removing all temporal single-loops
and temporal double-edges during two stages. Stage 1 (subsection 3.2) removes
all temporal single-loops in the graph. For this purpose three kinds of
switching operations are used. The main kind of switching removes a temporal
single-loop at a specified node and with a specified timestamp. After
performing this kind of switching we always perform one of two auxiliary
switchings. The purpose of these switchings is to equalize the probabilities
between graphs which contain ordinary multi-edges of high multiplicity and
graphs which do not. Stage 2 (subsection 3.3) removes all temporal double-
edges, i.e. double-edges which share the same timestamp. Doing this
efficiently requires five kinds of switchings, two of which remove a temporal
double-edge between two specified nodes and with a specified timestamp, and
three of which are auxiliary switchings. Once all non-simple edges have been
removed, the resulting simple temporal graph is output.

###  3.1 Initial Conditions

The initial conditions for the random multigraph $G$ are as follows. Define

$\hfill B_{L}=\frac{M_{2}}{M},\quad\quad\quad
B_{D}=\frac{M_{2}^{2}}{M^{2}T},\hfill$

let $L=\sum_{i,t}\mathbf{W}_{i,i,t}(G)$ and $D=\sum_{i\neq
j,t}\mathbf{W}_{i,j,t}(G)$ denote the sums of the multiplicities of loops and
temporal multi-edges of $G$, respectively, and choose three constants

$\hfill\lambda\geq 1+1/\epsilon,\quad\quad\quad\quad\kappa\geq
1+1/\epsilon,\quad\quad\quad\quad\mu\geq 3+2/\epsilon\hfill$

where $\epsilon>0$ is a constant such that $\Delta^{2+\epsilon}=O(M)$ (or set
$\lambda=\kappa=\mu=\Delta$ if no such constant exists). Then, $G$ satisfies
the initial conditions if $L\leq B_{L}$, $D/2\leq B_{D}$, there are no loops
of temporal multiplicity $w\geq 2$ or temporal multi-edges of temporal
multiplicity $w\geq 3$, and no node is incident with more than $\lambda$
temporal single-loops or $\kappa$ temporal double-edges.

Observe that the lower bounds on the constants $\lambda$ and $\kappa$ are
implied by 2.5. The lower bound on $\mu$ is implied by the following result
(proof in subsection 4.2).

######  Lemma 3.1.

If the input tuple $\mathbf{D}=(\mathbf{d},T)$ satisfies
$\Delta^{2+\epsilon}=O(M)$ for a constant $\epsilon>0$ and
$T-\Delta=\Omega(T)$, then with high probability none of the graphs visited
during a given run of T-Gen contain an edge of multiplicity higher than
$\mu=\lfloor 3+2/\epsilon\rfloor$.

As a simple temporal graph is allowed to contain ordinary multi-edges, the
constant $\mu$ cannot be enforced by rejecting violating initial graphs.
Instead, we equalize the probabilities between graphs which contain such edges
and graphs which do not via the auxiliary switchings mentioned above. We
describe this approach in detail in subsection 3.2 and subsection 3.3.

Finally, there are two special cases. First, if the initial multigraph $G$ is
simple, then this graph can be output without checking the preconditions or
going through any of the stages. Second, if the input tuple does not satisfy

$\hfill M>16\Delta^{2}+4\Delta+2B_{L}+4B_{D},\quad\quad\quad\quad
T>\Delta-1\hfill$

then T-Gen restarts until a simple graph is found and output. Note that these
requirements are satisfied if $\Delta^{2+\epsilon}=O(M)$ and
$T-\Delta=\Omega(T)$, however, we make them explicit here to ensure
correctness on any input tuple.

In all other cases, T-Gen restarts if the graph $G$ does not satisfy the
initial conditions. Otherwise, the algorithm enters Stage 1 to remove the
temporal single-loops in $G$.

###  3.2 Stage 1: Removal of Temporal Single-Loops

$t_{1}$$v_{1}$$t_{2}$$v_{2}$$v_{4}$$t_{3}$$v_{3}$$v_{5}$$t_{4}$$v_{1}$$v_{2}$$t_{5}$$v_{1}$$v_{3}$$t_{6}$$v_{4}$$v_{5}$

Figure 1: The $\mathsf{TL}$ switching removes a temporal single-loop with
timestamp $t_{1}$ at a node $v_{1}$. A shaded region labeled with a timestamp
contains all edges with this timestamp between the nodes. Red and green shades
indicate non-simple and simple edges, respectively.

Stage 1 removes the temporal single-loops in the graph. Doing this efficiently
requires multiple kinds of switching operations. In total, we use three kinds
of switchings which we denote as $\mathsf{TL}$, $\mathsf{A}_{m,n}$ and
$\mathsf{I}$. We formally define each kind of switching below. The switching
of the main kind written as $\mathsf{TL}$ removes a temporal single-loop at a
specified node and with a specified timestamp. After performing this kind of
switching, an $\mathsf{A}_{m,n}$ auxiliary switching is performed with a
certain probability. This switching adds up to two edges with multiplicities
$\max\\{m,n\\}\geq\mu$ to the graph to equalize the probability of producing
graphs with or without these kinds of edges. In addition, we define the
identity switching $\mathsf{I}$ which maps each graph to itself. This is done
to formalize the event in which no auxiliary switching is performed. Formal
definitions of the $\mathsf{TL}$ and $\mathsf{A}_{m,n}$ switchings are as
follows.

######  Definition 3.2 ($\mathsf{TL}$ switching at $v_{1},t_{1}$).

For a graph $G$ such that $(\\{v_{1}\\},t_{1})$ is a temporal single-loop, let
$(\\{v_{2},v_{4}\\},t_{2})$, $(\\{v_{3},v_{5}\\},t_{3})$ be edges and
$t_{4},t_{5},t_{6}\in[1,T]$ timestamps such that

  * •

none of the edges $(\\{v_{2},v_{4}\\},t_{2})$, $(\\{v_{3},v_{5}\\},t_{3})$ is
a loop or in a temporal double-edge,

  * •

the nodes $v_{2},v_{3},v_{4},v_{5}$ are distinct from $v_{1}$, and $v_{4}$ is
distinct from $v_{5}$, and

  * •

none of the edges $(\\{v_{1},v_{2}\\},t_{4})$, $(\\{v_{1},v_{3}\\},t_{5})$,
$(\\{v_{4},v_{5}\\},t_{6})$ exist.

Then, a $\mathsf{TL}$ switching replaces the edges $(\\{v_{1}\\},t_{1})$,
$(\\{v_{2},v_{4}\\},t_{2})$, $(\\{v_{3},v_{5}\\},t_{3})$ with
$(\\{v_{1},v_{2}\\},t_{4})$, $(\\{v_{1},v_{3}\\},t_{5})$,
$(\\{v_{4},v_{5}\\},t_{6})$ (see Figure 1).

We stress that the integer subscripts of nodes are used in place of generic
indices to reduce visual clutter and simplify the descriptions. Naturally,
these labels may still refer to any node in the graph.

######  Definition 3.3 ($\mathsf{A}_{m,n}$ switching at
$v_{1},v_{2},v_{3},v_{4},v_{5}$).

For a graph $G$ such that $\\{v_{2},v_{4}\\}$ and $\\{v_{3},v_{5}\\}$ are non-
edges, let $(\\{v_{2},v_{2i+4}\\},t_{i})$, $(\\{v_{4},v_{2i+5}\\},t_{m+i})$,
$1\leq i\leq m$ be incident edges at $v_{2}$, $v_{4}$,
$(\\{v_{3},v_{2m+2i+4}\\},t_{2m+i})$, $(\\{v_{5},v_{2m+2i+5}\\},t_{2m+n+i})$,
$1\leq i\leq n$ incident edges at $v_{3}$, $v_{5}$, and
$t_{2m+2n+1},\dots,t_{4m+4n}\in[1,T]$ timestamps such that

  * •

none of the edges $(\\{v_{2},v_{2i+4}\\},t_{i})$,
$(\\{v_{4},v_{2i+5}\\},t_{m+i})$, $1\leq i\leq m$,
$(\\{v_{3},v_{2m+2i+4}\\},t_{2m+i})$ and none of
$(\\{v_{3},v_{2m+2i+5}\\},t_{2m+n+i})$, $1\leq i\leq n$ is a loop or in a
temporal double-edge,

  * •

the nodes $v_{1},\dots,v_{2m+2n+5}$ are all distinct, and

  * •

none of the edges $(\\{v_{2},v_{4}\\},t_{2m+2n+i})$,
$(\\{v_{2i+4},v_{2i+5}\\},t_{3m+2n+i})$, $1\leq i\leq m$ and none of
$(\\{v_{3},v_{5}\\},t_{4m+2n+i})$,
$(\\{v_{2m+2i+4},v_{2m+2i+5}\\},t_{4m+3n+i})$, $1\leq i\leq n$ exist.

Then, an $\mathsf{A}_{m,n}$ switching replaces the edges
$(\\{v_{2},v_{2i+4}\\},t_{i})$, $(\\{v_{4},v_{2i+5}\\},t_{m+i})$, $1\leq i\leq
m$, $(\\{v_{3},v_{2m+2i+4}\\},t_{2m+i})$,
$(\\{v_{3},v_{2m+2i+5}\\},t_{2m+n+i})$, $1\leq i\leq n$ with
$(\\{v_{2},v_{4}\\},t_{2m+2n+i})$, $(\\{v_{2i+4},v_{2i+5}\\},t_{3m+2n+i})$,
$1\leq i\leq m$, $(\\{v_{3},v_{5}\\},t_{4m+2n+i})$,
$(\\{v_{2m+2i+4},v_{2m+2i+5}\\},t_{4m+3n+i})$, $1\leq i\leq n$.

In other words, the $\mathsf{TL}$ switching chooses two edges and then rewires
the specified loop and the two edges such that exactly the specified loop is
removed and no other non-simple edges are created or removed. Likewise, the
$\mathsf{A}_{m,n}$ switching chooses $m$ incident edges at two nodes
$v_{2},v_{4}$ each and $n$ incident edges at two nodes $v_{3},v_{5}$ each and
then rewires the edges such that exactly $m$ simple edges between the nodes
$v_{2},v_{4}$ and exactly $n$ simple edges between the nodes $v_{3},v_{5}$ are
created and no non-simple edges are created or removed.

After each $\mathsf{TL}$ switching, we perform an $\mathsf{A}_{m,n}$ auxiliary
switching or the identity switching. To decide which switching to perform we
define a probability distribution over the different types of switchings which
ensures uniformity. In total, the set of $\mathsf{A}_{m,n}$ auxiliary
switchings is

$\hfill\Theta_{\mathsf{A}}=\bigcup_{\begin{subarray}{c}0\leq m,n<\Delta\\\
\mu\leq\max\\{m,n\\}\end{subarray}}\\{\mathsf{A}_{m,n}\\}.\hfill.$

The switching to be performed is then sampled from the distribution
$(\Theta_{\mathsf{A}}\cup\\{\mathsf{I}\\},P_{\mathsf{A}})$ where

$\hfill
p_{\mathsf{A}}(\mathsf{A}_{m,n})=p_{\mathsf{A}}(\mathsf{I})\frac{\overline{f}_{\mathsf{A}_{m,n}}(\mathbf{W^{\prime}})}{\underline{b}_{\mathsf{A}_{m,n}}(\mathbf{W^{\prime}})},\quad\quad\quad
p_{\mathsf{A}}(\mathsf{I})=1-\sum_{\theta\in\Theta_{\mathsf{A}}}p_{\mathsf{A}}(\theta)\hfill$

for quantities $\overline{f}_{\mathsf{A}_{m,n}}(\mathbf{W^{\prime}})$ and
$\underline{b}_{\mathsf{A}_{m,n}}(\mathbf{W^{\prime}})$ given further below.

On a high level, Stage 1 runs in a loop until a rejection occurs or all
temporal single-loops have been removed from $G$. As our switchings remove a
temporal single-loop at a specified node and with a specified timestamp, the
temporal single-loops can be removed in an arbitrary order. To this end, let
$\pi$ denote a permutation of the entries in $\mathbf{W}(G)$ such that
$\mathbf{W}_{i,i,t}=1$. Then, Stage 1 iterates through the temporal single-
loops in the order given by $\pi$ and performs the following steps for each
temporal single-loop.

  1. 1.

Let $G$ denote the current graph, $\mathbf{W}=\mathbf{W}(G)$ and
$(\\{v_{1}\\},t_{1})$ the loop.

  2. 2.

Pick a uniform random $\mathsf{TL}$ switching $S$ which removes
$(\\{v_{1}\\},t_{1})$ from $G$.

  3. 3.

Restart (f-reject) with probability
$1-\frac{f_{\mathsf{TL}}(G)}{\overline{f}_{\mathsf{TL}}(\mathbf{W})}$.

  4. 4.

Rewire the edges according to $S$, let $G^{\prime}$ denote the resulting graph
and $\mathbf{W^{\prime}}=\mathbf{W}(G^{\prime})$.

  5. 5.

Let $(\\{v_{2},v_{4}\\},t_{2})$, $(\\{v_{3},v_{5}\\},t_{3})$ denote the edges
removed by $S$.

  6. 6.

Restart if $m_{2,4}\geq\mu$ or $m_{3,5}\geq\mu$.

  7. 7.

Restart (b-reject) with probability
$1-\frac{\underline{b}_{\mathsf{TL}}(\mathbf{W^{\prime}};2)}{b_{\mathsf{TL}}(G^{\prime},v_{1}v_{2}v_{3}v_{4}v_{5};2)}$.

  8. 8.

Choose a switching type
$\theta\sim(\Theta_{\mathsf{A}}\cup\\{\mathsf{I}\\},P_{\mathsf{A}})$.

  9. 9.

If $\theta=\mathsf{A}_{m,n}$ for some
$\mathsf{A}_{m,n}\in\Theta_{\mathsf{A}}$:

    1. (a)

Restart if $m_{2,4}\geq 1$ or $m_{3,5}\geq 1$.

    2. (b)

Pick a uniform random $\mathsf{A}_{m,n}$ switching $S^{\prime}$ which adds an
edge with node set $\\{v_{2},v_{4}\\}$ and multiplicity $m$ and an edge with
node set $\\{v_{3},v_{5}\\}$ and multiplicity $n$ to $G^{\prime}$.

    3. (c)

Restart (f-reject) with probability
$1-\frac{f_{\mathsf{A}_{m,n}}(G^{\prime})}{\overline{f}_{\mathsf{A}_{m,n}}(\mathbf{W^{\prime}})}$.

    4. (d)

Rewire the edges according to $S^{\prime}$ and let $G^{\prime\prime}$ denote
the resulting graph.

    5. (e)

Restart (b-reject) with probability
$1-\frac{\underline{b}_{\mathsf{A}_{m,n}}(\mathbf{W^{\prime}})}{b_{\mathsf{A}_{m,n}}(G^{\prime\prime},v_{1}v_{2}v_{3}v_{4}v_{5})}$.

    6. (f)

Set $G^{\prime}\leftarrow G^{\prime\prime}$.

  10. 10.

Restart (b-reject) with probability
$1-\frac{\underline{b}_{\mathsf{TL}}(\mathbf{W^{\prime}};0)\underline{b}_{\mathsf{TL}}(\mathbf{W^{\prime}};1)}{b_{\mathsf{TL}}(G^{\prime},v_{1};0)b_{\mathsf{TL}}(G^{\prime},v_{1}v_{2}v_{3};1)}$.

  11. 11.

Set $G\leftarrow G^{\prime}$.

To fully specify Stage 1, it remains to define the quantities used for the f-
and b-rejection steps. For the f-rejection in step $3$, define
$f_{\mathsf{TL}}(G)$ as the number of $\mathsf{TL}$ switchings which can be
performed on the graph $G$. The corresponding upper bound is

$\hfill\overline{f}_{\mathsf{TL}}(\mathbf{W})=M^{2}T^{3}.\hfill$

For the b-rejections in steps $7$ and $10$, define
$b_{\mathsf{TL}}(G^{\prime},v_{1}v_{2}v_{3}v_{4}v_{5};2)$ as the number of
timestamps $t_{2},t_{3}\in[1,T]$ such that the edges
$(\\{v_{2},v_{4}\\},t_{2})$, $(\\{v_{3},v_{5}\\},t_{3})$ do not exist in
$G^{\prime}$, $b_{\mathsf{TL}}(G^{\prime},v_{1}v_{2}v_{3};1)$ as the number of
simple temporal edges $(\\{v_{4},v_{5}\\},t_{6})$ such that $v_{4}$, $v_{5}$
are distinct from $v_{1}$, $v_{2}$, $v_{3}$, and
$b_{\mathsf{TL}}(G^{\prime},v_{1};0)$ as the number of distinct simple
temporal edges $(\\{v_{1},v_{2}\\},t_{4})$, $(\\{v_{1},v_{3}\\},t_{5})$
incident at $v_{1}$. The lower bounds on these quantities are

$\hfill\underline{b}_{\mathsf{TL}}(\mathbf{W^{\prime}};2)=(T-(\mu-1))^{2},\quad\underline{b}_{\mathsf{TL}}(\mathbf{W^{\prime}};1)=M-2B_{L}-4B_{D}-4\Delta,\quad\underline{b}_{\mathsf{TL}}(\mathbf{W^{\prime}};0)=k_{1}(k_{1}-1)\hfill$

where $k_{i}=d_{i}-\sum_{t}(2\mathbf{W^{\prime}}_{i,i,t}+\sum_{1\leq j\leq
n:j\neq i}\mathbf{W^{\prime}}_{i,j,t})$ denotes the number of simple edges at
$v_{i}$.

For the f-rejection in step $9c$, define $f_{\mathsf{A}_{m,n}}(G^{\prime})$ as
the number of $\mathsf{A}_{m,n}$ switchings which can be performed on the
graph $G^{\prime}$. The upper bound is

$\hfill\overline{f}_{\mathsf{A}_{m,n}}(\mathbf{W^{\prime}})=\Delta^{2(m+n)}T^{2(m+n)}.\hfill$

For the b-rejection in step $9e$, define
$b_{\mathsf{A}_{m,n}}(G^{\prime\prime},v_{1}v_{2}v_{3}v_{4}v_{5})$ as the
number of $\mathsf{A}_{m,n}$ switchings which can produce the graph
$G^{\prime\prime}$. The corresponding lower bound is

$\hfill\underline{b}_{\mathsf{A}_{m,n}}(\mathbf{W^{\prime}})=(M-2B_{L}-4B_{D}-4(m+n+3)\Delta)^{m+n}(T-(\Delta-1))^{2(m+n)}.\hfill$

The correctness of Stage 1 is implied by the following result, the proof of
which can be found in subsection 4.1.

######  Lemma 3.4.

The graph $G^{\prime}$ at the end of an iteration of Stage 1 is uniformly
distributed in $\mathcal{S}(\mathbf{W^{\prime}})$ given that the graph $G$ at
the start of the iteration is uniformly distributed in
$\mathcal{S}(\mathbf{W})$.

Showing that Stage 1 is efficient requires showing that both the probability
of restarting and the run time of all iterations is small. To this end, we
show the following in subsection 4.2.

######  Lemma 3.5.

The probability of not restarting in Stage 1 is
$\exp(-O(\Delta^{2}/M)-O(\Delta/T))$.

######  Lemma 3.6.

The expected run time of Stage 1 is $O(\Delta^{2})$.

Stage 1 ends if all temporal single-loops have been removed. The algorithm
then moves on to Stage 2 to remove the remaining temporal double-edges.

###  3.3 Stage 2: Removal of Temporal Double-Edges

$t_{1}$$v_{1}$$v_{2}$$t_{2}$$v_{3}$$v_{5}$$t_{3}$$v_{4}$$v_{6}$$t_{1}$$v_{1}$$v_{2}$$t_{4}$$v_{1}$$v_{3}$$t_{5}$$v_{2}$$v_{4}$$t_{6}$$v_{5}$$v_{6}$

Figure 2: The $\mathsf{TD}_{1}$ switching removes a temporal double-edge with
timestamp $t_{1}$ between two nodes $v_{1},v_{2}$ while leaving a single-edge
between the nodes. A shaded region labeled with a timestamp contains all edges
with this timestamp between the nodes. Red and green shades indicate non-
simple and simple edges, respectively.

Stage 2 uses five kinds of switchings which we denote as $\mathsf{TD}_{1}$,
$\mathsf{TD}_{0}$, $\mathsf{B}_{m,n}$, $\mathsf{C}_{m,n,o,p}$ and
$\mathsf{I}$. The two main switchings $\mathsf{TD}_{1}$ and $\mathsf{TD}_{0}$
remove a temporal double-edge between two specified nodes with a specified
timestamp. The difference is that the $\mathsf{TD}_{1}$ switching only removes
one occurrence of the edge while the $\mathsf{TD}_{0}$ switching erases both
occurrences. This is done to equalize the probability between graphs in which
the removed temporal double-edge is a non-edge, or single edge. After
performing a $\mathsf{TD}_{1}$ switching, the $\mathsf{B}_{m,n}$ auxiliary
switching may be performed, and after performing a $\mathsf{TD}_{0}$
switching, the $\mathsf{C}_{m,n,o,p}$ switching may be performed. These
auxiliary switchings add edges with multiplicity $\max\\{m,n\\}\geq\mu$ or
$\max\\{m,n,o,p\\}\geq\mu$ to the graph to equalize the probabilities between
graphs with or without these edges. We define the $\mathsf{TD}_{1}$ switching
as follows.

######  Definition 3.7 ($\mathsf{TD}_{1}$ switching at
$(\\{v_{1},v_{2}\\},t_{1})$).

For a graph $G$ such that $(\\{v_{1},v_{2}\\},t_{1})$ is contained in a
temporal double-edge, let $(\\{v_{3},v_{5}\\},t_{2})$,
$(\\{v_{4},v_{6}\\},t_{3})$ be edges and $t_{4},t_{5},t_{6}\in[1,T]$
timestamps such that

  * •

none of the edges $(\\{v_{3},v_{5}\\},t_{2})$, $(\\{v_{4},v_{6}\\},t_{3})$ is
contained in a temporal double-edge,

  * •

the nodes $v_{3},v_{4},v_{5},v_{6}$ are distinct from $v_{1}$ and $v_{2}$, and
$v_{5}$ is distinct from $v_{6}$, and

  * •

none of the edges $(\\{v_{1},v_{3}\\},t_{4})$, $(\\{v_{2},v_{4}\\},t_{5})$,
$(\\{v_{5},v_{6}\\},t_{6})$ exist.

Then, a $\mathsf{TD}_{1}$ switching replaces the edges
$(\\{v_{1},v_{2}\\},t_{1})$, $(\\{v_{3},v_{5}\\},t_{2})$,
$(\\{v_{4},v_{6}\\},t_{3})$ with $(\\{v_{1},v_{3}\\},t_{4})$,
$(\\{v_{2},v_{4}\\},t_{5})$, $(\\{v_{5},v_{6}\\},t_{6})$ (see Figure 2).

The $\mathsf{TD}_{0}$ switching can be defined analogously by using four edges
in place of two to remove both edges contained in the temporal double-edge. To
choose a $\mathsf{TD}_{1}$ or $\mathsf{TD}_{0}$ switching when removing a
temporal double-edge, specify the probability distribution
$(\\{\mathsf{TD}_{1},\mathsf{TD}_{0}\\},P)$ where

$\hfill
p(\mathsf{TD}_{1})=p(\mathsf{TD}_{0})\frac{p_{\mathsf{C}}(\mathsf{I})}{p_{\mathsf{B}}(\mathsf{I})}\frac{\overline{f}_{\mathsf{TD}_{1}}(\mathbf{W})\underline{b}_{\mathsf{TD}_{0}}(\mathbf{W^{\prime}})}{\overline{f}_{\mathsf{TD}_{0}}(\mathbf{W})\underline{b}_{\mathsf{TD}_{1}}(\mathbf{W^{\prime}})},\quad\quad\quad
p(\mathsf{TD}_{0})=1-p(\mathsf{TD}_{1})\hfill$

for quantities $\overline{f}_{\mathsf{TD}_{1}}(\mathbf{W})$,
$\overline{f}_{\mathsf{TD}_{0}}(\mathbf{W})$ and
$\underline{b}_{\mathsf{TD}_{1}}(\mathbf{W^{\prime}})=\underline{b}_{\mathsf{TD}_{1}}(\mathbf{W^{\prime}};0)\underline{b}_{\mathsf{TD}_{1}}(\mathbf{W^{\prime}};1)\underline{b}_{\mathsf{TD}_{1}}(\mathbf{W^{\prime}};2)$,
$\underline{b}_{\mathsf{TD}_{0}}(\mathbf{W^{\prime}})=\underline{b}_{\mathsf{TD}_{0}}(\mathbf{W^{\prime}};0)\underline{b}_{\mathsf{TD}_{0}}(\mathbf{W^{\prime}};1)\underline{b}_{\mathsf{TD}_{0}}(\mathbf{W^{\prime}};2)$
defined below and where $p_{\mathsf{B}}(\mathsf{I})$ and
$p_{\mathsf{C}}(\mathsf{I})$ are the probabilities of not performing a
$\mathsf{B}_{m,n}$ and $\mathsf{C}_{m,n,o,p}$ auxiliary switching,
respectively.

Continuing with the auxiliary switchings, we now define the $\mathsf{B}_{m,n}$
switching. The $\mathsf{C}_{m,n,o,p}$ switching can be defined analogously by
expanding the number of edges created from the two edges removed by the
$\mathsf{TD}_{1}$ switching to the four edges removed by the $\mathsf{TD}_{0}$
switching.

######  Definition 3.8 ($\mathsf{B}_{m,n}$ switching at
$v_{1},v_{2},v_{3},v_{4},v_{5},v_{6}$).

For a graph $G$ such that $\\{v_{3},v_{5}\\}$ and $\\{v_{4},v_{6}\\}$ are non-
edges, let $(\\{v_{3},v_{2i+5}\\},t_{i})$, $(\\{v_{5},v_{2i+6}\\},t_{m+i})$,
$1\leq i\leq m$ be incident edges at $v_{3}$, $v_{5}$,
$(\\{v_{4},v_{2m+2i+5}\\},t_{2m+i})$, $(\\{v_{6},v_{2m+2i+6}\\},t_{2m+n+i})$,
$1\leq i\leq n$ incident edges at $v_{4}$, $v_{6}$, and
$t_{2m+2n+1},\dots,t_{4m+4n}\in[1,T]$ timestamps such that

  * •

none of the edges $(\\{v_{3},v_{2i+5}\\},t_{i})$,
$(\\{v_{5},v_{2i+6}\\},t_{m+i})$, $1\leq i\leq m$,
$(\\{v_{4},v_{2m+2i+5}\\},t_{2m+i})$, $(\\{v_{6},v_{2m+2i+6}\\},t_{2m+n+i})$,
$1\leq i\leq n$ is contained in a temporal double-edge,

  * •

the nodes $v_{1},\dots,v_{2m+2n+6}$ are all distinct, and

  * •

none of the edges $(\\{v_{3},v_{5}\\},t_{2m+2n+i})$,
$(\\{v_{2i+5},v_{2i+6}\\},t_{3m+2n+i})$, $1\leq i\leq m$ and none of the edges
$(\\{v_{4},v_{6}\\},t_{4m+2n+i})$,
$(\\{v_{2m+2i+5},v_{2m+2i+6}\\},t_{4m+3n+i})$, $1\leq i\leq n$ exist.

Then, a $\mathsf{B}_{m,n}$ switching replaces the edges
$(\\{v_{3},v_{2i+5}\\},t_{i})$, $(\\{v_{5},v_{2i+6}\\},t_{m+i})$, $1\leq i\leq
m$, $(\\{v_{4},v_{2m+2i+5}\\},t_{2m+i})$,
$(\\{v_{6},v_{2m+2i+6}\\},t_{2m+n+i})$, $1\leq i\leq n$ with
$(\\{v_{3},v_{5}\\},t_{2m+2n+i})$, $(\\{v_{2i+5},v_{2i+6}\\},t_{3m+2n+i})$,
$1\leq i\leq m$, $(\\{v_{4},v_{6}\\},t_{4m+2n+i})$,
$(\\{v_{2m+2i+5},v_{2m+2i+6}\\},t_{4m+3n+i})$, $1\leq i\leq n$.

The sets of $\mathsf{B}_{m,n}$ and $\mathsf{C}_{m,n,o,p}$ switchings are

$\hfill\Theta_{\mathsf{B}}=\bigcup_{\begin{subarray}{c}0\leq m,n<\Delta\\\
\mu\leq\max\\{m,n\\}\end{subarray}}\\{\mathsf{B}_{m,n}\\}\quad\quad\quad\quad\quad\Theta_{\mathsf{C}}=\bigcup_{\begin{subarray}{c}0\leq
m,n,o,p<\Delta\\\
\mu\leq\max\\{m,n,o,p\\}\end{subarray}}\\{\mathsf{C}_{m,n,o,p}\\}\hfill$

and the associated type distributions are
$(\Theta_{\mathsf{B}}\cup\\{\mathsf{I}\\},P_{\mathsf{B}})$ and
$(\Theta_{\mathsf{C}}\cup\\{\mathsf{I}\\},P_{\mathsf{C}})$ where

$\displaystyle\hfill\quad\quad\quad\quad\quad
p_{\mathsf{B}}(\mathsf{B}_{m,n})$
$\displaystyle=p_{\mathsf{B}}(\mathsf{I})\frac{\overline{f}_{\mathsf{B}_{m,n}}(\mathbf{W^{\prime}})}{\underline{b}_{\mathsf{B}_{m,n}}(\mathbf{W^{\prime}})},\quad\quad\quad$
$\displaystyle p_{\mathsf{B}}(\mathsf{I})$
$\displaystyle=1-\sum_{\theta\in\Theta_{\mathsf{B}}}p_{\mathsf{B}}(\theta),$
$\displaystyle\hfill p_{\mathsf{C}}(\mathsf{C}_{m,n,o,p})$
$\displaystyle=p_{\mathsf{C}}(\mathsf{I})\frac{\overline{f}_{\mathsf{C}_{m,n,o,p}}(\mathbf{W^{\prime}})}{\underline{b}_{\mathsf{C}_{m,n,o,p}}(\mathbf{W^{\prime}})},\quad\quad\quad$
$\displaystyle p_{\mathsf{C}}(\mathsf{I})$
$\displaystyle=1-\sum_{\theta\in\Theta_{\mathsf{C}}}p_{\mathsf{C}}(\theta).$

The main loop of Stage 2 is as follows. Let $\pi$ denote a permutation of the
entries in $\mathbf{W}(G)$ such that $\mathbf{W}_{i,j,t}=2$ and $i\neq j$.
Then, Stage 2 iterates through the temporal double-edges in the order given by
$\pi$ and performs the following steps.

  1. 1.

Let $G$ denote the current graph, $\mathbf{W}=\mathbf{W}(G)$ and
$(\\{v_{1},v_{2}\\},t_{1})$ the temporal double-edge.

  2. 2.

Choose a switching type $\theta\sim(\\{\mathsf{TD}_{0},\mathsf{TD}_{1}\\},P)$.

  3. 3.

Pick a uniform random $\theta$ switching $S$ which removes
$(\\{v_{1},v_{2}\\},t_{1})$ from $G$.

  4. 4.

Restart (f-reject) with probability
$1-\frac{f_{\theta}(G)}{\overline{f}_{\theta}(\mathbf{W})}$.

  5. 5.

Rewire the edges according to $S$, let $G^{\prime}$ denote the resulting graph
and $\mathbf{W^{\prime}}=\mathbf{W}(G^{\prime})$.

  6. 6.

If $\theta=\mathsf{TD}_{1}$:

    1. (a)

Let $(\\{v_{3},v_{5}\\},t_{2})$, $(\\{v_{4},v_{6}\\},t_{3})$ denote the edges
removed by $S$.

    2. (b)

Restart if $m_{3,5}\geq\mu$ or $m_{4,6}\geq\mu$.

    3. (c)

Restart (b-reject) with probability
$1-\frac{\underline{b}_{\mathsf{TD}_{0}}(\mathbf{W^{\prime}};2)}{b_{\mathsf{TD}_{0}}(G^{\prime},v_{1}\dots
v_{6};2)}$.

    4. (d)

Choose a switching type
$\theta_{\mathsf{B}}\sim(\Theta_{\mathsf{B}}\cup\\{\mathsf{I}\\},P_{\mathsf{B}})$.

    5. (e)

If $\theta=\mathsf{B}_{m,n}$ for some
$\mathsf{B}_{m,n}\in\Theta_{\mathsf{B}}$:

      1. i.

Restart if $m_{3,5}\geq 1$ or $m_{4,6}\geq 1$.

      2. ii.

Pick a uniform random $\mathsf{B}_{m,n}$ switching $S^{\prime}$ which adds an
edge with node set $\\{v_{3},v_{5}\\}$ and multiplicity $m$ and an edge with
node set $\\{v_{4},v_{6}\\}$ and multiplicity $n$ to $G^{\prime}$.

      3. iii.

Restart (f-reject) with probability
$1-\frac{f_{\mathsf{B}_{m,n}}(G^{\prime})}{\overline{f}_{\mathsf{B}_{m,n}}(\mathbf{W^{\prime}})}$.

      4. iv.

Rewire the edges according to $S^{\prime}$ and let $G^{\prime\prime}$ denote
the resulting graph.

      5. v.

Restart (b-reject) with probability
$1-\frac{\underline{b}_{\mathsf{B}_{m,n}}(\mathbf{W^{\prime}})}{b_{\mathsf{B}_{m,n}}(G^{\prime\prime},v_{1}\dots
v_{6})}$.

      6. vi.

Set $G^{\prime}\leftarrow G^{\prime\prime}$.

    6. (f)

Restart (b-reject) with probability
$1-\frac{\underline{b}_{\mathsf{TD}_{1}}(\mathbf{W^{\prime}};0)\underline{b}_{\mathsf{TD}_{1}}(\mathbf{W^{\prime}};1)}{b_{\mathsf{TD}_{1}}(G^{\prime},v_{1}v_{2};0)b_{\mathsf{TD}_{1}}(G^{\prime},v_{1}v_{2}v_{3}v_{4};1)}$.

  7. 7.

Else if $\theta=\mathsf{TD}_{0}$:

    1. (a)

Let $(\\{v_{3},v_{7}\\},t_{2})$, $(\\{v_{4},v_{8}\\},t_{3})$,
$(\\{v_{5},v_{9}\\},t_{4})$, $(\\{v_{6},v_{10}\\},t_{5})$ denote the edges
removed by $S$.

    2. (b)

Restart if $m_{3,7}\geq\mu$, $m_{4,8}\geq\mu$, $m_{5,9}\geq\mu$ or
$m_{6,10}\geq\mu$.

    3. (c)

Restart (b-reject) with probability
$1-\frac{\underline{b}_{\mathsf{TD}_{0}}(\mathbf{W^{\prime}};2)}{b_{\mathsf{TD}_{0}}(G^{\prime},v_{1}\dots
v_{10};2)}$.

    4. (d)

Choose a switching type
$\theta_{\mathsf{C}}\sim(\Theta_{\mathsf{C}}\cup\\{\mathsf{I}\\},P_{\mathsf{C}})$.

    5. (e)

If $\theta=\mathsf{C}_{m,n,o,p}$ for some
$\mathsf{C}_{m,n,o,p}\in\Theta_{\mathsf{C}}$:

      1. i.

Restart if $m_{3,7}\geq 1$, $m_{4,8}\geq 1$, $m_{5,9}\geq 1$ or $m_{6,10}\geq
1$.

      2. ii.

Pick a uniform random $\mathsf{C}_{m,n,o,p}$ switching $S^{\prime}$ which adds
an edge with node set $\\{v_{3},v_{7}\\}$ and multiplicity $m$, an edge with
node set $\\{v_{4},v_{8}\\}$ and multiplicity $n$, an edge with node set
$\\{v_{5},v_{9}\\}$ and multiplicity $o$,, and an edge with node set
$\\{v_{6},v_{10}\\}$ and multiplicity $p$ to $G^{\prime}$.

      3. iii.

Restart (f-reject) with probability
$1-\frac{f_{\mathsf{C}_{m,n,o,p}}(G^{\prime})}{\overline{f}_{\mathsf{C}_{m,n,o,p}}(\mathbf{W^{\prime}})}$.

      4. iv.

Rewire the edges according to $S^{\prime}$ and let $G^{\prime\prime}$ denote
the resulting graph.

      5. v.

Restart (b-reject) with probability
$1-\frac{\underline{b}_{\mathsf{C}_{m,n,o,p}}(\mathbf{W^{\prime}})}{b_{\mathsf{C}_{m,n,o,p}}(G^{\prime\prime},v_{1}\dots
v_{10})}$.

      6. vi.

Set $G^{\prime}\leftarrow G^{\prime\prime}$.

    6. (f)

Restart (b-reject) with probability
$1-\frac{\underline{b}_{\mathsf{TD}_{0}}(\mathbf{W^{\prime}};0)\underline{b}_{\mathsf{TD}_{0}}(\mathbf{W^{\prime}};1)}{b_{\mathsf{TD}_{0}}(G^{\prime},v_{1}v_{2};0)b_{\mathsf{TD}_{0}}(G^{\prime},v_{1}\dots
v_{6};1)}$.

  8. 8.

Set $G\leftarrow G^{\prime}$.

It remains to define the quantities required for the f- and b-rejection steps.
For the f-rejection in step $4$, define $f_{\mathsf{TD}_{1}}(G)$ and
$f_{\mathsf{TD}_{0}}(G)$ as the number of $\mathsf{TD}_{1}$ and
$\mathsf{TD}_{0}$ switchings which can be performed on the graph $G$,
respectively. The corresponding upper bounds are

$\hfill\overline{f}_{\mathsf{TD}_{1}}(\mathbf{W})=M^{2}T^{3},\quad\quad\quad\quad\overline{f}_{\mathsf{TD}_{0}}(\mathbf{W})=M^{4}T^{6}.\hfill$

For the b-rejections in steps $6c$ and $7c$, define
$b_{\mathsf{TD_{1}}}(G^{\prime},v_{1}\dots v_{6};2)$ as the number of
timestamps $t_{2},t_{3}\in[1,T]$ such that $(\\{v_{3},v_{5}\\},t_{2})$,
$(\\{v_{4},v_{6}\\},t_{3})$ do not exist in $G^{\prime}$ and
$b_{\mathsf{TD_{0}}}(G^{\prime},v_{1}\dots v_{10};2)$ as the number of
timestamps $t_{2},t_{3},t_{4},t_{5}\in[1,T]$ such that
$(\\{v_{3},v_{7}\\},t_{2})$, $(\\{v_{4},v_{8}\\},t_{3})$,
$(\\{v_{5},v_{9}\\},t_{4})$, $(\\{v_{6},v_{10}\\},t_{5})$ do not exist in
$G^{\prime}$. The lower bounds are

$\hfill\underline{b}_{\mathsf{TD}_{1}}(\mathbf{W^{\prime}};2)=(T-(\mu-1))^{2},\quad\quad\quad\quad\underline{b}_{\mathsf{TD}_{0}}(\mathbf{W^{\prime}};2)=(T-(\mu-1))^{4}.\hfill$

For the b-rejections in steps $6f$ and $7f$, define
$b_{\mathsf{TD_{1}}}(G^{\prime},v_{1}\dots v_{4};1)$ as the number of simple
edges $(\\{v_{5},v_{6}\\},t_{6})$ in $G^{\prime}$ such that $v_{5}$, $v_{6}$
are distinct from $v_{1},v_{2},v_{3},v_{4}$ and
$b_{\mathsf{TD_{0}}}(G^{\prime},v_{1}\dots v_{6};1)$ as the number of distinct
simple edges $(\\{v_{7},v_{8}\\},t_{10})$, $(\\{v_{9},v_{10}\\},t_{11})$ in
$G^{\prime}$ such that $v_{7}$, $v_{8}$, $v_{9}$, $v_{10}$ are distinct from
$v_{1},v_{2},v_{3},v_{4},v_{5},v_{6}$. Then, define
$b_{\mathsf{TD_{1}}}(G^{\prime},v_{1}v_{2};0)$ as the number of simple edges
$(\\{v_{1},v_{3}\\},t_{4})$, $(\\{v_{2},v_{4}\\},t_{5})$ incident at $v_{1}$
and $v_{2}$ in $G^{\prime}$ and $b_{\mathsf{TD_{0}}}(G^{\prime},v_{1}v_{2};0)$
as the number of distinct simple edges $(\\{v_{1},v_{3}\\},t_{4})$,
$(\\{v_{2},v_{4}\\},t_{5})$, $(\\{v_{1},v_{5}\\},t_{6})$,
$(\\{v_{2},v_{6}\\},t_{7})$ incident at $v_{1}$ and $v_{2}$ in $G^{\prime}$.
The lower bounds are

$\displaystyle\begin{aligned}
\quad&\underline{b}_{\mathsf{TD}_{1}}(\mathbf{W^{\prime}};1)=M-4B_{D}-4\Delta,&&\underline{b}_{\mathsf{TD}_{0}}(\mathbf{W^{\prime}};1)=(M-4B_{D}-4\Delta)^{2},&\\\
\quad&\underline{b}_{\mathsf{TD}_{1}}(\mathbf{W^{\prime}};0)=k_{1}k_{2},&&\underline{b}_{\mathsf{TD}_{0}}(\mathbf{W^{\prime}};0)=k_{1}(k_{1}-1)k_{2}(k_{2}-1).&\end{aligned}$

For the f-rejections in steps $6eiii$ and $7eiii$, define
$f_{\mathsf{B}_{m,n}}(G^{\prime})$, $f_{\mathsf{C}_{m,n,o,p}}(G^{\prime})$ as
the number of $\mathsf{B}_{m,n}$, $\mathsf{C}_{m,n,o,p}$ switchings which can
be performed on $G^{\prime}$, respectively. In addition, define

$\hfill\overline{f}_{\mathsf{B}_{m,n}}(\mathbf{W^{\prime}})=\Delta^{2(m+n)}T^{2(m+n)},\quad\quad\quad\quad\overline{f}_{\mathsf{C}_{m,n,o,p}}(\mathbf{W^{\prime}})=\Delta^{2(m+n+o+p)}T^{2(m+n+o+p)}.\hfill$

For the b-rejections in steps $6ev$ and $7ev$, define
$b_{\mathsf{B}_{m,n}}(G^{\prime\prime},v_{1}\dots v_{6})$ and
$b_{\mathsf{C}_{m,n,o,p}}(G^{\prime\prime},v_{1}\dots v_{10})$ as the number
of $\mathsf{B}_{m,n}$ and $\mathsf{C}_{m,n,o,p}$ switchings which can produce
the graph $G^{\prime\prime}$, respectively. The corresponding lower bounds are

$\displaystyle\underline{b}_{\mathsf{B}_{m,n}}(\mathbf{W^{\prime}})$
$\displaystyle=(M-4B_{D}-4(m+n+3)\Delta)^{m+n}(T-(\Delta-1))^{2(m+n)},$
$\displaystyle\underline{b}_{\mathsf{C}_{m,n,o,p}}(\mathbf{W^{\prime}})$
$\displaystyle=(M-4B_{D}-4(m+n+o+p+5)\Delta)^{m+n+o+p}(T-(\Delta-1))^{2(m+n+o+p)}.$

The following lemmata ensure the correctness and efficiency of Stage 2 (proofs
in subsection 4.1 and subsection 4.2).

######  Lemma 3.9.

The graph $G^{\prime}$ at the end of an iteration of Stage 2 is uniformly
distributed in $\mathcal{S}(\mathbf{W^{\prime}})$ given that the graph $G$ at
the start of the iteration is uniformly distributed in
$\mathcal{S}(\mathbf{W})$.

######  Lemma 3.10.

The probability of not restarting in Stage 2 is
$\exp(-O(\Delta^{3}/MT)-O(\Delta^{2}/T^{2}))$.

######  Lemma 3.11.

The expected run time of Stage 2 is $O(\Delta^{3}/T)$.

Once Stage 2 ends, the final graph is simple and can be output.

##  4 Proof of Theorem 1.2

It remains to show Theorem 1.2. We start with the uniformity of the output
distribution.

###  4.1 Uniformity of T-Gen

To show 3.4, we first show that the upper and lower bounds specified for Stage
1 hold. To this end, let
$\mathcal{M}_{0}(\mathbf{D})\subseteq\mathcal{M}(\mathbf{D})$ denote the set
of temporal multigraphs which satisfy the initial conditions specified in
subsection 3.1. Then, we obtain the following.

######  Lemma 4.1.

For all $G\in\mathcal{S}(\mathbf{W})\subseteq\mathcal{M}_{0}(\mathbf{D})$ we
have

$\displaystyle f_{\mathsf{TL}}(G)\leq\overline{f}_{\mathsf{TL}}(\mathbf{W}).$

######  Proof 4.2.

By 3.2, a $\mathsf{TL}$ switching involves two edges
$(\\{v_{2},v_{4}\\},t_{2})$, $(\\{v_{3},v_{5}\\},t_{3})$ and three timestamps
$t_{4},t_{5},t_{6}\in[1,T]$. The total number of choices for the edges and
timestamps constitutes an upper bound on the number of switchings which can be
performed, and there are at most $M^{2}$ choices the (oriented) edges and at
most $T^{3}$ choices the timestamps.

######  Lemma 4.3.

For all
$G^{\prime}\in\mathcal{S}(\mathbf{W^{\prime}})\subseteq\mathcal{M}_{0}(\mathbf{D})$
where $m_{2,4}<\mu$ and $m_{3,5}<\mu$ we have

$\displaystyle\underline{b}_{\mathsf{TL}}(\mathbf{W^{\prime}};2)\leq
b_{\mathsf{TL}}(G^{\prime},v_{1}v_{2}v_{3}v_{4}v_{5};2)\leq T^{2}$

and for all
$G^{\prime}\in\mathcal{S}(\mathbf{W^{\prime}})\subseteq\mathcal{M}_{0}(\mathbf{D})$
we have

$\displaystyle\underline{b}_{\mathsf{TL}}(\mathbf{W^{\prime}};1)\leq
b_{\mathsf{TL}}(G^{\prime},v_{1}v_{2}v_{3};1)\leq M,$
$\displaystyle\underline{b}_{\mathsf{TL}}(\mathbf{W^{\prime}};0)=b_{\mathsf{TL}}(G^{\prime},v_{1};0).$

######  Proof 4.4.

The first set of inequalities follows since there are at most $T$ and at least
$T-(\mu-1)$ available timestamps for each edge with multiplicity at most
$\mu-1$. For the second set of inequalities, there are at most $M$ choices for
an edge, at most $2B_{L}+4B_{D}$ choices such that the edge is not simple, and
at most $4\Delta$ choices such that some of the nodes are not distinct. For
the equality, observe that $\mathbf{W^{\prime}}$ (in addition to $\mathbf{D}$)
determines the number of incident simple temporal edges at all nodes.

######  Lemma 4.5.

For all
$G^{\prime}\in\mathcal{S}(\mathbf{W^{\prime}})\subseteq\mathcal{M}_{0}(\mathbf{D})$
we have

$\displaystyle
f_{\mathsf{A}_{m,n}}(G^{\prime})\leq\overline{f}_{\mathsf{A}_{m,n}}(\mathbf{W^{\prime}}).$

######  Proof 4.6.

The number of edges and timestamps needed for the $\mathsf{A}_{m,n}$ switching
is $2(m+n)$ and there are at most $\Delta$ choices for each incident edge, and
at most $T$ choices for each timestamp.

######  Lemma 4.7.

For all
$G^{\prime\prime}\in\mathcal{S}(\mathbf{W^{\prime}})\subseteq\mathcal{M}_{0}(\mathbf{D})$
we have

$\displaystyle\underline{b}_{\mathsf{A}_{m,n}}(\mathbf{W^{\prime}})\leq
b_{\mathsf{A}_{m,n}}(G^{\prime\prime},v_{1}\dots v_{5})\leq
M^{m+n}T^{2(m+n)}.$

######  Proof 4.8.

The number of switchings which can produce a given graph corresponds to the
number of choices for edges and timestamps needed to reverse the switching.
Reversing the $\mathsf{A}_{m,n}$ switching requires $m+n$ edges and $2(m+n)$
timestamps. For each edge, there are at most $M$ choices, at most
$2B_{L}+4B_{D}$ choices such that the edge is not simple, and at most
$2\Delta$ choices for each node already chosen such that the nodes are not
distinct. For each timestamp, there are at most $T$ choices, and at least
$T-(\Delta-1)$ choices such that the edge does not exist in
$G^{\prime\prime}$.

######  Proof 4.9 (Proof of 3.4).

Let $c_{i,j}=\sum_{1\leq t\leq T}\mathbf{1}_{w_{i,j,t}>0}$ denote the number
of distinct temporal edges between two given nodes $v_{i},v_{j}$ and
$N(v_{i})$ the (multi-)set of incident temporal edges at a given node $v_{i}$.
Then by 4.1, after the f-rejection in step $3$ a given graph
$G^{\prime}\in\mathcal{S}(\mathbf{W^{\prime}})$ is produced with probability

$\hfill\sum_{\begin{subarray}{c}(\\{v_{1},v_{2}\\},t_{4})\neq(\\{v_{1},v_{3}\\},t_{5})\in
N(v_{1})\\\ v_{1}\neq v_{2},w_{1,2,4}=1\\\ v_{1}\neq
v_{3},w_{1,3,5}=1\end{subarray}}\sum_{\begin{subarray}{c}(\\{v_{4},v_{5}\\},t_{6})\in
E\\\ v_{4}\neq v_{5},w_{4,5,6}=1\\\ v_{4}\notin\\{v_{1},v_{2}\\}\\\
v_{5}\notin\\{v_{1},v_{3}\\}\end{subarray}}\frac{(T-c_{2,4})(T-c_{3,5})}{\overline{f}_{\mathsf{TL}}(\mathbf{W})|\mathcal{S}(\mathbf{W})|}\hfill$

where $v_{1}$ is the node at which the temporal single-loop was removed. Thus,
in particular, $G^{\prime}$ is produced via switchings where we fix the three
created edges $(\\{v_{1},v_{2}\\},t_{4})$, $(\\{v_{1},v_{3}\\},t_{5})$,
$(\\{v_{4},v_{5}\\},t_{6})$ to three given edges which satisfy the conditions
with probability

$\hfill\frac{(T-c_{2,4})(T-c_{3,5})}{{\overline{f}_{\mathsf{TL}}(\mathbf{W})|\mathcal{S}(\mathbf{W})|}}\propto
b_{\mathsf{TL}}(G^{\prime},v_{1}v_{2}v_{3}v_{4}v_{5};2)\hfill$

and by 4.3 after steps $6$ and $7$ with probability proportional to
$\underline{b}_{\mathsf{TL}}(\mathbf{W^{\prime}};2)=T-(\mu-1)$ if
$m_{2,4},m_{3,5}<\mu$ (which implies $c_{2,4},c_{3,5}<\mu$) and probability
$0$ if any of $m_{2,4}\geq\mu$, $m_{3,5}\geq\mu$. Now, if $m_{2,4}=m_{3,5}=0$,
we perform a type $\mathsf{A}_{m,n}$ switching with probability
$p_{\mathsf{A}}(\mathsf{A}_{m,n})$, or restart the algorithm with this
probability if $0<m_{2,4},m_{3,5}<\mu$. Thus, if $0\leq m_{2,4},m_{3,5}<\mu$,
the probability of producing $G^{\prime}$ via switchings which create the
three fixed edges is

$\hfill
p_{\mathsf{A}}(\mathsf{I})\frac{\underline{b}_{\mathsf{TL}}(\mathbf{W^{\prime}};2)}{\overline{f}_{\mathsf{TL}}(\mathbf{W})|\mathcal{S}(\mathbf{W})|}.\hfill$

If instead $\mu\leq m_{2,4}<\min\\{d_{2},d_{4}\\}$ or $\mu\leq
m_{3,5}<\min\\{d_{3},d_{5}\\}$, then $G^{\prime}$ is produced only via an
$\mathsf{A}_{m_{2,4},m_{3,5}}$ switching on a graph with $m_{2,4}=m_{3,5}=0$
and by 4.5 and 4.7, after the f- and b-rejections in steps $9c$ and $9e$, the
probability of producing $G^{\prime}$ in this way is

$\hfill
p_{\mathsf{A}}(\mathsf{A}_{m_{2,4},m_{3,5}})\frac{\underline{b}_{\mathsf{A}_{m_{2,4},m_{3,5}}}(\mathbf{W^{\prime}})}{\overline{f}_{\mathsf{A}_{m_{2,4},m_{3,5}}}(\mathbf{W^{\prime}})}\frac{\underline{b}_{\mathsf{TL}}(\mathbf{W^{\prime}};2)}{\overline{f}_{\mathsf{TL}}(\mathbf{W})|\mathcal{S}(\mathbf{W})|}.\hfill$

It is now straightforward to verify that the probabilities
$p_{\mathsf{A}}(\mathsf{I})$ and $p_{\mathsf{A}}(\mathsf{A}_{m,n})$ as
specified for Stage 1 equalize the expressions given above. Thus, after step
$9$, the probability of producing a given graph $G^{\prime}$ via switchings
which create the three fixed edges no longer depends on $c_{2,4}$ or
$c_{3,5}$. It only remains to show that step $10$ equalizes the probabilities
over all choices of the three edges $(\\{v_{1},v_{2}\\},t_{4})$,
$(\\{v_{1},v_{3}\\},t_{5})$ and $(\\{v_{4},v_{5}\\},t_{6})$. To this end,
observe that the probability of producing $G^{\prime}$ via switchings where we
only fix the choices of $(\\{v_{1},v_{2}\\},t_{4})$ and
$(\\{v_{1},v_{3}\\},t_{5})$ is

$\hfill\sum_{\begin{subarray}{c}(\\{v_{4},v_{5}\\},t_{6})\in E\\\ v_{4}\neq
v_{5},w_{4,5,6}=1\\\ v_{4}\notin\\{v_{1},v_{2}\\}\\\
v_{5}\notin\\{v_{1},v_{3}\\}\end{subarray}}p_{\mathsf{A}}(\mathsf{I})\frac{\underline{b}_{\mathsf{TL}}(\mathbf{W^{\prime}};2)}{{\overline{f}_{\mathsf{TL}}(\mathbf{W})|\mathcal{S}(\mathbf{W})|}}\propto
b_{\mathsf{TL}}(G^{\prime},v_{1}v_{2}v_{3};1)\hfill$

and by 4.3 after the second b-rejection in step $10$, this probability is
proportional to $\underline{b}_{\mathsf{TL}}(\mathbf{W^{\prime}};1)$. Finally,
to show that the probability is equal over all choices of
$(\\{v_{1},v_{2}\\},t_{4})$, $(\\{v_{1},v_{3}\\},t_{5})$, observe that by 4.3,
we have

$\hfill\sum_{\begin{subarray}{c}(\\{v_{1},v_{2}\\},t_{4})\neq(\\{v_{1},v_{3}\\},t_{5})\in
N(v_{1})\\\ v_{1}\neq v_{2},w_{1,2,4}=1\\\ v_{1}\neq
v_{3},w_{1,3,5}=1\end{subarray}}p_{\mathsf{A}}(\mathsf{I})\frac{\underline{b}_{\mathsf{TL}}(\mathbf{W^{\prime}};1)\underline{b}_{\mathsf{TL}}(\mathbf{W^{\prime}};2)}{{\overline{f}_{\mathsf{TL}}(\mathbf{W})|\mathcal{S}(\mathbf{W})|}}\propto
b_{\mathsf{TL}}(G^{\prime},v_{1};0)=\underline{b}_{\mathsf{TL}}(\mathbf{W^{\prime}};0)\hfill$

and thus $G^{\prime}$ is produced with probability

$\hfill
p_{\mathsf{A}}(\mathsf{I})\frac{\underline{b}_{\mathsf{TL}}(\mathbf{W^{\prime}};0)\underline{b}_{\mathsf{TL}}(\mathbf{W^{\prime}};1)\underline{b}_{\mathsf{TL}}(\mathbf{W^{\prime}};2)}{{\overline{f}_{\mathsf{TL}}(\mathbf{W})|\mathcal{S}(\mathbf{W})|}}\hfill$

which only depends on $\mathbf{W}$, $\mathbf{W^{\prime}}$ and $\mathbf{D}$.

The proof of 3.9 requires showing that the upper and lower bounds for Stage 2
are correct. To this end, let
$\mathcal{M}_{1}(\mathbf{D})\subseteq\mathcal{M}_{0}(\mathbf{D})$ denote set
of temporal multigraphs which satisfy the initial conditions and which are
output by Stage 1, i.e. which contain no temporal single-loops. Then, we
obtain the following results.

######  Lemma 4.10.

For all $G\in\mathcal{S}(\mathbf{W})\subseteq\mathcal{M}_{1}(\mathbf{D})$ we
have

$\displaystyle
f_{\mathsf{TD}_{1}}(G)\leq\overline{f}_{\mathsf{TD}_{1}}(\mathbf{W}),$
$\displaystyle
f_{\mathsf{TD}_{0}}(G)\leq\overline{f}_{\mathsf{TD}_{0}}(\mathbf{W}).$

######  Proof 4.11.

There are at most $M^{2}$ choices for the (oriented) edges
$(\\{v_{3},v_{5}\\},t_{2})$, $(\\{v_{4},v_{6}\\},t_{3})$ and at most $T^{3}$
choices for the timestamps $t_{4},t_{5},t_{6}\in[1,T]$ needed to perform a
$\mathsf{TD}_{1}$ switching. The $\mathsf{TD}_{0}$ switching uses twice as
many edges and timestamps.

######  Lemma 4.12.

For all
$G^{\prime}\in\mathcal{S}(\mathbf{W^{\prime}})\subseteq\mathcal{M}_{1}(\mathbf{D})$
where $m_{3,5}<\mu$ and $m_{4,6}<\mu$ we have

$\displaystyle\underline{b}_{\mathsf{TD}_{1}}(\mathbf{W^{\prime}};2)\leq
b_{\mathsf{TD_{1}}}(G^{\prime},v_{1}\dots v_{6};2)\leq T^{2},$

for all
$G^{\prime}\in\mathcal{S}(\mathbf{W^{\prime}})\subseteq\mathcal{M}_{1}(\mathbf{D})$
where $m_{3,7},m_{4,8},m_{5,9},m_{6,10}<\mu$ we have

$\displaystyle\underline{b}_{\mathsf{TD}_{0}}(\mathbf{W^{\prime}};2)\leq
b_{\mathsf{TD_{0}}}(G^{\prime},v_{1}\dots v_{10};2)\leq T^{4}$

and for all
$G^{\prime}\in\mathcal{S}(\mathbf{W^{\prime}})\subseteq\mathcal{M}_{1}(\mathbf{D})$
we have

$\displaystyle\underline{b}_{\mathsf{TD}_{1}}(\mathbf{W^{\prime}};1)\leq
b_{\mathsf{TD_{1}}}(G^{\prime},v_{1}\dots v_{4};1)\leq M,$
$\displaystyle\underline{b}_{\mathsf{TD}_{0}}(\mathbf{W^{\prime}};1)\leq
b_{\mathsf{TD_{0}}}(G^{\prime},v_{1}\dots v_{6};1)\leq M^{2},$
$\displaystyle\underline{b}_{\mathsf{TD}_{1}}(\mathbf{W^{\prime}};0)=b_{\mathsf{TD_{1}}}(G^{\prime},v_{1}v_{2};0),$
$\displaystyle\underline{b}_{\mathsf{TD}_{0}}(\mathbf{W^{\prime}};0)=b_{\mathsf{TD_{0}}}(G^{\prime},v_{1}v_{2};0).$

######  Proof 4.13.

The first two sets of inequalities follow since there are at most $T$ and at
least $T-(\mu-1)$ available timestamps for each edge. For the third and fourth
sets of inequalities, observe that there are at most $M$ choices for an edge,
at most $4B_{D}$ choices such that the edge is not simple, and at most
$4\Delta$ choices such that the nodes are not distinct. The equalities follow
from the observation that $\mathbf{W^{\prime}}$ (in addition to $\mathbf{D}$)
determines the number of incident simple temporal edges at each node.

######  Lemma 4.14.

For all
$G^{\prime}\in\mathcal{S}(\mathbf{W^{\prime}})\subseteq\mathcal{M}_{1}(\mathbf{D})$
we have

$\displaystyle
f_{\mathsf{B}_{m,n}}(G^{\prime})\leq\overline{f}_{\mathsf{B}_{m,n}}(\mathbf{W^{\prime}}),$
$\displaystyle
f_{\mathsf{C}_{m,n,o,p}}(G^{\prime})\leq\overline{f}_{\mathsf{C}_{m,n,o,p}}(\mathbf{W^{\prime}}).$

######  Proof 4.15.

The number of edges and timestamps needed for the $\mathsf{B}_{m,n}$ switching
is $2(m+n)$, the number of edges and timestamps needed for the
$\mathsf{C}_{m,n,o,p}$ switching is $2(m+n+o+p)$, and there are at most
$\Delta$ choices for each incident edge, and at most $T$ choices for each
timestamp.

######  Lemma 4.16.

For all
$G^{\prime\prime}\in\mathcal{S}(\mathbf{W^{\prime}})\subseteq\mathcal{M}_{1}(\mathbf{D})$
we have

$\displaystyle\underline{b}_{\mathsf{B}_{m,n}}(\mathbf{W^{\prime}})\leq
b_{\mathsf{B}_{m,n}}(G^{\prime\prime},v_{1}\dots v_{6})\leq
M^{m+n}T^{2(m+n)},$
$\displaystyle\underline{b}_{\mathsf{C}_{m,n,o,p}}(\mathbf{W^{\prime}})\leq
b_{\mathsf{C}_{m,n,o,p}}(G^{\prime\prime},v_{1}\dots v_{10})\leq
M^{m+n+o+p}T^{2(m+n+o+p)}.$

######  Proof 4.17.

The number of edges and timestamps needed to reverse the $\mathsf{B}_{m,n}$
switching is $m+n$ and $2(m+n)$, the number of edges and timestamps needed to
reverse the $\mathsf{C}_{m,n,o,p}$ switching is $m+n+o+p$ and $2(m+n+o+p)$.
There are at most $M$ choices for each edge, at most $4B_{D}$ choices such
that the edge is not simple, and at most $2\Delta$ choices for each node
already chosen such that the nodes are not distinct. Finally, there are at
most $T$ and at least $T-(\Delta-1)$ choices for each timestamp such that the
edge does not exist in $G^{\prime\prime}$.

######  Proof 4.18 (Proof of 3.9).

Using 4.10, 4.12, 4.14, and 4.16 in a similar style argument as in the proof
of 3.4, after removing a temporal double-edge between two nodes $v_{1}$ and
$v_{2}$ in step $5$, a given graph
$G^{\prime}\in\mathcal{S}(\mathbf{W^{\prime}})$ is produced with probability

$\hfill
p(\mathsf{TD}_{1})p_{\mathsf{B}}(\mathsf{I})\frac{\underline{b}_{\mathsf{TD}_{1}}(\mathbf{W^{\prime}};0)\underline{b}_{\mathsf{TD}_{1}}(\mathbf{W^{\prime}};1)\underline{b}_{\mathsf{TD}_{1}}(\mathbf{W^{\prime}};2)}{\overline{f}_{\mathsf{TD}_{1}}(\mathbf{W})|\mathcal{S}(\mathbf{W})|}\hfill$

if $m_{1,2}(G^{\prime})=1$ and with probability

$\hfill
p(\mathsf{TD}_{0})p_{\mathsf{C}}(\mathsf{I})\frac{\underline{b}_{\mathsf{TD}_{0}}(\mathbf{W^{\prime}};0)\underline{b}_{\mathsf{TD}_{0}}(\mathbf{W^{\prime}};1)\underline{b}_{\mathsf{TD}_{0}}(\mathbf{W^{\prime}};2)}{\overline{f}_{\mathsf{TD}_{0}}(\mathbf{W})|\mathcal{S}(\mathbf{W})|}\hfill$

if $m_{1,2}(G^{\prime})=0$. Specifying the probabilities $p(\mathsf{TD}_{1})$
and $p(\mathsf{TD}_{0})$ as done for Stage 2 then suffices to equalize the
probabilities over all graphs in $\mathcal{S}(\mathbf{W^{\prime}})$.

We are now able to show the following.

######  Lemma 4.19.

Given a tuple $\mathbf{D}=(\mathbf{d},T)$ as input, T-Gen outputs a uniform
random sample $G\in\mathcal{G}(\mathbf{D})$.

######  Proof 4.20.

If the initial graph $G$ is simple, then the claim follows by Theorem 2.1.
Otherwise the initial graph $G$ is uniformly distributed in the set
$\mathcal{S}(\mathbf{W}(G))\subseteq\mathcal{M}(\mathbf{D})$ for some
$\mathbf{W}(G)\neq\mathbf{0}^{n\times n\times T}$. If $G$ satisfies the
initial conditions, then all entries $\mathbf{W}(G)_{i,i,t}$ are either $0$ or
$1$ and all entries $\mathbf{W}(G)_{i,j,t}$ such that $i\neq j$ are either $0$
or $2$. Now, it is straightforward to check that each iteration of Stage 1
corresponds to a map
$\mathcal{S}(\mathbf{W})\to\mathcal{S}(\mathbf{W^{\prime}})$ where
$\mathbf{W^{\prime}}$ is the tensor obtained from $\mathbf{W}=\mathbf{W}(G)$
by setting exactly one entry $\mathbf{W}_{i,i,t}=1$ to $0$, and Stage 1 ends
once all such entries have been set to $0$. Similarly, each iteration of Stage
2 corresponds to a map
$\mathcal{S}(\mathbf{W})\to\mathcal{S}(\mathbf{W^{\prime}})$ where
$\mathbf{W^{\prime}}$ is the tensor obtained from $\mathbf{W}$ by setting
exactly two entries $\mathbf{W}_{i,j,t}=\mathbf{W}_{j,i,t}=2$ where $i\neq j$
to $0$, and Stage 2 ends once all such entries have been set to $0$. Thus,
after Stage 1 and Stage 2 end, the final graph $G$ is a simple temporal graph
with $\mathbf{W}(G)=\mathbf{0}^{n\times n\times T}$, and by 3.4 and 3.9, this
graph is uniformly distributed in $\mathcal{S}(\mathbf{0}^{n\times n\times
T})=\mathcal{G}(\mathbf{D})$ as claimed.

We move on to the run time proof.

###  4.2 Runtime of T-Gen

The following additional results are needed for the proofs of 3.1, 3.5, 3.10,
3.6, and 3.11.

######  Lemma 4.21.

Given that $\Delta^{2+\epsilon}=O(M)$ for a constant $\epsilon>0$ and
$T-\Delta=\Omega(T)$, we have $p_{\mathsf{A}}(\mathsf{I})=1-o(\Delta^{-1})$.

######  Proof 4.22.

Let $k=m+n$. Then, the probability of choosing a type $\mathsf{A}_{m,n}$
switching is at most

$\hfill
p(\mathsf{A}_{m,n})=p_{\mathsf{A}}(\mathsf{I})\frac{\overline{f}_{\mathsf{A}_{m,n}}(\mathbf{W^{\prime}})}{\underline{b}_{\mathsf{A}_{m,n}}(\mathbf{W^{\prime}})}<\frac{\Delta^{2k}T^{2k}}{(M-B_{L}-B_{D}-4(k+3)\Delta)^{k}(T-(\Delta-1))^{2k}}.\hfill$

Now, if $\Delta^{2+\epsilon}=O(M)$ and $T-\Delta=\Omega(T)$, then

$\hfill\frac{\Delta^{2k}T^{2k}}{(M-B_{L}-B_{D}-4(k+3)\Delta)^{k}(T-(\Delta-1))^{2k}}=O\left(\Delta^{-\epsilon
k}\right)=o(\Delta^{-k/\mu})\hfill$

by $B_{L}+B_{D}+4(k+3)\Delta=O(\Delta^{2})=o(M)$ and $\epsilon>\frac{1}{\mu}$.
Thus, the type $\mathsf{I}$ switching is chosen with probability at least

$\hfill p_{\mathsf{A}}(\mathsf{I})=1-\sum_{\begin{subarray}{c}0\leq
m,n<\Delta\\\
\mu\leq\max\\{m,n\\}\end{subarray}}p_{\mathsf{A}}(\mathsf{A}_{m,n})>1-\sum_{\mu\leq
k<2\Delta}\binom{k+1}{1}o\left(\Delta^{-k/\mu}\right)=1-o\left(\Delta^{-1}\right)\hfill$

as claimed.

######  Lemma 4.23.

Given that $\Delta^{2+\epsilon}=O(M)$ for a constant $\epsilon>0$ and
$T-\Delta=\Omega(T)$, we have $p_{\mathsf{B}}(\mathsf{I})=1-o(\Delta^{-1})$
and $p_{\mathsf{C}}(\mathsf{I})=1-o(\Delta^{-1})$.

######  Proof 4.24.

By a similar argument as in the proof of 4.21.

######  Proof 4.25 (Proof of 3.1).

By 2.5, the highest multiplicity of any ordinary multi-edge in the initial
graph is at most $\eta=\lfloor 2+2/\epsilon\rfloor$ with high probability. To
complete the proof, we show that with high probability no two edges created
due to switchings share the same node set, which in turn implies that the
highest multiplicity of any ordinary multi-edge is $\eta+1=\lfloor
3+2/\epsilon\rfloor:=\mu$.

First, observe that 4.21 and 4.23 imply that the probability of performing at
least one auxiliary switching in either of Stage 1 or Stage 2 is at most
$(B_{L}+B_{D})o(\Delta^{-1})=o(1)$. With the remaining probability, only
$\mathsf{TL}$, $\mathsf{TD}_{1}$, and $\mathsf{TD}_{0}$ switchings are
performed. The $\mathsf{TL}$ switching creates three edges with node sets
$\\{v_{1},v_{2}\\}$, $\\{v_{1},v_{3}\\}$ and $\\{v_{4},v_{5}\\}$ where $v_{1}$
is incident with a temporal single-loop, and where $v_{2}$ and $v_{4}$,
$v_{3}$ and $v_{5}$ are determined by choosing the switching uniformly at
random which implies that these nodes are incident with edges
$(\\{v_{2},v_{4}\\},t_{2})$, $(\\{v_{3},v_{5}\\},t_{3})$ chosen uniformly at
random among all edges which satisfy the conditions. Likewise, the
$\mathsf{TD}_{1}$ switching creates three edges with node sets
$\\{v_{1},v_{3}\\}$, $\\{v_{2},v_{4}\\}$ and $\\{v_{5},v_{6}\\}$ where $v_{1}$
and $v_{2}$ are incident with a temporal double-edge, $v_{3}$ and $v_{5}$,
$v_{4}$ and $v_{6}$ are incident with edges satisfying the conditions chosen
uniformly at random, and the $\mathsf{TD}_{0}$ switching adds two such sets of
edges. Now, observe that when performing a $\mathsf{TL}$ switching at some
node $v_{1}$, there are at least $M-2B_{L}-4B_{D}-2\Delta$ choices for the
edge $(\\{v_{2},v_{4}\\},t_{2})$ and at least $M-2B_{L}-4B_{D}-3\Delta$
choices for the second edge $(\\{v_{3},v_{5}\\},t_{3})$. Thus, the probability
that a given node $v$ with degree $d$ takes on the role of one of $v_{2}$,
$v_{3}$, $v_{4}$, $v_{5}$ in such a switching chosen uniformly at random is at
most

$\hfill\frac{2d}{M-2B_{L}-4B_{D}-2\Delta}+\frac{2d}{M-2B_{L}-4B_{D}-3\Delta}=O\left(\frac{\Delta}{M}\right)\hfill$

due to $d\leq\Delta$ and $O(B_{L}+B_{D}+\Delta)=o(M)\implies
M-O(B_{L}-B_{D}-\Delta)=\Omega(M)$. Similar calculations give the same
asymptotic probability of a given node being involved in a $\mathsf{TD}_{1}$
or $\mathsf{TD}_{0}$ switching.

This leads to the following bounds on the probability of creating two edges
with the same node set in terms of the number of iterations of a stage
performed. Fix any stage, and any node $v$, and let $i$ denote the number of
iterations performed overall, and $j$ the number of iterations performed such
that the non-simple edge removed is incident at $v$. Then, the number of edges
created overall is $O(i)$ and the expected number of edges created which are
incident at $v$ is $O(j+i\Delta/M)$. Thus, the probability that the next
switching performed at $v$ creates an edge which shares the same node set as
any edges created prior is $O(i\Delta^{2}/M^{2})$ for edges not incident at
$v$, and $O(j\Delta/M+i\Delta^{2}/M^{2})$ for edges incident at $v$.

Now, recall that by the initial conditions, there are at most $\lambda=O(1)$
incident temporal single-loops and at most $\kappa=O(1)$ incident temporal
double-edges at any node, and at most $B_{L}=M_{2}/M=O(\Delta)$ temporal
single-loops and at most $B_{D}=M_{2}^{2}/MT=O(\Delta^{2}/T)$ temporal double-
edges overall. Then, starting with Stage 1, the probability of creating two
edges with share the same node set due to any of the $\mathsf{TL}$ switchings
is at most

$\displaystyle\sum_{1\leq i\leq B_{L}}\sum_{1\leq
j\leq\lambda}\left(O\left(i\frac{\Delta^{2}}{M^{2}}\right)+O\left(j\frac{\Delta}{M}+i\frac{\Delta^{2}}{M^{2}}\right)\right)$
$\displaystyle<B_{L}\lambda\left(O\left(B_{L}\frac{\Delta^{2}}{M^{2}}\right)+O\left(\lambda\frac{\Delta}{M}\right)\right)$
$\displaystyle=O\left(\frac{\Delta^{4}}{M^{2}}+\frac{\Delta^{2}}{M}\right)$
$\displaystyle=o(1)$

by $B_{L}=O(\Delta)$, $\lambda=O(1)$, and $\Delta^{2+\epsilon}=O(M)$.
Likewise, for Stage 2, the probability of creating two edges with share the
same node set due to any of the $\mathsf{TD}_{1}$ or $\mathsf{TD}_{0}$
switchings is at most

$\displaystyle\begin{aligned} \quad\quad\sum_{1\leq i\leq B_{D}}&\sum_{1\leq
j\leq\kappa}\left(O\left(\left(B_{L}+i\right)\frac{\Delta^{2}}{M^{2}}\right)+O\left(\left(\lambda+j\right)\frac{\Delta}{M}+\left(B_{L}+i\right)\frac{\Delta^{2}}{M^{2}}\right)\right)\\\
&<B_{D}\kappa\left(O\left(\left(B_{L}+B_{D}\right)\frac{\Delta^{2}}{M^{2}}\right)+O\left(\left(\lambda+\kappa\right)\frac{\Delta}{M}\right)\right)\\\
&=O\left(\frac{\Delta^{6}}{T^{2}M^{2}}+\frac{\Delta^{5}}{TM^{2}}+\frac{\Delta^{3}}{TM}\right)\\\
&=o(1)\end{aligned}$

by $B_{D}=O(\Delta^{2}/T)$, $\kappa=O(1)$, $\Delta=O(T)$ and
$\Delta^{2+\epsilon}=O(M)$.

######  Proof 4.26 (Proof of 3.5).

By 4.21 the probability that Stage 1 restarts in steps $9a-f$ is smaller than
$B_{L}o(\Delta^{-1})=o(1)$ and by 3.1 we can assume that the highest
multiplicity of an edge in $G$ is at most $\mu$. Hence, the probability of not
restarting is at most the probability of not f- or b-rejecting in steps $3$,
$7$ or $10$ under this assumption.

The probability of an f-rejection in step $3$ equals the probability of
choosing edges $(\\{v_{2},v_{4}\\},t_{2})$, $(\\{v_{3},v_{5}\\},t_{3})$ and
timestamps $t_{4},t_{5},t_{6}\in[1,T]$ which do not fulfill the conditions
defined for the $\mathsf{TL}$ switching. For each edge, this probability is at
most $(2B_{L}+4B_{D}+3\Delta)/M$ as there are at least $M$ choices for each
(oriented) edge, at most $2B_{L}$ choices for a loop, at most $4B_{D}$ choices
for an edge contained in a temporal double-edge and at most $3\Delta$ choices
for an edge such that $v_{2},v_{3},v_{4},v_{5}$ is not distinct from $v_{1}$
or $v_{4}$ is not distinct from $v_{5}$. For the timestamps, we can assume
that $m_{1,2},m_{1,3},m_{4,5}\leq\mu$ so for each timestamp the probability of
a rejection is at most $(\mu-1)/T$. Then, the probability of not f-rejecting
in a given iteration is at least

$\hfill\frac{(M-2B_{L}-4B_{D}-3\Delta)^{2}(T-(\mu-1))^{3}}{M^{2}T^{3}}=\left(1-O\left(\frac{\Delta}{M}\right)\right)^{2}\left(1-O\left(\frac{\mu}{T}\right)\right)^{3}.\hfill$

In addition, by 4.3, the probability of a b-rejection in step $7$ is at most
$(\mu-1)/T$ for each timestamp, and the probability of a b-rejection in step
$10$ is at most $(2B_{L}+4B_{D}+4\Delta)/M$. Thus, the probability of not
b-rejecting in a given iteration is at least

$\hfill\frac{(M-2B_{L}-4B_{D}-4\Delta)(T-(\mu-1))^{2}}{MT^{2}}=\left(1-O\left(\frac{\Delta}{M}\right)\right)\left(1-O\left(\frac{\mu}{T}\right)\right)^{2}.\hfill$

Finally, by the initial conditions there are at most $B_{L}=M_{2}/M<\Delta$
iterations of Stage 1, and by using $\mu=O(1)$, the probability that the
algorithm does not restart in Stage 1 is at least

$\hfill\left(\left(1-O\left(\frac{\Delta}{M}\right)\right)^{2}\left(1-O\left(\frac{\mu}{T}\right)\right)^{3}\right)^{B_{L}}=\exp\left(-O\left(\frac{\Delta^{2}}{M}\right)-O\left(\frac{\Delta}{T}\right)\right).\hfill\qed$

######  Proof 4.27 (Proof of 3.6).

By the initial conditions, there are at most $B_{L}=M_{2}/M<\Delta$ iterations
of Stage 1. Thus, the claim follows if an iteration runs in expected time
$O(\Delta)$. The steps of an iteration which require attention are the
f-rejection in step $3$, the b-rejections in step $7$ and $10$, choosing an
auxiliary switching in steps $8-9$, the f-rejection in step $9c$, and the
b-rejection in step $9f$.

First, note that as observed by [1], there is a simple trick to implement an
f-rejection step at little additional cost. In the case of step $3$, it
suffices to choose the two edges and three timestamps required for the
$\mathsf{TL}$ switching uniformly at random and restart if those choices do
not satisfy the conditions given in 3.2. Then, since there are
$\overline{f}_{\mathsf{TL}}(\mathbf{W})=M^{2}T^{3}$ ways to choose two
(oriented) edges and three timestamps and $f_{\mathsf{TL}}(G)$ choices yield a
switching which can be performed on the current graph $G$, we restart with the
desired probability of
$f_{\mathsf{TL}}(G)/\overline{f}_{\mathsf{TL}}(\mathbf{W})$.

The b-rejections in step $7$ and $10$ require computing the quantities
$b_{\mathsf{TL}}(G^{\prime},v_{1}v_{2}v_{3}v_{4}v_{5};2)$, and
$b_{\mathsf{TL}}(G^{\prime},v_{1}v_{2}v_{3};1)$,
$b_{\mathsf{TL}}(G^{\prime},v_{1};0)$. Computing
$b_{\mathsf{TL}}(G^{\prime},v_{1}v_{2}v_{3}v_{4}v_{5};2)$ only requires look
ups of the multiplicities of $\\{v_{2},v_{4}\\}$ and $\\{v_{3},v_{5}\\}$ which
take time $O(1)$ if the implementation maintains a data structure to store the
multiplicity of the edges in the graph. To compute
$b_{\mathsf{TL}}(G^{\prime},v_{1}v_{2}v_{3};1)$, it suffices to iterate trough
the lists of incident edges at nodes $v_{1}$, $v_{2}$, $v_{3}$ and subtract
the number of simple edges which collide with those nodes from the total
number of simple edges, which takes time $O(\Delta)$. Additionally, computing
$b_{\mathsf{TL}}(G^{\prime},v_{1};0)$ can be implemented in time $O(1)$ by
maintaining the number of simple edges incident at each node.

Computing the type distribution for steps $8-9$ naively would take time
$\Theta(\Delta^{2})$, but there is a simple trick to speed-up the computation.
Re-purposing the proof of 4.21, we see that

$\hfill\sum_{\begin{subarray}{c}0\leq m,n<\Delta\\\ \mu\leq\max\\{m,n\\}\\\
m+n=k\end{subarray}}p_{\mathsf{A}}(\mathsf{A}_{m,n})<\binom{k+1}{1}p_{\mathsf{A}}(\mathsf{A}_{k,0})<\binom{k+1}{1}\frac{\overline{f}_{\mathsf{A}_{k,0}}(\mathbf{W})}{\underline{b}_{\mathsf{A}_{k,0}}(\mathbf{W^{\prime}})}=:\overline{p}_{\mathsf{A}}(\mathsf{A}_{k}).\hfill$

Thus, in time $O(\Delta)$, we can compute

$\hfill\underline{p}_{\mathsf{A}}(\mathsf{I}):=1-\sum_{\mu\leq
k<2\Delta-1}\overline{p}_{\mathsf{A}}(\mathsf{A}_{k})\hfill$

as a lower bound on the probability of performing the identity switching, and
with this probability step $9$ can be skipped. Otherwise, if one of the
auxiliary switchings $\mathsf{A}_{m,n}$ where $m+n=k$ is chosen, then we
compute the exact probabilities of these at most $k+1=O(\Delta)$ switchings,
and either choose a switching in accordance with the exact probabilities or
restart the algorithm with probability

$\hfill 1-\sum_{\begin{subarray}{c}0\leq m,n<\Delta\\\ \mu\leq\max\\{m,n\\}\\\
m+n=k\end{subarray}}\frac{p_{\mathsf{A}}(\mathsf{A}_{m,n})}{\overline{p}_{\mathsf{A}}(\mathsf{A}_{k})}\hfill$

to correct for the overestimate.

Finally, by 4.21 the probability that steps $9a-f$ are executed is at most
$o(\Delta^{-1})$, so it suffices if these steps can be implemented in time
$O(\Delta^{2})$. For the f-rejection in step $9c$, we first pick the incident
edges of $v_{2}$ and $v_{4}$ and the timestamps uniformly at random, and then
restart if these choices do not satisfy the conditions in step 3.3. This
results in a restart probability of
$f_{\mathsf{A}_{m,n}}(G^{\prime})/(d_{2}^{m}d_{4}^{n}T^{2(m+n)})$, and to
reach the desired probability of
$f_{\mathsf{A}_{m,n}}(G^{\prime})/\overline{f}_{\mathsf{A}_{m,n}}(\mathbf{W^{\prime}})$,
it suffices to restart with probability
$1-(d_{2}^{m}d_{4}^{n}T^{2(m+n)})/(\Delta T)^{2(m+n)}$ afterwards. To
implement the b-rejection in step $9f$, we need to compute
$b_{\mathsf{A}_{m,n}}(G^{\prime\prime},v_{1}v_{2}v_{3}v_{4}v_{5})$ which is
the number of $\mathsf{A}_{m,n}$ switchings which can produce the graph
$G^{\prime\prime}$. As this is equal to the number of ways to reverse an
$\mathsf{A}_{m,n}$ switching on the graph $G^{\prime\prime}$, we can compute
this quantity as the number of choices for $m$ and $n$ edges between
$v_{2},v_{4}$ and $v_{3},v_{5}$, respectively, $m+n$ additional edges, and
$2(m+n)$ timestamps which satisfy the conditions. Computing the number of
choices for the edges between $v_{2},v_{4}$ and $v_{3},v_{5}$ can be done in
time $O(1)$ by looking up the number of simple edges between these nodes.
Choosing an additional edge, and checking if it satisfies the conditions, e.g.
if it is simple, and does not share nodes with the other edges, takes time
$O(1)$ for the first edges chosen and time $O(\Delta)$ for the last edges, so
for all $m+n<2\Delta-1$ edges this takes at most time $O(\Delta^{2})$.
Finally, computing the number of available timestamps again only requires
looking up the multiplicities of $2(m+n)=O(\Delta)$ edges and takes time
$O(\Delta)$.

######  Proof 4.28 (Proof of 3.10).

By 4.23 the probability that Stage 2 restarts in steps $6ei-vi$ or $7ei-vi$ is
smaller than $B_{D}o(\Delta^{-1})=o(1)$ and by 3.1 we can assume that the
highest multiplicity of an edge in $G$ is at most $\mu$. Hence, the
probability of not restarting is at most the probability of not f- or
b-rejecting in steps $4$, $6c$, $6f$, $7c$ or $7f$ under this assumption.
Furthermore, it is straightforward to check that the probability of f- or
b-rejecting in a given iteration is larger if $\theta=\mathsf{TD}_{0}$ so we
focus on this case.

Using a similar argument as for 3.5, the probability of not f-rejecting in
step $3$ of a given iteration is at least

$\hfill\frac{(M-4B_{D}-5\Delta)^{4}(T-(\mu-1))^{6}}{M^{4}T^{6}}=\left(1-O\left(\frac{\Delta}{M}\right)\right)^{4}\left(1-O\left(\frac{\mu}{T}\right)\right)^{6}.\hfill$

In addition, by 4.12 and 4.14, the probability of a b-rejection in step $6c$
or $7c$ is at most $(\mu-1)/T$ for each timestamp, and the probability of a
b-rejection in step $6f$ or $7f$ is at most $(4B_{D}+4\Delta)/M$. Then, the
probability of not b-rejecting in a given iteration is at least

$\hfill\frac{(M-4B_{D}-4\Delta)^{2}(T-(\mu-1))^{4}}{M^{2}T^{4}}=\left(1-O\left(\frac{\Delta}{M}\right)\right)^{2}\left(1-O\left(\frac{\mu}{T}\right)\right)^{4}.\hfill$

Finally, by the initial conditions there are at most
$B_{D}=M_{2}^{2}/MT<\Delta^{2}/T$ iterations of Stage 2, and thus the
probability that the algorithm does not restart in Stage 2 is at least

$\hfill\left(\left(1-O\left(\frac{\Delta}{M}\right)\right)^{4}\left(1-O\left(\frac{\mu}{T}\right)\right)^{6}\right)^{B_{D}}=\exp\left(-O\left(\frac{\Delta^{3}}{MT}\right)-O\left(\frac{\Delta^{2}}{T^{2}}\right)\right).\hfill\qed$

######  Proof 4.29 (Proof of 3.11).

By the initial conditions, there are at most $B_{D}=M_{2}^{2}/MT<\Delta^{2}/T$
iterations of Stage 2, so the claim follows if an iteration runs in expected
time $O(\Delta)$. We focus on the f-rejection in step $4$, the b-rejections in
steps $6c$, $6f$ and $7c$, $7f$, choosing an auxiliary switching in steps
$6d-e$ and $7d-e$, the f-rejections in step $6eiii$ and $7eiii$, and the
b-rejections in step $6ev$ and $7ev$.

To implement the f-rejection in step $4$, it again suffices to choose the two
(or four) edges and three (or six) timestamps needed for the $\mathsf{TD}_{1}$
or $\mathsf{TD}_{0}$ switching uniformly at random and restart if those
choices do not satisfy the conditions given in 3.7. By similar arguments as in
the proof of 3.6, the quantities needed for the b-rejections in step $6c$,
$6f$ and $7c$, $7f$ can be computed in time $O(\Delta)$.

To choose an auxiliary switching in steps $6d-e$ the method described in the
proof of 3.6 can be re-used. For steps $7d-e$, define

$\hfill\sum_{\begin{subarray}{c}0\leq m,n,o,p\leq\Delta\\\
\mu<\max\\{m,n,o,p\\}\\\
m+n+o+p=k\end{subarray}}p_{\mathsf{C}}(\mathsf{C}_{m,n,o,p})<\binom{k+1}{3}\frac{\overline{f}_{\mathsf{C}_{k,0,0,0}}(\mathbf{W})}{\underline{b}_{\mathsf{C}_{k,0,0,0}}(\mathbf{W^{\prime}})}=:\overline{p}_{\mathsf{C}}(\mathsf{C}_{k}).\hfill$

Then, we can compute

$\hfill\underline{p}_{\mathsf{C}}(\mathsf{I}):=1-\sum_{\mu\leq
k<4\Delta-3}\overline{p}_{\mathsf{C}}(\mathsf{C}_{k})\hfill$

in time $O(\Delta)$. To efficiently choose one of the switchings where
$m+n+o+p=k$, observe that $p_{\mathsf{C}}(\mathsf{C}_{m,n,o,p})$ only depends
on $k$ and not the individual choices of $m,n,o,p$, thus, it suffices to
compute the exact probability for one of the switchings, and the exact number
of switchings, and then follow the steps described in the proof of 3.6.

By 4.23 the probability that steps $6ev$ or $7ev$ are executed is at most
$o(\Delta^{-1})$, so it suffices if these steps can be implemented in time
$O(\Delta^{2})$. This is possible by following the steps described towards the
end of the proof of 3.6 with the necessary modifications.

The following shows the efficiency of T-Gen.

######  Lemma 4.30.

T-Gen runs in expected time $O(M)$ for a tuple $\mathbf{D}=(\mathbf{d},T)$
which satisfies $\Delta^{2+\epsilon}=O(M)$ for a constant $\epsilon>0$ and
$T-\Delta=\Omega(T)$.

######  Proof 4.31.

By 2.3 and 2.5 the algorithm restarts at most $O(1)$ times before finding a
multigraph which satisfies the initial conditions. In addition, if the initial
multigraph satisfies the conditions, then by 3.5 and 3.10, the algorithm
restarts at most $O(1)$ times during Stage 1 and Stage 2. The run time of the
temporal configuration model is $O(M)$, and if the initial multigraph
satisfies the conditions, then by 3.6 and 3.11, the combined runtime of both
Stage 1 and Stage 2 is $O(\Delta^{3}/T)+O(\Delta^{2})=O(M)$.

###  4.3 Proof of Theorem 1.2

######  Proof 4.32 (Proof of Theorem 1.2).

The claim follows by 4.19 and 4.30.

##  5 Future Directions

It would be interesting to loosen the condition on the maximum degree $\Delta$
in terms of the lifetime $T$. Additionally, there are other parameters which
could be incorporated into the model. For instance, it could be useful to fix
the number of edges assigned to each timestamp, or to specify desired
multiplicities for the edges.

## References

  * [1] B. D. McKay and N. C. Wormald.  Uniform generation of random regular graphs of moderate degree.  J. Algorithms, 11(1), 1990.
  * [2] N. J. Gotelli and G. R. Graves.  Null models in ecology.  Smithsonian Institution, 1996.
  * [3] J. K. Blitzstein and P. Diaconis.  A sequential importance sampling algorithm for generating random graphs with prescribed degrees.  Internet Math., 6(4):489–522, 2011.
  * [4] A. Sinclair and M. Jerrum.  Approximate counting, uniform generation and rapidly mixing markov chains.  Inf. Comput., 82(1):93–133, 1989.
  * [5] P. Holme and J. Saramäki.  Temporal networks.  Physics reports, 519(3):97–125, 2012.
  * [6] A. Casteigts, P. Flocchini, W. Quattrociocchi, and N. Santoro.  Time-varying graphs and dynamic networks.  International Journal of Parallel, Emergent and Distributed Systems, 27(5):387–408, 2012.
  * [7] A.-L. Barabási.  The origin of bursts and heavy tails in human dynamics.  Nature, 435(7039):207–211, 2005.
  * [8] U. Harder and M. Paczuski.  Correlated dynamics in human printing behavior.  Physica A: Statistical Mechanics and its Applications, 361(1):329–336, 2006.
  * [9] V. Havel.  A remark on the existence of finite graphs.  Casopis Pest., Mat., 80:477–480, 1955.
  * [10] S. L. Hakimi.  On realizability of a set of integers as degrees of the vertices of a linear graph. i.  Journal of the Society for Industrial and Applied Mathematics, 10(3):496–506, 1962.
  * [11] E. A. Bender and E. R. Canfield.  The asymptotic number of labeled graphs with given degree sequences.  J. Comb. Theory, Ser. A, 24(3):296–307, 1978.
  * [12] B. Bollobás.  A probabilistic proof of an asymptotic formula for the number of labelled regular graphs.  Eur. J. Comb., 1(4):311–316, 1980.
  * [13] N. C. Wormald.  Generating random regular graphs.  J. Algorithms, 5(2):247–280, 1984.
  * [14] B. D. McKay.  Asymptotics for symmetric 0-1 matrices with prescribed row sums.  Ars Combinatoria, 19:15–25, 1985.
  * [15] A. Arman, P. Gao, and N. C. Wormald.  Fast uniform generation of random graphs with given degree sequences.  Random Struct. Algorithms, 59(3):291–314, 2021.
  * [16] P. Gao and N. C. Wormald.  Uniform generation of random regular graphs.  SIAM J. Comput., 46(4):1395–1427, 2017.
  * [17] P. Gao and N. C. Wormald.  Uniform generation of random graphs with power-law degree sequences.  In Artur Czumaj, editor, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 1741–1758. SIAM, 2018.
  * [18] F. Chung and L. Lu.  Connected components in random graphs with given expected degree sequences.  Annals of Combinatorics, 6(2), 2002.
  * [19] J. C. Miller and A. A. Hagberg.  Efficient generation of networks with given expected degrees.  In Alan M. Frieze, Paul Horn, and Pawel Pralat, editors, Algorithms and Models for the Web Graph - 8th International Workshop, WAW 2011, Atlanta, GA, USA, May 27-29, 2011. Proceedings, pages 115–126, 2011.
  * [20] M. Jerrum and A. Sinclair.  Fast uniform generation of regular graphs.  Theor. Comput. Sci., 73(1):91–100, 1990.
  * [21] A. R. Rao, R. Jana, and S. Bandyopadhyay.  A Markov Chain Monte Carlo method for generating random $(0,1)$-matrices with given marginals.  Sankhyā: The Indian J. of Statistics A, 58, 1996.
  * [22] J. Y. Zhao.  Expand and contract: Sampling graphs with given degrees and other combinatorial families.  CoRR, abs/1308.6627, 2013.
  * [23] P. L. Erdös, C. S. Greenhill, T. R. Mezei, I. Miklós, D. Soltész, and L. Soukup.  The mixing time of switch markov chains: A unified approach.  Eur. J. Comb., 99:103421, 2022.
  * [24] C. Greenhill.  Generating graphs randomly.  Surveys in Combinatorics 2021, London Mathematical Society Lecture Notes Series 470:133–186, 2021.