- This event has passed.
Eindhoven SPOR Seminar
Sep 13, 2022, 15:45 - 16:45
Rik Versendaal (UU)
Sampling simple random graphs under degree and edge-weight constraints
In , 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  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 .
 Mohsen Bayati, Jeong Han Kim, and Amin Saberi. “A sequential algorithm for generating random graphs”. In: Algorithmica 58.4 (2010), pp. 860–910.
 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/.