TY - JOUR

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

AU - Piccioli, Giovanni

AU - Semerjian, Guilhem

AU - Sicuro, Gabriele

AU - Zdeborová, Lenka

N1 - Publisher Copyright:
© 2022 IOP Publishing Ltd and SISSA Medialab srl.

PY - 2022/6/1

Y1 - 2022/6/1

N2 - 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.

AB - 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.

KW - analysis of algorithms

KW - message-passing algorithms

KW - random graphs, networks

KW - statistical inference

UR - http://www.scopus.com/inward/record.url?scp=85132792274&partnerID=8YFLogxK

U2 - 10.1088/1742-5468/ac70d2

DO - 10.1088/1742-5468/ac70d2

M3 - Article

AN - SCOPUS:85132792274

SN - 1742-5468

VL - 2022

JO - Journal of Statistical Mechanics: Theory and Experiment

JF - Journal of Statistical Mechanics: Theory and Experiment

IS - 6

M1 - 063401

ER -