تقرير
Aligning random graphs with a sub-tree similarity message-passing algorithm
| العنوان: | Aligning random graphs with a sub-tree similarity message-passing algorithm |
|---|---|
| المؤلفون: | Piccioli, Giovanni, Semerjian, Guilhem, Sicuro, Gabriele, Zdeborová, Lenka |
| المصدر: | J. Stat. Mech. (2022) 063401 |
| سنة النشر: | 2021 |
| المجموعة: | Computer Science Mathematics Condensed Matter |
| مصطلحات موضوعية: | Computer Science - Information Theory, Condensed Matter - Disordered Systems and Neural Networks, Computer Science - Discrete Mathematics, Mathematics - Probability |
| الوصف: | The problem of aligning Erd\"os-R\'enyi 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. Comment: 36 pages, 14 figures, submitted to Journal of Statistical Mechanics: Theory and Experiment. Corrected typos. Modified Figure 1 for clarity. Added references' titles in bibliography. Added definition of "quasi-aligned". Added clarifications about the significance of Nishimori experiments |
| نوع الوثيقة: | Working Paper |
| DOI: | 10.1088/1742-5468/ac70d2 |
| الوصول الحر: | http://arxiv.org/abs/2112.13079Test |
| رقم الانضمام: | edsarx.2112.13079 |
| قاعدة البيانات: | arXiv |
| DOI: | 10.1088/1742-5468/ac70d2 |
|---|