Aligning random graphs with a sub-tree similarity message-passing algorithm

Giovanni Piccioli*, Guilhem Semerjian, Gabriele Sicuro, Lenka Zdeborová

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)

Abstract

The problem of aligning ErdÅ's-Rényi random graphs is a noisy, average-case version of the graph isomorphism problem, in which a pair of correlated random graphs is observed through a random permutation of their vertices. We study a polynomial time message-passing algorithm devised to solve the inference problem of partially recovering the hidden permutation, in the sparse regime with constant average degrees. We perform extensive numerical simulations to determine the range of parameters in which this algorithm achieves partial recovery. We also introduce a generalized ensemble of correlated random graphs with prescribed degree distributions, and extend the algorithm to this case.

Original languageEnglish
Article number063401
JournalJournal of Statistical Mechanics: Theory and Experiment
Volume2022
Issue number6
DOIs
Publication statusPublished - 1 Jun 2022

Keywords

  • analysis of algorithms
  • message-passing algorithms
  • random graphs, networks
  • statistical inference

Fingerprint

Dive into the research topics of 'Aligning random graphs with a sub-tree similarity message-passing algorithm'. Together they form a unique fingerprint.

Cite this