Weighted community detection and data clustering using message passing
From MaRDI portal
Abstract: Grouping objects into clusters based on similarities or weights between them is one of the most important problems in science and engineering. In this work, by extending message passing algorithms and spectral algorithms proposed for unweighted community detection problem, we develop a non-parametric method based on statistical physics, by mapping the problem to Potts model at the critical temperature of spin glass transition and applying belief propagation to solve the marginals corresponding to the Boltzmann distribution. Our algorithm is robust to over-fitting and gives a principled way to determine whether there are significant clusters in the data and how many clusters there are. We apply our method to different clustering tasks and use extensive numerical experiments to illustrate the advantage of our method over existing algorithms. In the community detection problem in weighted and directed networks, we show that our algorithm significantly outperforms existing algorithms. In the clustering problem when the data was generated by mixture models in the sparse regime we show that our method works to the theoretical limit of detectability and gives accuracy very close to that of the optimal Bayesian inference. In the semi-supervised clustering problem, our method only needs several labels to work perfectly in classic datasets. Finally, we further develop Thouless-Anderson-Palmer equations which reduce heavily the computation complexity in dense-networks but gives almost the same performance as belief propagation.
Recommendations
- Weighted message passing and minimum energy flow for heterogeneous stochastic block models with side information
- Community detection for weighted networks with unknown number of communities
- Clustering by passing messages between data points
- Algorithms and Models for the Web-Graph
- Overlapping community detection in weighted networks via a Bayesian approach
Cites work
- Clustering and community detection in directed networks: a survey
- Clustering by passing messages between data points
- Community structure in social and biological networks
- Evaluating accuracy of community detection using the relative normalized mutual information
- Fast computation of low-rank matrix approximations
- Fast unfolding of communities in large networks
- Information, Physics, and Computation
- Printer graphics for clustering
- Reconstruction and estimation in the planted partition model
- Spectral redemption in clustering sparse networks
Cited in
(6)- Weighted message passing and minimum energy flow for heterogeneous stochastic block models with side information
- Multilayer modularity belief propagation to assess detectability of community structure
- On tuning a mean-field model for semi-supervised classification
- Nishimori meets Bethe: a spectral method for node classification in sparse weighted graphs
- An improved belief propagation algorithm for detecting mesoscale structure in complex networks
- Community detection with the weighted parsimony criterion
This page was built for publication: Weighted community detection and data clustering using message passing
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4964522)
