Partial Recovery of ErdÅ's-Rényi Graph Alignment via k-Core Alignment

Daniel Cullina, Negar Kiyavash, Prateek Mittal, H. Vincent Poor

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.

Original languageEnglish (US)
Title of host publicationSIGMETRICS Performance 2020 - Abstracts of the 2020 SIGMETRICS/Performance Joint International Conference on Measurement and Modeling of Computer Systems
PublisherAssociation for Computing Machinery, Inc
Pages99-100
Number of pages2
ISBN (Electronic)9781450379854
DOIs
StatePublished - Jun 8 2020
Event2020 SIGMETRICS/Performance Joint International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 2020 - Boston, United States
Duration: Jun 8 2020Jun 12 2020

Publication series

NameSIGMETRICS Performance 2020 - Abstracts of the 2020 SIGMETRICS/Performance Joint International Conference on Measurement and Modeling of Computer Systems

Conference

Conference2020 SIGMETRICS/Performance Joint International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 2020
CountryUnited States
CityBoston
Period6/8/206/12/20

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture
  • Computer Networks and Communications
  • Computational Theory and Mathematics

Keywords

  • de-anonymization
  • network alignment

Fingerprint Dive into the research topics of 'Partial Recovery of ErdÅ's-Rényi Graph Alignment via k-Core Alignment'. Together they form a unique fingerprint.

Cite this