- This event has passed.
Eindhoven SPOR Seminar
May 17, 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 .
This seminar will be hosted in a hybrid fashion; you are welcome to attend the talk either on-campus or via Zoom. The on-campus location will be announced later. The Zoom link is attached to the bottom of the invitation text.
For upcoming events of the SPOR seminar, as well as a history of previous talks, see: https://www.eurandom.tue.nl/eindhoven-spor-seminar/. Recordings of earlier talks are available upon request.