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

New phase transition phenomena have recently been discovered for thestochastic block model, for the special case of two non-overlapping symmetriccommunities. This gives raise in particular to new algorithmic challengesdriven by the thresholds. This paper investigates whether a general phenomenontakes place for multiple communities, without imposing symmetry.  In the general stochastic block model $\text{SBM}(n,p,Q)$, $n$ vertices aresplit into $k$ communities of relative size $\{p_i\}_{i \in [k]}$, and verticesin community $i$ and $j$ connect independently with probability$\{Q_{i,j}\}_{i,j \in [k]}$. This paper investigates the partial and exactrecovery of communities in the general SBM (in the constant and logarithmicdegree regimes), and uses the generality of the results to tackle overlappingcommunities.  The contributions of the paper are: (i) an explicit characterization of therecovery threshold in the general SBM in terms of a new divergence function$D_+$, which generalizes the Hellinger and Chernoff divergences, and whichprovides an operational meaning to a divergence function analog to theKL-divergence in the channel coding theorem, (ii) the development of analgorithm that recovers the communities all the way down to the optimalthreshold and runs in quasi-linear time, showing that exact recovery has noinformation-theoretic to computational gap for multiple communities, incontrast to the conjectures made for detection with more than 4 communities;note that the algorithm is optimal both in terms of achieving the threshold andin having quasi-linear complexity, (iii) the development of an efficientalgorithm that detects communities in the constant degree regime with anexplicit accuracy bound that can be made arbitrarily close to 1 when aprescribed signal-to-noise ratio (defined in term of the spectrum of$\diag(p)Q$) tends to infinity.

Community detection in general stochastic block models: fundamental limits and efficient recovery algorithms