THE K-CORE IN PERCOLATED DENSE GRAPH SEQUENCES

Erhan Bayraktar; Suman Chakraborty; Xin Zhang

doi:10.1017/jpr.2024.66

THE K-CORE IN PERCOLATED DENSE GRAPH SEQUENCES

Erhan Bayraktar, Suman Chakraborty, Xin Zhang

Finance and Risk Engineering

Research output: Contribution to journal › Article › peer-review

Abstract

We determine the order of the k-core in a large class of dense graph sequences. Let G_n be a sequence of undirected, n-vertex graphs with edge weights {aⁿ_i,j}_i,j∈[n_] that converges to a graphon W : [0, 1]² → [0, +∞) in the cut metric. Keeping an edge (i,j) of G_n with probability aⁿ_i,j/n independently, we obtain a sequence of random graphs G_n(1/n). Using a branching process and the theory of dense graph limits, under mild assumptions we obtain the order of the k-core of random graphs G_n(1/n). Our result can also be used to obtain the threshold of appearance of a k-core of order n.

Original language	English (US)
Pages (from-to)	298-318
Number of pages	21
Journal	Journal of Applied Probability
Volume	62
Issue number	1
DOIs	https://doi.org/10.1017/jpr.2024.66
State	Published - Mar 1 2025

Keywords

Random graphs
branching process
dense graph limit
graphon
k-core
percolation
phase transition

ASJC Scopus subject areas

Statistics and Probability
General Mathematics
Statistics, Probability and Uncertainty

Access to Document

10.1017/jpr.2024.66

Cite this

@article{e6cf17e9836e4534b901958f9f63836c,

title = "THE K-CORE IN PERCOLATED DENSE GRAPH SEQUENCES",

abstract = "We determine the order of the k-core in a large class of dense graph sequences. Let Gn be a sequence of undirected, n-vertex graphs with edge weights {ani,j}i,j∈[n] that converges to a graphon W : [0, 1]2 → [0, +∞) in the cut metric. Keeping an edge (i,j) of Gn with probability ani,j/n independently, we obtain a sequence of random graphs Gn(1/n). Using a branching process and the theory of dense graph limits, under mild assumptions we obtain the order of the k-core of random graphs Gn(1/n). Our result can also be used to obtain the threshold of appearance of a k-core of order n.",

keywords = "Random graphs, branching process, dense graph limit, graphon, k-core, percolation, phase transition",

author = "Erhan Bayraktar and Suman Chakraborty and Xin Zhang",

note = "Publisher Copyright: {\textcopyright} The Author(s), 2024.",

year = "2025",

month = mar,

day = "1",

doi = "10.1017/jpr.2024.66",

language = "English (US)",

volume = "62",

pages = "298--318",

journal = "Journal of Applied Probability",

issn = "0021-9002",

publisher = "Cambridge University Press",

number = "1",

}

TY - JOUR

T1 - THE K-CORE IN PERCOLATED DENSE GRAPH SEQUENCES

AU - Bayraktar, Erhan

AU - Chakraborty, Suman

AU - Zhang, Xin

N1 - Publisher Copyright: © The Author(s), 2024.

PY - 2025/3/1

Y1 - 2025/3/1

N2 - We determine the order of the k-core in a large class of dense graph sequences. Let Gn be a sequence of undirected, n-vertex graphs with edge weights {ani,j}i,j∈[n] that converges to a graphon W : [0, 1]2 → [0, +∞) in the cut metric. Keeping an edge (i,j) of Gn with probability ani,j/n independently, we obtain a sequence of random graphs Gn(1/n). Using a branching process and the theory of dense graph limits, under mild assumptions we obtain the order of the k-core of random graphs Gn(1/n). Our result can also be used to obtain the threshold of appearance of a k-core of order n.

AB - We determine the order of the k-core in a large class of dense graph sequences. Let Gn be a sequence of undirected, n-vertex graphs with edge weights {ani,j}i,j∈[n] that converges to a graphon W : [0, 1]2 → [0, +∞) in the cut metric. Keeping an edge (i,j) of Gn with probability ani,j/n independently, we obtain a sequence of random graphs Gn(1/n). Using a branching process and the theory of dense graph limits, under mild assumptions we obtain the order of the k-core of random graphs Gn(1/n). Our result can also be used to obtain the threshold of appearance of a k-core of order n.

KW - Random graphs

KW - branching process

KW - dense graph limit

KW - graphon

KW - k-core

KW - percolation

KW - phase transition

UR - http://www.scopus.com/inward/record.url?scp=85206347558&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85206347558&partnerID=8YFLogxK

U2 - 10.1017/jpr.2024.66

DO - 10.1017/jpr.2024.66

M3 - Article

AN - SCOPUS:85206347558

SN - 0021-9002

VL - 62

SP - 298

EP - 318

JO - Journal of Applied Probability

JF - Journal of Applied Probability

IS - 1

ER -

THE K-CORE IN PERCOLATED DENSE GRAPH SEQUENCES

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this