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

Community detection is a fundamental problem in network science. In thispaper, we consider community detection in hypergraphs drawn from the$hypergraph$ $stochastic$ $block$ $model$ (HSBM), with a focus on exactcommunity recovery. We study the performance of polynomial-time algorithmswhich operate on the $similarity$ $matrix$ $W$, where $W_{ij}$ reports thenumber of hyperedges containing both $i$ and $j$. Under this information model,while the precise information-theoretic limit is unknown, Kim, Bandeira, andGoemans derived a sharp threshold up to which the natural min-bisectionestimator on $W$ succeeds. As min-bisection is NP-hard in the worst case, theyadditionally proposed a semidefinite programming (SDP) relaxation andconjectured that it achieves the same recovery threshold as the min-bisectionestimator.  In this paper, we confirm this conjecture. We also design a simple and highlyefficient spectral algorithm with nearly linear runtime and show that itachieves the min-bisection threshold. Moreover, the spectral algorithm alsosucceeds in denser regimes and is considerably more efficient than previousapproaches, establishing it as the method of choice. Our analysis of thespectral algorithm crucially relies on strong $entrywise$ bounds on theeigenvectors of $W$. Our bounds are inspired by the work of Abbe, Fan, Wang,and Zhong, who developed entrywise bounds for eigenvectors of symmetricmatrices with independent entries. Despite the complex dependency structure insimilarity matrices, we prove similar entrywise guarantees.

Community Detection in the Hypergraph SBM: Exact Recovery Given the Similarity Matrix