Cited By
View all- Ding JLi Z(2024)A Polynomial Time Iterative Algorithm for Matching Gaussian Matrices with Non-vanishing CorrelationFoundations of Computational Mathematics10.1007/s10208-024-09662-xOnline publication date: 22-Jul-2024
Partial Recovery of Erdős-Rényi Graph Alignment via k-Core Alignment
Pages 99 - 100
Abstract
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.
References
[1]
P. Pedarsani and M. Grossglauser, "On the privacy of anonymized networks," in Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2011, pp. 1235--1243.
[2]
BIBentryALTinterwordspacingD. Cullina and N. Kiyavash, "Exact alignment recovery for correlated Erdos Rényi graphs," arXiv:1711.06783 [cs, math], Nov. 2017, arXiv: 1711.06783. [Online]. Available: http://arxiv.org/abs/1711.06783.
[3]
----, "Improved achievability and converse bounds for Erdos-Rényi graph matching," in Proceedings of the 2016 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Science. ACM, 2016, pp. 63--72.
[4]
B. Bollobás, The evolution of sparse graphs, Graph Theory and Combinatorics (Cambridge 1983), 35--57. Academic Press, London, 1984.
Index Terms
- Partial Recovery of Erdős-Rényi Graph Alignment via k-Core Alignment
Recommendations
Partial Recovery of Erdðs-Rényi Graph Alignment via k-Core Alignment
SIGMETRICSWe 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. ...
Partial Recovery of Erdős-Rényi Graph Alignment via k-Core Alignment
We determine information theoretic conditions under which it is possible to partially recover the alignment used to generate a pair of sparse, correlated Erdős-Rényi graphs. To prove our achievability result, we introduce the k-core alignment estimator. ...
Analysis of a Canonical Labeling Algorithm for the Alignment of Correlated Erdős-Rényi Graphs
Graph alignment in two correlated random graphs refers to the task of identifying the correspondence between vertex sets of the graphs. Recent results have characterized the exact informationtheoretic threshold for graph alignment in correlated Erdős-...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
June 2020
124 pages
ISBN:9781450379854
DOI:10.1145/3393691
- General Chair:
- Edmund Yeh,
- Program Chairs:
- Athina Markopoulou,
- Y.C. Tay
Copyright © 2020 Owner/Author.
Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the Owner/Author.
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 08 June 2020
Check for updates
Author Tags
Qualifiers
- Abstract
Funding Sources
Conference
SIGMETRICS '20
Sponsor:
SIGMETRICS '20: ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems
June 8 - 12, 2020
MA, Boston, USA
Acceptance Rates
Overall Acceptance Rate 459 of 2,691 submissions, 17%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 57Total Downloads
- Downloads (Last 12 months)1
- Downloads (Last 6 weeks)0
Reflects downloads up to 19 Dec 2024
Other Metrics
Citations
Cited By
View all- Ding JLi Z(2024)A Polynomial Time Iterative Algorithm for Matching Gaussian Matrices with Non-vanishing CorrelationFoundations of Computational Mathematics10.1007/s10208-024-09662-xOnline publication date: 22-Jul-2024
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in