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

DOI10.1088/1742-5468/AC70D2MaRDI QIDQ5093855zbMATH OpenOpenAlexFDO

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

Publication date 1 August 2022

Published in Journal of Statistical Mechanics: Theory and Experiment (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2112.13079

zbMATH Keywords

networksrandom graphsstatistical inference

Mathematics Subject Classification ID

Statistical mechanics, structure of matter (82-XX)

Recommendations

• Exact matching of random graphs with constant correlation
• Correlation detection in trees for planted graph alignment
• Partial Recovery in the Graph Alignment Problem
• Efficient random graph matching via degree profiles
• Matching recovery threshold for correlated random graphs

Cites work

• Belief propagation, robust reconstruction and optimal recovery of block models
• Community detection and stochastic block models
• Efficient random graph matching via degree profiles
• On the asymmetry of random regular graphs and random graphs
• Seeded graph matching for correlated Erdős-Rényi graphs
• The (2) limit in the random assignment problem
• The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness
• The number of trees
• The quadratic assignment problem. Theory and algorithms

Cited in

(12)

• Spectral graph matching and regularized quadratic relaxations. I: Algorithm and Gaussian analysis
• Matching recovery threshold for correlated random graphs
• Partial Recovery in the Graph Alignment Problem
• Correlation detection in trees for planted graph alignment
• Statistical limits of correlation detection in trees
• A polynomial-time approximation scheme for the maximal overlap of two independent Erdős-Rényi graphs
• A computational transition for detecting correlated stochastic block models by low-degree polynomials
• Low-degree hardness of detection for correlated Erdős-Rényi graphs
• A polynomial time iterative algorithm for matching Gaussian matrices with non-vanishing correlation
• Average-case and smoothed analysis of graph isomorphism
• Testing network correlation efficiently via counting trees
• Faster algorithms for the alignment of sparse correlated Erdős-Rényi random graphs

This page was built for publication: Aligning random graphs with a sub-tree similarity message-passing algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5093855)