Efficient Graph Matching for Correlated Stochastic Block Models
Shuwen Chai, Miklós Z. Rácz · 2024
Read Efficient Graph Matching for Correlated Stochastic Block Models by Shuwen Chai, Miklós Z. Rácz (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-02661.txt.
Introduction
Shuwen Chai and Miklós Rácz give an efficient matching algorithm for paired networks in a 2024 paper. Graph matching aligns the nodes of two networks that were built from the same hidden groups. In block models, nodes fall into communities, and edges appear with set odds. Matching two such graphs is easy to state and hard to do fast.
Their algorithm is the first efficient one for two balanced communities. In the key regime, where each node has few links, it matches nearly every node correctly when edge correlation passes a sharp threshold. The threshold involves a classic constant from tree counting. The method builds on counting small tree patterns, with new care for errors from unknown community labels. It also yields exact community recovery when several graphs are combined.
Catalog record
| CREATOR | Shuwen Chai, Miklós Z. Rácz |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 246 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-02661