k(n)-cores in the scale-free configuration model

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.