English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We consider the problem of graph matching, or learning vertex correspondence,between two correlated stochastic block models (SBMs). The graph matchingproblem arises in various fields, including computer vision, natural languageprocessing and bioinformatics, and in particular, matching graphs with inherentcommunity structure has significance related to de-anonymization of correlatedsocial networks. Compared to the correlated Erdos-Renyi (ER) model, wherevarious efficient algorithms have been developed, among which a few algorithmshave been proven to achieve the exact matching with constant edge correlation,no low-order polynomial algorithm has been known to achieve exact matching forthe correlated SBMs with constant correlation. In this work, we propose anefficient algorithm for matching graphs with community structure, based on thecomparison between partition trees rooted from each vertex, by extending theidea of Mao et al. (2021) to graphs with communities. The partition treedivides the large neighborhoods of each vertex into disjoint subsets usingtheir edge statistics to different communities. Our algorithm is the firstlow-order polynomial-time algorithm achieving exact matching between twocorrelated SBMs with high probability in dense graphs.

Efficient Algorithms for Exact Graph Matching on Correlated Stochastic Block Models with Constant Correlation