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

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

Research output: Contribution to journalArticle

Abstract

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. 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)
Pages (from-to)99-100
Number of pages2
JournalPerformance Evaluation Review
Volume48
Issue number1
DOIs
StatePublished - Jul 8 2020

All Science Journal Classification (ASJC) codes

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

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