K-core in random graphs

Abstract

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.