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/

Zendy Plus

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

Zendy Tools

Zendy Open

Community detection is considered for a stochastic block model graph of nvertices, with K vertices in the planted community, edge probability p forpairs of vertices both in the community, and edge probability q for other pairsof vertices.  The main focus of the paper is on weak recovery of the community based on thegraph G, with o(K) misclassified vertices on average, in the sublinear regime$n^{1-o(1)} \leq K \leq o(n).$ A critical parameter is the effectivesignal-to-noise ratio $\lambda=K^2(p-q)^2/((n-K)q)$, with $\lambda=1$corresponding to the Kesten-Stigum threshold. We show that a belief propagationalgorithm achieves weak recovery if $\lambda>1/e$, beyond the Kesten-Stigumthreshold by a factor of $1/e.$ The belief propagation algorithm only needs torun for $\log^\ast n+O(1) $ iterations, with the total time complexity $O(|E|\log^*n)$, where $\log^*n$ is the iterated logarithm of $n.$ Conversely, if$\lambda \leq 1/e$, no local algorithm can asymptotically outperform trivialrandom guessing. Furthermore, a linear message-passing algorithm thatcorresponds to applying power iteration to the non-backtracking matrix of thegraph is shown to attain weak recovery if and only if $\lambda>1$. In addition,the belief propagation algorithm can be combined with a linear-time votingprocedure to achieve the information limit of exact recovery (correctlyclassify all vertices with high probability) for all $K \ge \frac{n}{\log n}\left( \rho_{\rm BP} +o(1) \right),$ where $\rho_{\rm BP}$ is a function of$p/q$.

Recovering a Hidden Community Beyond the Kesten-Stigum Threshold in $O(|E| \log^*|V|)$ Time