Viinistu, Estonia, March 4 - 7, 2024
Assistant Professor at Reykjavik University, Iceland
In this lecture series we will look at the problem of generating random
graphs with various prescribed properties, and investigating them. How
do we generate a random tree, chosen uniformly from the set of all
trees on n vertices? What is an efficient algorithm for creating a
random graph with a given number of edges? What is the probability that
it will be connected? What about generating random connected graphs
with prescribed degrees? What if we only specify the average degree of
each vertex (a so-called "soft" constraint)?
So-called random graph models—statistical distributions over the set of
graphs—find many practical applications. They are one of the
fundamental tools for studying real-world network data, and are
commonly used as statistical null models. In order to make effective
use of them we need unbiased and efficient sampling algorithms for
graph. In these lectures we will learn about different kinds of random
graph models (including maximum entropy models), and will look at
techniques for constructing sampling algorithms for them.
Last changed
March 7, 2024 13:02 EET (GMT +02:00)
by local organisers