Uniform Generation of Temporal Graphs with Given Degrees

Publication date 19 April 2023

Abstract: Uniform sampling from the set

m a t h c a l G (m a t h b f d)

of graphs with a given degree-sequence

m a t h b f d = (d_{1}, d o t s, d_{n}) i n m a t h b b 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

m a t h b f D = (m a t h b f d, T) i n m a t h b b N^{n} i m e s m a t h b b N_{> 0}

and the task is to output a uniform random sample from the set

m a t h c a l G (m a t h b f D)

of temporal graphs with degree-sequence

m a t h b f d

and timestamps in the interval

[1, T]

. By allowing repeated edges with distinct timestamps,

m a t h c a l G (m a t h b f D)

can be non-empty even if

m a t h c a l G (m a t h b f d)

is, and as a consequence, existing algorithms are difficult to apply. We describe an algorithm for this generation problem which runs in expected time

O (M)

if

D e l t a^{2 + e p s i l o n} = O (M)

for some constant

e p s i l o n > 0

and

T - D e l t a = O m e g a (T)

where

M = s u m_{i} d_{i}

and

D e l t a = m a x_{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.

This page was built for publication: Uniform Generation of Temporal Graphs with Given Degrees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6433634)