The Coloured Half-Edges Model
Importance Sampling for Large Deviations of the Giant Component in the Configuration Model
J.C. Strack van Schijndel (TU Delft - Electrical Engineering, Mathematics and Computer Science)
J. Komjáthy – Mentor (TU Delft - Applied Probability)
Marleen Keijzer – Graduation committee member (TU Delft - Mathematical Physics)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
This thesis is about building a model that creates specific types of networks. A network, in this case, is simply a collection of elements (like people) and the connections between them (like friendships or communication). Mathematically, we call this a graph. There already exists a method called the configuration model that randomly builds such graphs while following certain rules—such as how many connections each person should have. When we use this model to make very large graphs, something interesting happens: a large, connected group of ‘people’ almost always forms. We call this the giant component, and it’s a bit like the main cluster in a social network where everyone is connected, directly or indirectly. For a given setup, the giant component has a predictable–typical– size. It’s extremely rare—-almost impossible–for it to be much smaller or larger than typically. But sometimes, we want to study what happens in those rare cases. This thesis explores how to build a new model that can generate these unusual graphs on purpose; graphs that still look natural, but where the giant component is either larger or smaller than the typical giant. This allows us to study networks in extreme scenarios that we normally can’t access.