Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Information-theoretic bounds for exact recovery in weighted stochastic
  block models using the Renyi divergence   We derive sharp thresholds for exact recovery of communities in a weighted
stochastic block model, where observations are collected in the form of a
weighted adjacency matrix, and the weight of each edge is generated
independently from a distribution determined by the community membership of its
endpoints. Our main result, characterizing the precise boundary between success
and failure of maximum likelihood estimation when edge weights are drawn from
discrete distributions, involves the Renyi divergence of order $\frac{1}{2}$
between the distributions of within-community and between-community edges. When
the Renyi divergence is above a certain threshold, meaning the edge
distributions are sufficiently separated, maximum likelihood succeeds with
probability tending to 1; when the Renyi divergence is below the threshold,
maximum likelihood fails with probability bounded away from 0. In the language
of graphical channels, the Renyi divergence pinpoints the information-theoretic
capacity of discrete graphical channels with binary inputs. Our results
generalize previously established thresholds derived specifically for
unweighted block models, and support an important natural intuition relating
the intrinsic hardness of community estimation to the problem of edge
classification. Along the way, we establish a general relationship between the
Renyi divergence and the probability of success of the maximum likelihood
estimator for arbitrary edge weight distributions. Finally, we discuss
consequences of our bounds for the related problems of censored block models
and submatrix localization, which may be seen as special cases of the framework
developed in our paper.

15
The categories of this paper are: nucl-ex
3
The categories of this paper are: physics
35
The categories of this paper are: mtrl-th
27
The categories of this paper are: comp-gas
20
The categories of this paper are: acc-phys
9
The categories of this paper are: nlin
26
The categories of this paper are: bayes-an
21
The categories of this paper are: adap-org
31
The categories of this paper are: ao-sci
17
The categories of this paper are: q-fin
22
The categories of this paper are: chao-dyn
33
The categories of this paper are: plasm-ph
36
The categories of this paper are: cmp-lg
4
The categories of this paper are: cond-mat
13
The categories of this paper are: quant-ph
10
The categories of this paper are: q-bio