A distributed community detection algorithm for large scale networks under stochastic block models
From MaRDI portal
Publication:6096648
DOI10.1016/J.CSDA.2023.107794arXiv2009.11747OpenAlexW4379379817MaRDI QIDQ6096648FDOQ6096648
Authors:
Publication date: 15 September 2023
Published in: Computational Statistics and Data Analysis (Search for Journal in Brave)
Abstract: With rapid developments of information and technology, large scale network data are ubiquitous. In this work we develop a distributed spectral clustering algorithm for community detection in large scale networks. To handle the problem, we distribute l pilot network nodes on the master server and the others on worker servers. A spectral clustering algorithm is first conducted on the master to select pseudo centers. The indexes of the pseudo centers are then broadcasted to workers to complete distributed community detection task using a SVD type algorithm. The proposed distributed algorithm has three merits. First, the communication cost is low since only the indexes of pseudo centers are communicated. Second, no further iteration algorithm is needed on workers and hence it does not suffer from problems as initialization and non-robustness. Third, both the computational complexity and the storage requirements are much lower compared to using the whole adjacency matrix. A Python package DCD (www.github.com/Ikerlz/dcd) is developed to implement the distributed algorithm for a Spark system. Theoretical properties are provided with respect to the estimation accuracy and mis-clustering rates. Lastly, the advantages of the proposed methodology are illustrated by experiments on a variety of synthetic and empirical datasets.
Full work available at URL: https://arxiv.org/abs/2009.11747
Recommendations
- A spectral method for community detection in moderately sparse degree-corrected stochastic block models
- Subsampling spectral clustering for stochastic block models in large-scale networks
- Pseudo-likelihood methods for community detection in large sparse networks
- scientific article; zbMATH DE number 7307464
- Find Your Place: Simple Distributed Algorithms for Community Detection
stochastic block modelcommunity detectiondistributed systemlarge scale networkdistributed spectral clustering
Cites Work
- A nonparametric view of network models and Newman–Girvan and other modularities
- Spectral clustering and the high-dimensional stochastic blockmodel
- Pseudo-likelihood methods for community detection in large sparse networks
- Consistency of community detection in networks under degree-corrected stochastic block models
- Consistency of spectral clustering in stochastic block models
- Community detection and stochastic block models: recent developments
- Fast community detection by SCORE
- Entrywise eigenvector analysis of random matrices with low expected rank
- A tensor approach to learning mixed membership community models
- TENET: tail-event driven network risk
- Role of normalization in spectral clustering for stochastic blockmodels
- Numerical methods for large eigenvalue problems
- Divide and conquer local average regression
- Co-clustering directed graphs to discover asymmetries and directional communities
- Distributed testing and estimation under sparse high dimensional models
- Communication-efficient algorithms for statistical optimization
- Distributed semi-supervised learning with kernel ridge regression
- Peer effects in bedtime decisions among adolescents: a social network model with sampled data
- Distributed estimation of principal eigenspaces
- Multivariate spatial autoregressive model for large scale social networks
- Distributed one-step upgraded estimation for non-uniformly and non-randomly distributed data
- Scalable and Robust Community Detection with Randomized Sketching
Cited In (4)
This page was built for publication: A distributed community detection algorithm for large scale networks under stochastic block models
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6096648)
