Rik Versendaal (UU)
Sampling simple random graphs under degree and edge-weight constraints

ABSTRACT:

In [1], the problem was studied of sampling simple random graphs with degree constraints, which is typically a hard problem. Therefore, the authors proposed a sequential algorithm that samples such graphs asymptotically uniformly at random, when the number n of vertices tends to infinity.

In this talk, we will extend the algorithm in [1] to also include edge-weights. More specifically, we first assign random weights to all edges according to some probability distribution  and consider some target edge-weight distribution  . We then aim to sample random graphs satisfying some prescribed degree sequence, while additionally having empirical edge-weight distribution close to the target distribution .

We make this statement precise by proving that with high probability the empirical edge-weight distribution of the random graph produced by our algorithm is close to  in Wasserstein distance. The key assumption for this is that the target edge-weight distribution is not too large compared to the distribution  of the edge-weights, i.e.,  for some constant . This constant is allowed to grow moderately with , being  for some . The proof of this result mainly relies on a variety of concentration inequalities.
Finally, we will discuss what happens in the boundary case where . This for example occurs when studying graphs under geometric constraints in the box , where the connection threshold is in the critical regime, i.e., of order .

Based on work together with Ivan Kryven. Preprint available on ArXiv [2].

[1] Mohsen Bayati, Jeong Han Kim, and Amin Saberi. “A sequential algorithm for generating random graphs”. In: Algorithmica 58.4 (2010), pp. 860–910.

[2] Ivan Kryven and Rik Versendaal. “Sequential construction of spatial networks with arbitrary degree sequence and edge length distribution”. In: ArXiv preprint (2022). url: https://arxiv.org/abs/2207.08527.

For upcoming events of the SPOR seminar, as well as a history of previous talks, see: https://www.eurandom.tue.nl/eindhoven-spor-seminar/.