MATCHING RECOVERY THRESHOLD FOR CORRELATED RANDOM GRAPHS

被引：8

作者：

Ding, Jian ^{[1
]}

Du, Hang ^{[1
]}

机构：

[1] Peking Univ, Sch Math Sci, Beijing, Peoples R China

来源：

ANNALS OF STATISTICS | 2023年 / 51卷 / 04期

基金：

中国国家自然科学基金;

关键词：

Correlated Erdos-Renyi random graph; matching recovery; information threshold; ORIENTABILITY THRESHOLDS; ALIGNMENT;

D O I：

10.1214/23-AOS2305

中图分类号：

O21 [概率论与数理统计]; C8 [统计学];

学科分类号：

020208 ; 070103 ; 0714 ;

摘要：

For two correlated graphs which are independently sub-sampled from a common Erdos-Renyi graph G(n, p) , we wish to recover their latent vertex matching from the observation of these two graphs without labels. When p = n-alpha +o(1) for alpha E (0 , 1] , we establish a sharp information-theoretic threshold for whether it is possible to correctly match a positive fraction of vertices. Our result sharpens a constant factor in a recent work by Wu, Xu and Yu.

引用

页码：1718 / 1743

页数：26

共 50 条

[1]

Aldous D, 2004, ENCYL MATH SCI, V110, P1

[2] THE DENSEST SUBGRAPH PROBLEM IN SPARSE RANDOM GRAPHS [J].

Anantharam, Venkat ;

Salez, Justin .

ANNALS OF APPLIED PROBABILITY, 2016, 26 (01) :305-327

[3] THE CYCLE STRUCTURE OF RANDOM PERMUTATIONS [J].

ARRATIA, R ;

TAVARE, S .

ANNALS OF PROBABILITY, 1992, 20 (03) :1567-1591

[4]

Barak B, 2019, ADV NEUR IN, V32

[5]

Berg AC, 2005, PROC CVPR IEEE, P26

[6]

Bozorg M, 2020, Arxiv, DOI arXiv:1907.06334

[7]

Cain JA, 2007, PROCEEDINGS OF THE EIGHTEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P469

[8]

Chen SX, 2022, Arxiv, DOI arXiv:2204.13858

[9]

Cour T., 2006, Advances in Neural Information Processing Systems, V19

[10]

Cullina D, 2018, Arxiv, DOI arXiv:1711.06783

← 1 2 3 4 5 →