Fast Network Community Detection With Profile-Pseudo Likelihood Methods

• 成果类型: Article
• 署名作者: Wang, Jiangzhou; Zhang, Jingfei; Liu, Binghui; Zhu, Ji; Guo, Jianhua
• 署名单位: Northeast Normal University - China; Northeast Normal University - China; Southern University of Science & Technology; University of Miami; University of Michigan System; University of Michigan
• 刊物名称: JOURNAL OF THE AMERICAN STATISTICAL ASSOCIATION
• ISSN/ISSBN: 0162-1459
• DOI: 10.1080/01621459.2021.1996378
• 发表日期: 2023
• 页码: 1359-1372
• 关键词: stochastic blockmodels; maximum-likelihood; Consistency; approximation; prediction; RECOVERY; MODEL

摘要

The stochastic block model is one of the most studied network models for community detection, and fitting its likelihood function on large-scale networks is known to be challenging. One prominent work that overcomes this computational challenge is the fast pseudo-likelihood approach proposed by Amini et al. for fitting stochastic block models to large sparse networks. However, this approach does not have convergence guarantee, and may not be well suited for small and medium scale networks. In this article, we propose a novel likelihood based approach that decouples row and column labels in the likelihood function, enabling a fast alternating maximization. This new method is computationally efficient, performs well for both small- and large-scale networks, and has provable convergence guarantee. We show that our method provides strongly consistent estimates of communities in a stochastic block model. We further consider extensions of our proposed method to handle networks with degree heterogeneity and bipartite properties. Supplementary materials for this article are available online.