### Partial Recovery Bounds for the Sparse Stochastic Block Model

**2016-02-02**

1602.00877 | cs.IT

In this paper, we study the information-theoretic limits of community
detection in the symmetric two-community stochastic block model, with
intra-community and inter-community edge probabilities $\frac{a}{n}$ and
$\frac{b}{n}$ respectively. We consider the sparse setting, in which $a$ and
$b$ do not scale with $n$, and provide upper and lower bounds on the proportion
of community labels recovered on average. We provide a numerical example for
which the bounds are near-matching for moderate values of $a - b$, and matching
in the limit as $a-b$ grows large.

**Login to like/save this paper, take notes and configure your recommendations**

# Related Articles

**2018-04-24**

1804.08796 | stat.ML

Although the computational and statistical trade-off for modeling single
graphs, for instance, using… show more

**2019-05-17**

1905.07342 | stat.ML

The pair-matching problem appears in many applications where one wants to
discover good matches betw… show more

**2018-06-20**

1806.07562 | stat.ML

We study the stochastic block model with two communities where vertices
contain side information in … show more

**2019-04-16**

1904.07494 | cs.DC

Designing effective algorithms for community detection is an important and
challenging problem in {\… show more

**2019-04-21**

1904.09635 | math.ST

We study the statistical performance of semidefinite programming (SDP)
relaxations for clustering un… show more

**2019-02-03**

1902.00896 | physics.soc-ph

As recent work demonstrated, the task of identifying communities in networks
can be considered analo… show more

**2018-11-14**

1811.06055 | math.ST

This paper surveys some recent developments in fundamental limits and optimal
algorithms for network… show more

**2018-03-06**

1803.02427 | cs.SI

Most empirical studies of networks assume that the network data we are given
represent a complete an… show more

**2019-02-12**

1902.04243 | cs.SI

The maximization of generalized modularity performs well on networks in which
the members of all com… show more

**2017-10-13**

1710.04765 | math.ST

Complex interactions between entities are often represented as edges in a
network. In practice, the … show more

**2018-11-29**

1812.00769 | cs.IT

We introduce the problems of goodness-of-fit and two-sample testing of the
latent community structur… show more

**2018-03-15**

1803.06031 | math.ST

We study bipartite community detection in networks, or more generally the
network biclustering probl… show more

**2018-07-12**

1807.04426 | stat.ME

A fundamental problem in network data analysis is to test Erd\"{o}s-R\'{e}nyi
model $\mathcal{G}\lef… show more

**2019-01-08**

1901.09656 | cs.SI

This paper employs the extrinsic information transfer (EXIT) method, a
technique imported from the a… show more

**2019-04-05**

1904.03272 | math.OC

We consider the densest $k$-subgraph problem, which seeks to identify the
$k$-node subgraph of a giv… show more

**2018-04-05**

1804.01964 | cs.SI

Characterizing large-scale organization in networks, including multilayer
networks, is one of the mo… show more