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

CREATORShuwen Chai, Miklós Z. Rácz
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE246 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-02661

Browse the full library · About the Tower of Babel