The k-Core and Branching Processes

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 λc for the emergence of a non-trivial k-core in the random graph G(n, λ/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 ≥ 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, λ/n), this fraction tends to 0 as ϵ→0.

• Publication year

  2005

• Venue

  Combinatorics, probability & computing

• Publication date

  2005-11-03

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1017/S0963548307008589arXiv math/0511093
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Differential equation approximations for Markov chains

  2007cited by this paper
• Encores on Cores

  2006cited by this paper
• The phase transition in inhomogeneous random graphs

  2005cited by this paper
• The phase transition in the uniformly grown random graph has infinite order

  2005cited by this paper
• A proof of a conjecture of Buck, Chan, and Robbins on the expected value of the minimum assignment

  2005cited by this paper
• A simple solution to the k‐core problem

  2005cited by this paper
• Three-query PCPs with perfect completeness over non-Boolean domains

  2005cited by this paper
• The Small Giant Component in Scale-Free Random Graphs

  2005cited by this paper
• Directed graphs, Hamiltonicity and doubly stochastic matrices

  2004cited by this paper
• The giant k-core of a random graph with a speci ed degree sequence

  2003influential reference
• Rigorous Result for the CHKNS Random Graph Model

  2003cited by this paper
• General formalism for inhomogeneous random graphs.

  2002cited by this paper
• Anomalous percolation properties of growing networks.

  2001cited by this paper
• A Random Graph Model for Power Law Graphs

  2001cited by this paper
• Are randomly grown graphs really random?

  2001cited by this paper
• Emergence of Scaling in Random Networks

  1999cited by this paper
• Sudden Emergence of a Giantk-Core in a Random Graph

  1996influential reference
• A Critical Point for Random Graphs with a Given Degree Sequence

  1995cited by this paper
• Almost All Graphs with 1.44n Edges are 3-Colorable

  1991influential reference
• When are random graphs connected

  1988cited by this paper
• Families of Non-disjoint subsets*

  1966cited by this paper
• A lower bound for the critical probability in a certain percolation process

  1960cited by this paper

• The $k$-core of a graph and its high-order spectra

  2025cites this paper
• The k-core in percolated dense graph sequences

  2024influential citation
• On Edge Collapse of Random Simplicial Complexes

  2024cites this paper
• Dynamics of Cascading Losses in Locally Tree-Like Networks

  2024cites this paper
• The k-XORSAT threshold revisited

  2023cites this paper
• Locality via Global Ties: Stability of the 2-Core Against Misspecification

  2023influential citation
• Study on the Hierarchical Structure of the “Belt and Road” Aviation Network Based on K -Core Analysis

  2022cites this paper
• Propagation of Chaos of Forward–Backward Stochastic Differential Equations with Graphon Interactions

  2022cites this paper
• The Size of the Giant Joint Component in a Binomial Random Double Graph

  2021influential citation
• Warning Propagation: stability and subcriticality

  2021cites this paper
• Loose Cores and Cycles in Random Hypergraphs

  2021cites this paper
• Singularity of the k-core of a random graph

  2021cites this paper
• The coreness and h-index of random geometric graphs

  2021cites this paper
• A branching process with deletions and mergers that matches the threshold for hypercube percolation

  2021cites this paper
• A Central Limit Theorem for Diffusion in Sparse Random Graphs

  2021cites this paper
• Warning Propagation on random graphs

  2021cites this paper
• Continuous phase transitions on Galton-Watson trees

  2020cites this paper
• $k$-core in percolated dense graph sequences.

  2020influential citation
• Component Games on Random Graphs

  2020influential citation
• k-core: Theories and applications

  2019cites this paper
• The rank of sparse random matrices

  2019cites this paper
• The size of the joint-giant component in a binomial random double graph.

  2019cites this paper
• Probability and Computing

  2018cites this paper
• The rank of random matrices over finite fields

  2018cites this paper
• Core forging and local limit theorems for the k-core of random graphs

  2017cites this paper
• Phase transitions in graphs on orientable surfaces

  2017cites this paper
• Random simplicial complexes - around the phase transition

  2016cites this paper
• Birth of a giant (k1, k2)-core in the random digraph

  2016influential citation
• Finding Community Structures In Social Activity Data

  2015cites this paper
• Density Evolution for Deterministic Generalized Product Codes on the Binary Erasure Channel at High Rates

  2015influential citation
• How does the core sit inside the mantle?

  2015influential citation
• The core in random hypergraphs and local weak convergence

  2015influential citation
• Extraction and Analysis of Crucial Fraction in Software Networks

  2014cites this paper
• Accelerating Community Detection by Using K-core Subgraphs

  2014cites this paper
• The Phase Transition in the Erdős-Rényi Random Graph Process

  2013cites this paper
• Core Structures in Random Graphs and Hypergraphs

  2013cites this paper
• Cores of random graphs are born Hamiltonian

  2013cites this paper
• An old approach to the giant component problem

  2012cites this paper
• On the robustness of random k-cores

  2012cites this paper
• Exact thresholds for DPLL on random XOR-SAT and NP-complete extensions of XOR-SAT

  2012cites this paper
• The Satisfiability Threshold for a Seemingly Intractable Random Constraint Satisfaction Problem

  2012cites this paper
• External-Memory Network Analysis Algorithms for Naturally Sparse Graphs

  2011cites this paper
• The cook-book approach to the differential equation method

  2010cites this paper
• Heterogeneous k-core versus bootstrap percolation on complex networks.

  2010cites this paper
• Parameter testing in bounded degree graphs of subexponential growth

  2010cites this paper
• Understanding Edge Connectivity in the Internet through Core Decomposition

  2009cites this paper
• New Graph Polynomials from the Bethe Approximation of the Ising Partition Function

  2009cites this paper
• Efficient control of epidemics over random networks

  2009cites this paper
• Exact phase transition of backtrack-free search with implications on the power of greedy algorithms

  2008cites this paper
• Threshold Phenomena in Random Constraint Satisfaction Problems

  2008cites this paper
• Random Graphs and Branching Processes

  2008cites this paper
• The Structure of Typical Clusters in Large Sparse Random Configurations

  2008influential citation
• On percolation in random graphs with given vertex degrees

  2008cites this paper
• Survival probabilities for N-ary subtrees on a Galton-Watson family tree

  2007cites this paper
• Differential equation approximations for Markov chains

  2007cites this paper
• Random graphs with forbidden vertex degrees

  2007cites this paper
• Encores on Cores

  2006cites this paper
• The phase transition in inhomogeneous random graphs

  2005cites this paper
• K-core Organization of Complex Networks

  2005cites this paper
• k -core: Theories and applications ✩

  year unknowncites this paper