Improved achievability and converse bounds for erd?os-rényi graph matching

Daniel Cullina, Negar Kiyavash

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

Abstract

We consider the problem of perfectly recovering the vertex correspondence between two correlated Erd}os-Rényi (ER) graphs. For a pair of correlated graphs on the same ver-tex set, the correspondence between the vertices can be ob- scured by randomly permuting the vertex labels of one of the graphs. In some cases, the structural information in the graphs allow this correspondence to be recovered. We investigate the information-theoretic threshold for exact re- covery, i.e. the conditions under which the entire vertex correspondence can be correctly recovered given unbounded computational resources. Pedarsani and Grossglauser provided an achievability re-sult of this type. Their result establishes the scaling de-pendence of the threshold on the number of vertices. We improve on their achievability bound. We also provide a converse bound, establishing conditions under which exact recovery is impossible. Together, these establish the scal- ing dependence of the threshold on the level of correlation between the two graphs. The converse and achievability bounds differ by a factor of two for sparse, significantly cor- related graphs. c 2016 Copyright held by the owner/author(s). Publication rights licensed to ACM.

Original languageEnglish (US)
Title of host publicationSIGMETRICS/ Performance 2016 - Proceedings of the SIGMETRICS/Performance Joint International Conference on Measurement and Modeling of Computer Science
PublisherAssociation for Computing Machinery, Inc
Pages63-72
Number of pages10
ISBN (Electronic)9781450342667
DOIs
StatePublished - Jun 14 2016
Event13th Joint International Conference on Measurement and Modeling of Computer Systems, ACM SIGMETRICS / IFIP Performance 2016 - Antibes Juan-les-Pins, France
Duration: Jun 14 2016Jun 18 2016

Publication series

NameSIGMETRICS/ Performance 2016 - Proceedings of the SIGMETRICS/Performance Joint International Conference on Measurement and Modeling of Computer Science

Other

Other13th Joint International Conference on Measurement and Modeling of Computer Systems, ACM SIGMETRICS / IFIP Performance 2016
CountryFrance
CityAntibes Juan-les-Pins
Period6/14/166/18/16

ASJC Scopus subject areas

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

Fingerprint Dive into the research topics of 'Improved achievability and converse bounds for erd?os-rényi graph matching'. Together they form a unique fingerprint.

  • Cite this

    Cullina, D., & Kiyavash, N. (2016). Improved achievability and converse bounds for erd?os-rényi graph matching. In SIGMETRICS/ Performance 2016 - Proceedings of the SIGMETRICS/Performance Joint International Conference on Measurement and Modeling of Computer Science (pp. 63-72). (SIGMETRICS/ Performance 2016 - Proceedings of the SIGMETRICS/Performance Joint International Conference on Measurement and Modeling of Computer Science). Association for Computing Machinery, Inc. https://doi.org/10.1145/2896377.2901460