A simple solution to the k‐core problem
From MaRDI portal
Publication:3419611
Abstract: We study the k-core of a random (multi)graph on n vertices with a given degree sequence. We let n tend to infinity. Then, under some regularity conditions on the degree sequences, we give conditions on the asymptotic shape of the degree sequence that imply that with high probability the k-core is empty, and other conditions that imply that with high probability the k-core is non-empty and the sizes of its vertex and edge sets satisfy a law of large numbers; under suitable assumptions these are the only two possibilities. In particular, we recover the result by Pittel, Spencer and Wormald on the existence and size of a k-core in G(n,p) and G(n,m). Our method is based on the properties of empirical distributions of independent random variables, and leads to simple proofs.
Recommendations
- Minimum k‐cores and the k‐core polytope
- The \(k\)-separator problem
- The \(k\)-partitioning problem
- A complete resolution of the Keller maximum clique problem
- The $k$ -Equal Problem
- The minimal \(k\)-core problem for modeling \(k\)-assemblies
- A Linear Time Algorithm for Finding ak-Tree Core
- scientific article; zbMATH DE number 1092062
- The \(k\)-cardinality assignment problem
- A parameterized complexity view on collapsing \(k\)-cores
Cites work
Cited in
(38)- Singularity of the \(k\)-core of a random graph
- Persuasion in networks: public signals and cores
- Random graphs with forbidden vertex degrees
- On the threshold for k-regular subgraphs of random graphs
- Preferential attachment without vertex growth: emergence of the giant component
- Load Thresholds for Cuckoo Hashing with Overlapping Blocks
- The minimal \(k\)-core problem for modeling \(k\)-assemblies
- SIR epidemics on random graphs with a fixed degree sequence
- On Edge-Disjoint Spanning Trees in a Randomly Weighted Complete Graph
- Successive minimum spanning trees
- Diffusion and cascading behavior in random networks
- Dismantling Sparse Random Graphs
- The probability that a random multigraph is simple
- The diameter of weighted random graphs
- On the robustness of random k-cores
- Asymptotic normality of the \(k\)-core in random graphs
- Cores of random graphs are born Hamiltonian
- A general critical condition for the emergence of a giant component in random graphs with given degrees
- The cook-book approach to the differential equation method
- Thek-Core and Branching Processes
- Law of large numbers for the SIR epidemic on a random graph with given degrees
- The coreness and H-index of random geometric graphs
- Small cores in 3-uniform hypergraphs
- Sets that are connected in two random graphs
- Degree sequences of monocore graphs
- Finding density-based subspace clusters in graphs with feature vectors
- Load Thresholds for Cuckoo Hashing with Overlapping Blocks
- The solution space geometry of random linear equations
- A central limit theorem for diffusion in sparse random graphs
- On the spread of random graphs
- Core forging and local limit theorems for the \(k\)-core of random graphs
- A new approach to the giant component problem
- scientific article; zbMATH DE number 7525475 (Why is no real title available?)
- The stripping process can be slow. II
- Degree correlations in scale-free random graph models
- A new approach to the orientation of random hypergraphs
- Loose cores and cycles in random hypergraphs
- How to determine if a random graph with a fixed degree sequence has a giant component
This page was built for publication: A simple solution to the k‐core problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3419611)
