"Estimation of the number of communities for sparse networks" by Sharmodeep Bhattacharyya from Oregon State University in STAG 213.

Link to Probability and Data Science Seminar.

Abstract: Among the non-parametric methods of estimating the number of communities (K) in a community detection problem, methods based on the spectrum of the Bethe Hessian matrices ($\vH_\zeta$ with the scalar parameter $\zeta$) have garnered much popularity for their simplicity, computational efficiency, and robustness to the sparsity of data. For certain heuristic choices of $\zeta$, such methods have been shown to be consistent for networks with $N$ nodes with a common expected degree of $\omega(\log N)$. In this paper, we obtain several finite sample results to show that if the input network is generated from either stochastic block models or degree-corrected block models, and if $\zeta$ is chosen from a certain interval, then the associated spectral methods based on $\vH_\zeta$ is consistent for estimating K for the sub-logarithmic sparse regime, when the expected maximum degree is $o(\log N)$ and $\omega(1)$, under some mild conditions even in the situation when K increases with N. We also propose a method to empirically estimate the aforementioned interval, enabling us to develop a consistent K estimation procedure in the sparse regime. We evaluate the performance of the resulting estimation procedure's performance theoretically and empirically through extensive simulation studies and application to a comprehensive collection of real-world network data.