K-core in random graphs

K-core in random graphs

Wassenaar, Vincent (TU Delft Electrical Engineering, Mathematics and Computer Science)

Komjáthy, J. (mentor)
Spandaw, J.G. (graduation committee)

Delft University of Technology

Applied Mathematics

2022-07-12

A graph G=(V,E) is a mathematical model for a network with vertex set V and edge set E. A Random Graph model is a probabilistic graph. A Random Geometric Graph is a Random Graph were each vertex has a location in a space χ. We compare the Erdos-Rényi random graph, G(n,p), to the Random Geometric Graph model, RGG(n,r) where, in general we use r=c / (n^(-1/d)), with dimension d. It is known that for p = λ*/n the k-core has a first-order phase transition in G(n,p) where λ* is the critical value for the k-core. The k-core is a global property of a graph. The k-core is the largest induced subgraph where each vertex has at least degree k. We suggest by simulations and a supportive proof that for the RGG-model a first-order phase transition not plausible. A inhomogeneous extension of the RGG-model with a vertex weight distribution T is a Geometric Inhomogeneous Random Graph model (GIRG). We also prove why some heavy-tailed (i.e. power-law) distributions almost surely have a k-core, when the amount of vertices v, which have weights greater than the square root of n, is greater than k. Furthermore, we rephrase from known literature how using a fixed equation for a branching process is a useful tool for analysing the existence of a k-core. In particular, the critical value for the 3-core is recovered using the probability of a binary tree embedding in branching processes, with the root having at least 3 children.

Random Graphs
k-core
Random Geometric Graph
Geometric Inhomogeneous Random Graph

http://resolver.tudelft.nl/uuid:b195b6fa-7521-4c12-9fc6-a930b798bf8f

Student theses

bachelor thesis

© 2022 Vincent Wassenaar