Thek-Core and Branching Processes

DOI10.1017/S0963548307008589MaRDI QIDQ5448993zbMATH OpenFDO

Authors Oliver Riordan

Publication date 10 March 2008

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0511093

zbMATH Keywords

power-lawscale-free graphGalton-Watson branching processRandom graph

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Extremal problems in graph theory (05C35) Branching processes (Galton-Watson, birth-and-death, etc.) (60J80) Vertex degrees (05C07)

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 $lambd{a}_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 epsilon above the threshold. In contrast to $G(n,lambda/n)$, this fraction tends to 0 as epsilon tends to 0.

Recommendations

• Sudden emergence of a giant k-core in a random graph
• Core forging and local limit theorems for the \(k\)-core of random graphs
• Asymptotic normality of the \(k\)-core in random graphs
• Size and connectivity of the \(k\)-core of a random graph

Cites work

• A Random Graph Model for Power Law Graphs
• A simple solution to the k‐core problem
• Cores in random hypergraphs and Boolean formulas
• Emergence of Scaling in Random Networks
• Families of Non-disjoint subsets
• Sudden emergence of a giant \(k\)-core in a random graph
• The Small Giant Component in Scale-Free Random Graphs
• The phase transition in inhomogeneous random graphs
• The phase transition in the uniformly grown random graph has infinite order

Cited in

(23)

• Branching Processes, the Max-Plus Algebra and Network Calculus
• Loose cores and cycles in random hypergraphs
• The cook-book approach to the differential equation method
• \(k\)-core organization in complex networks
• Propagation of chaos of forward-backward stochastic differential equations with graphon interactions
• Singularity of the \(k\)-core of a random graph
• An old approach to the giant component problem
• Cores of random graphs are born Hamiltonian
• Exact thresholds for DPLL on random XOR-SAT and NP-complete extensions of XOR-SAT
• A central limit theorem for diffusion in sparse random graphs
• Phase transitions in graphs on orientable surfaces
• Random graphs with forbidden vertex degrees
• The stripping process can be slow. II
• On the robustness of random \(k\)-cores
• The structure of typical clusters in large sparse random configurations
• Continuous phase transitions on Galton–Watson trees
• A branching process with deletions and mergers that matches the threshold for hypercube percolation
• Survival probabilities for \(N\)-ary subtrees on a Galton-Watson family tree
• Asymptotic normality of the \(k\)-core in random graphs
• Random simplicial complexes: around the phase transition
• Birth of a giant \((k_{1},k_{2})\)-core in the random digraph
• Core forging and local limit theorems for the \(k\)-core of random graphs
• The coreness and H-index of random geometric graphs

This page was built for publication: Thek-Core and Branching Processes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5448993)