Partial Recovery of Erdos-Renyi Graph Alignment via k-Core Alignment

被引：15

作者：

Cullina, Daniel ^{[1
]}

Kiyavash, Negar ^{[2
]}

Mittal, Prateek ^{[1
]}

Poor, H. Vincent ^{[1
]}

机构：

[1] Princeton Univ, Dept Elect Engn, Princeton, NJ 08544 USA

[2] Ecole Polytech Fed Lausanne, Sch Management Technol, Lausanne, Switzerland

来源：

PROCEEDINGS OF THE ACM ON MEASUREMENT AND ANALYSIS OF COMPUTING SYSTEMS | 2019年 / 3卷 / 03期

关键词：

Network alignment; de-anonymization;

D O I：

10.1145/3366702

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

We determine information theoretic conditions under which it is possible to partially recover the alignment used to generate a pair of sparse, correlated Erdos-Renyi graphs. To prove our achievability result, we introduce the k-core alignment estimator. This estimator searches for an alignment in which the intersection of the correlated graphs using this alignment has a minimum degree of k. We prove a matching converse bound. As the number of vertices grows, recovery of the alignment for a fraction of the vertices tending to one is possible when the average degree of the intersection of the graph pair tends to infinity. It was previously known that exact alignment is possible when this average degree grows faster than the logarithm of the number of vertices.

引用

页数：21

共 29 条

[1]

Abbe E, 2023, Arxiv, DOI arXiv:1703.10146

[2]

Backstrom L., 2007, P 16 INT C WORLD WID, P181

[3]

Barak B., 2018, nearly) efficient algorithms for the graph matching problem on correlated random graphs

[4]

Bollobas Bela, 1984, EVOLUTION SPARSE GRA

[5]

Cullina D, 2018, Arxiv, DOI arXiv:1805.03829

[6]

Cullina D, 2018, Arxiv, DOI arXiv:1711.06783

[7]

Cullina D, 2016, SIGMETRICS/PERFORMANCE 2016: PROCEEDINGS OF THE SIGMETRICS/PERFORMANCE JOINT INTERNATIONAL CONFERENCE ON MEASUREMENT AND MODELING OF COMPUTER SCIENCE, P63, DOI [10.1145/2964791.2901460, 10.1145/2896377.2901460]

[8]

Feizi S, 2017, Arxiv, DOI arXiv:1602.04181

[9] On Your Social Network De-anonymizablity: Quantification and Large Scale Evaluation with Seed Knowledge [J].

Ji, Shouling ;

Li, Weiqing ;

Gong, Neil Zhenqiang ;

Mittal, Prateek ;

Beyah, Raheem .

22ND ANNUAL NETWORK AND DISTRIBUTED SYSTEM SECURITY SYMPOSIUM (NDSS 2015), 2015,

[10]

Kazemi E, 2015, ANN ALLERTON CONF, P33, DOI 10.1109/ALLERTON.2015.7446983

← 1 2 3 →