Distributed Pseudo-Likelihood Method for Community Detection in Large-Scale Networks

Abstract

This paper proposes a distributed pseudo-likelihood method (DPL) to conveniently identify the community structure of large-scale networks. Specifically, we first propose a block-wise splitting method to divide large-scale network data into several subnetworks and distribute them among multiple workers. For simplicity, we assume the classical stochastic block model. Then, the DPL algorithm is iteratively implemented for the distributed optimization of the sum of the local pseudo-likelihood functions. At each iteration, the worker updates its local community labels and communicates with the master. The master then broadcasts the combined estimator to each worker for the new iterative steps. Based on the distributed system, DPL significantly reduces the computational complexity of the traditional pseudo-likelihood method using a single machine. Furthermore, to ensure statistical accuracy, we theoretically discuss the requirements of the worker sample size. Moreover, we extend the DPL method to estimate degree-corrected stochastic block models. The superior performance of the proposed distributed algorithm is demonstrated through extensive numerical studies and real data analysis.

References in corpus (21)

• Community structure in social and biological networks
• Finding and evaluating community structure in networks
• Stochastic blockmodels and community structure in networks
• Mixed membership stochastic blockmodels
• Spectral clustering and the high-dimensional stochastic blockmodel
• Consistency of spectral clustering in stochastic block models
• Fast community detection by SCORE
• Community Detection via Maximization of Modularity and Its Variants
• Consistency of community detection in networks under degree-corrected stochastic block models
• Pseudo-likelihood methods for community detection in large sparse networks
• Latent Space Models for Dynamic Networks
• Community extraction for social networks
• Robust and computationally feasible community detection in the presence of arbitrary outlier nodes
• On Communication Cost of Distributed Statistical Estimation and Dimensionality
• First-order Newton-type Estimator for Distributed Estimation and Inference
• Communication-efficient sparse regression: a one-shot approach
• Distributed High-dimensional Regression Under a Quantile Loss Function
• GIANT: Globally Improved Approximate Newton Method for Distributed Optimization
• Divide-and-conquer based Large-Scale Spectral Clustering
• Subsampling Spectral Clustering for Large-Scale Social Networks
• Distributed Community Detection in Large Networks