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

Community detection in the stochastic block model is one of the centralproblems of graph clustering. Since its introduction, many subsequent papershave made great strides in solving and understanding this model. In this setup,spectral algorithms have been one of the most widely used frameworks. However,despite the long history of study, there are still unsolved challenges. One ofthe main open problems is the design and analysis of "simple"(vanilla) spectralalgorithms, especially when the number of communities is large.  In this paper, we provide two algorithms. The first one is based on thepower-iteration method. It is a simple algorithm which only compares the rowsof the powered adjacency matrix. Our algorithm performs optimally (up tologarithmic factors) compared to the best known bounds in the dense graphregime by Van Vu (Combinatorics Probability and Computing, 2018). Furthermore,our algorithm is also robust to the "small cluster barrier", recovering largeclusters in the presence of an arbitrary number of small clusters. Then basedon a connection between the powered adjacency matrix and eigenvectors, weprovide a vanilla spectral algorithm for large number of communities in thebalanced case. This answers an open question by Van Vu (CombinatoricsProbability and Computing, 2018) in the balanced case. Our methods alsopartially solve technical barriers discussed by Abbe, Fan, Wang and Zhong(Annals of Statistics, 2020).  In the technical side, we introduce a random partition method to analyze eachentry of a powered random matrix. This method can be viewed as an eigenvectorversion of Wigner's trace method. Recall that Wigner's trace method links thetrace of powered matrix to eigenvalues. Our method links the whole poweredmatrix to the span of eigenvectors. We expect our method to have moreapplications in random matrix theory.

Detecting Hidden Communities by Power Iterations with Connections to Vanilla Spectral Algorithms