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 derive sharp thresholds for exact recovery of communities in a weightedstochastic block model, where observations are collected in the form of aweighted adjacency matrix, and the weight of each edge is generatedindependently from a distribution determined by the community membership of itsendpoints. Our main result, characterizing the precise boundary between successand failure of maximum likelihood estimation when edge weights are drawn fromdiscrete distributions, involves the Renyi divergence of order $\frac{1}{2}$between the distributions of within-community and between-community edges. Whenthe Renyi divergence is above a certain threshold, meaning the edgedistributions are sufficiently separated, maximum likelihood succeeds withprobability tending to 1; when the Renyi divergence is below the threshold,maximum likelihood fails with probability bounded away from 0. In the languageof graphical channels, the Renyi divergence pinpoints the information-theoreticcapacity of discrete graphical channels with binary inputs. Our resultsgeneralize previously established thresholds derived specifically forunweighted block models, and support an important natural intuition relatingthe intrinsic hardness of community estimation to the problem of edgeclassification. Along the way, we establish a general relationship between theRenyi divergence and the probability of success of the maximum likelihoodestimator for arbitrary edge weight distributions. Finally, we discussconsequences of our bounds for the related problems of censored block modelsand submatrix localization, which may be seen as special cases of the frameworkdeveloped in our paper.

Information-theoretic bounds for exact recovery in weighted stochastic block models using the Renyi divergence