Weighted community detection and data clustering using message passing

doi:10.1088/1742-5468/aaa8f5

ITP OpenIR > SCI期刊论文

	Shi, C 1; Liu, YC ; Zhang, P
	Weighted community detection and data clustering using message passing
Source Publication	JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT
Language	英语
Keyword	NETWORKS MODEL
Abstract	Grouping objects into clusters based on the 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 an unweighted community detection problem, we develop a nonparametric method based on statistical physics, by mapping the problem to the 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. In the community detection problem in weighted and directed networks, we show that our algorithm significantly outperforms existing algorithms. In the clustering problem, where the data were generated by mixture models in the sparse regime, we show that our method works all the way down 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 heavily reduce the computation complexity in dense networks but give almost the same performance as belief propagation.
	2018
ISSN	1742-5468
Pages	33405
Subject Area	Mechanics ; Physics
MOST Discipline Catalogue	Mechanics ; Physics, Mathematical
DOI	10.1088/1742-5468/aaa8f5
Indexed By	SCIE
Citation statistics	Cited Times:6[WOS] [WOS Record] [Related Records in WOS]
Document Type	期刊论文
Identifier	http://ir.itp.ac.cn/handle/311006/22948
Collection	SCI期刊论文计算平台成果
Affiliation	1.Chinese Acad Sci, Inst Theoret Phys, CAS Key Lab Theoret Phys, Beijing 100190, Peoples R China 2.Univ Elect Sci & Technol China, CompleX Lab, Web Sci Ctr, Chengdu 611731, Sichuan, Peoples R China 3.Northeastern Univ, Network Sci Inst, 177 Huntington Ave, Boston, MA 02115 USA
Recommended Citation GB/T 7714	Shi, C,Liu, YC,Zhang, P. Weighted community detection and data clustering using message passing[J]. JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT,2018:33405.
APA	Shi, C,Liu, YC,&Zhang, P.(2018).Weighted community detection and data clustering using message passing.JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT,33405.
MLA	Shi, C,et al."Weighted community detection and data clustering using message passing".JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT (2018):33405.

Files in This Item:
File Name/Size	DocType	Version	Access	License
ournal of Statistica（6274KB）	期刊论文	作者接受稿	开放获取	CC BY-NC-SA	Application Full Text

If you have any objections to this item, please fill out the form below and the administrator will contact you as soon as possible.
Content:
Email：	*
Institution:
Verification Code:	Refresh

Any comments and suggestions are welcomed.
Title:	*
Content:
Email：	*
Verification Code:	Refresh

中国科学院理论物理研究所机构知识库