Fast Network Community Detection With Profile-Pseudo Likelihood Methods

Wang, Jiangzhou1,2,3; Zhang, Jingfei4; Liu, Binghui1,2; Zhu, Ji5; Guo, Jianhua1,2

2021-12-01

10.1080/01621459.2021.1996378

JOURNAL OF THE AMERICAN STATISTICAL ASSOCIATION   影响因子和分区

0162-1459

1537-274X

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.

Network analysis Profile likelihood Pseudo likelihood Stochastic block model Strong consistency

SCI

英语

其他

National Key R&D Program of China[2020YFA0714102] ; NSFC[11690012,12171079] ; China Postdoctoral Science Foundation[2021M701588] ; Special Fund for Key Laboratories of Jilin Province, China["20190201285JC","DMS2015190"] ; NSF[DMS1821243]

Mathematics

Statistics & Probability

WOS:000728636900001

TAYLOR & FRANCIS INC

MATHEMATICS

Web of Science

1.Northeast Normal Univ, Sch Math & Stat, Jilin 130024, Jilin, Peoples R China
2.Northeast Normal Univ, KLAS, Jilin 130024, Jilin, Peoples R China
3.Southern Univ Sci & Technol, Dept Stat & Data Sci, Shenzhen, Peoples R China
4.Univ Miami, Dept Management Sci, Coral Gables, FL 33124 USA
5.Univ Michigan, Dept Stat, Ann Arbor, MI 48109 USA

Wang, Jiangzhou,Zhang, Jingfei,Liu, Binghui,et al. Fast Network Community Detection With Profile-Pseudo Likelihood Methods[J]. JOURNAL OF THE AMERICAN STATISTICAL ASSOCIATION,2021,118(542).

Wang, Jiangzhou,Zhang, Jingfei,Liu, Binghui,Zhu, Ji,&Guo, Jianhua.(2021).Fast Network Community Detection With Profile-Pseudo Likelihood Methods.JOURNAL OF THE AMERICAN STATISTICAL ASSOCIATION,118(542).

Wang, Jiangzhou,et al."Fast Network Community Detection With Profile-Pseudo Likelihood Methods".JOURNAL OF THE AMERICAN STATISTICAL ASSOCIATION 118.542(2021).