TY - GEN
T1 - Partial Recovery of ErdÅ's-Rényi Graph Alignment via k-Core Alignment
AU - Cullina, Daniel
AU - Kiyavash, Negar
AU - Mittal, Prateek
AU - Poor, H. Vincent
N1 - Publisher Copyright:
© 2019 Owner/Author.
PY - 2020/6/8
Y1 - 2020/6/8
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85086994042&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85086994042&partnerID=8YFLogxK
U2 - 10.1145/3393691.3394211
DO - 10.1145/3393691.3394211
M3 - Conference contribution
AN - SCOPUS:85086994042
T3 - SIGMETRICS Performance 2020 - Abstracts of the 2020 SIGMETRICS/Performance Joint International Conference on Measurement and Modeling of Computer Systems
SP - 99
EP - 100
BT - SIGMETRICS Performance 2020 - Abstracts of the 2020 SIGMETRICS/Performance Joint International Conference on Measurement and Modeling of Computer Systems
PB - Association for Computing Machinery, Inc
T2 - 2020 SIGMETRICS/Performance Joint International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 2020
Y2 - 8 June 2020 through 12 June 2020
ER -