k(n)-cores in the scale-free configuration model
Understanding the structure of a commonly used null model for scale-free networks
J.P. Jaspers (TU Delft - Electrical Engineering, Mathematics and Computer Science)
J. Komjáthy – Mentor (TU Delft - Applied Probability)
A. Bishnoi – Graduation committee member (TU Delft - Discrete Mathematics and Optimization)
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
During this research, we investigate if there exists a k(n)-core in the scale-free configuration model, this is a commonly used null model to simulate networks. The scale-free configuration model produces a random graph, where the degree of every vertex is determined using a random variable. In this thesis, the discrete Pareto variable is used with parameter τ ∈ (2, 3). The k-core of a graph is the biggest induced subgraph where every vertex is connected to at least k edges in the subgraph. In this thesis, we let k be dependent on the number of vertices in a graph, this makes it a k(n)-core. By investigating whether k(n)-cores exist in graphs produced by the scale-free configuration model, we hope to to get a better understanding of the structure of these graphs.
In this thesis, the scale-free configuration model is modeled as a death process. This death process will produce the graph and its k(n)-core jointly. First, we remove all edges which cannot be part of the k(n)-core until the point where no such edges exist anymore. This is the moment where we reach the k(n)-core. Using this method, we prove that whenever the number of vertices is sufficiently high a (log(n))^α-core exists with high probability for all constant α >0. For α < (3−τ)/(8τ) , also a n^α-core exists with high probability when the number of vertices is sufficiently high. We also find a lower bound for the number of vertices and edges left in the cores.