ML p(r)ior | Partial Recovery Bounds for the Sparse Stochastic Block Model

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.
PDF

Highlights - Most important sentences from the article

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
PDF

Highlights - Most important sentences from the article

2019-05-17

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

Highlights - Most important sentences from the article

2018-06-20
1806.07562 | stat.ML

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

Highlights - Most important sentences from the article

2019-04-16

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

Highlights - Most important sentences from the article

2019-04-21
1904.09635 | math.ST

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

Highlights - Most important sentences from the article

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
PDF

Highlights - Most important sentences from the article

2018-11-14
1811.06055 | math.ST

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

Highlights - Most important sentences from the article

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
PDF

Highlights - Most important sentences from the article

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
PDF

Highlights - Most important sentences from the article

2017-10-13
1710.04765 | math.ST

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

Highlights - Most important sentences from the article

2018-11-29

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

Highlights - Most important sentences from the article

2018-03-15
1803.06031 | math.ST

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

Highlights - Most important sentences from the article

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
PDF

Highlights - Most important sentences from the article

2019-01-08
1901.09656 | cs.SI

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

Highlights - Most important sentences from the article

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
PDF

Highlights - Most important sentences from the article

2018-04-05

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

Highlights - Most important sentences from the article