The k-core and branching processes

Abstract

The k-core of a graph G is the maximal subgraph of G having minimum degree at least k. In 1996, Pittel, Spencer and Wormald found the threshold ${\lambda }_c$ for the emergence of a non-trivial k-core in the random graph $G(n,\lambda /n)$, and the asymptotic size of the k-core above the threshold. We give a new proof of this result using a local coupling of the graph to a suitable branching process. This proof extends to a general model of inhomogeneous random graphs with independence between the edges. As an example, we study the k-core in a certain power-law or `scale-free' graph with a parameter c controlling the overall density of edges. For each k at least 3, we find the threshold value of c at which the k-core emerges, and the fraction of vertices in the k-core when c is εabove the threshold. In contrast to $G(n,\lambda /n)$, this fraction tends to 0 as εtends to 0.

30 pages, 1 figure. Minor revisions. To appear in Combinatorics, Probability and Computing

References in corpus (6)

• Emergence of scaling in random networks
• The phase transition in inhomogeneous random graphs
• Are randomly grown graphs really random?
• Differential equation approximations for Markov chains
• A General Formalism for Inhomogeneous Random Graphs
• Anomalous percolating properties of growing networks

Cited by in corpus (20)

• Differential equation approximations for Markov chains
• Heterogeneous-k-core versus Bootstrap Percolation on Complex Networks
• Accelerating Community Detection by Using K-core Subgraphs
• An old approach to the giant component problem
• The structure of typical clusters in large sparse random configurations
• Cores of random graphs are born Hamiltonian
• Exact phase transition of backtrack-free search with implications on the power of greedy algorithms
• Understanding edge-connectivity in the Internet through core-decomposition
• The rank of random matrices over finite fields
• On the robustness of random k-cores
• External-Memory Network Analysis Algorithms for Naturally Sparse Graphs
• Phase transitions in graphs on orientable surfaces
• Warning Propagation on random graphs
• The core in random hypergraphs and local weak convergence
• New graph polynomials from the Bethe approximation of the Ising partition function
• Warning Propagation: stability and subcriticality
• K-core in percolated dense graph sequences
• Continuous phase transitions on Galton-Watson trees
• The Satisfiability Threshold for a Seemingly Intractable Random Constraint Satisfaction Problem
• Survival Probabilities for N-ary Subtrees on a Galton-Watson Family Tree