Knowledge Management System of Institute of Theoretical Physics, CAS
Shi, C1; Liu, YC; Zhang, P | |
Weighted community detection and data clustering using message passing | |
发表期刊 | JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT |
语种 | 英语 |
关键词 | NETWORKS MODEL |
摘要 | 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 |
页码 | 33405 |
学科领域 | Mechanics ; Physics |
学科门类 | Mechanics ; Physics, Mathematical |
DOI | 10.1088/1742-5468/aaa8f5 |
收录类别 | SCIE |
引用统计 | |
文献类型 | 期刊论文 |
条目标识符 | http://ir.itp.ac.cn/handle/311006/22948 |
专题 | SCI期刊论文 计算平台成果 |
作者单位 | 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 |
推荐引用方式 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. |
条目包含的文件 | ||||||
文件名称/大小 | 文献类型 | 版本类型 | 开放类型 | 使用许可 | ||
ournal of Statistica(6274KB) | 期刊论文 | 作者接受稿 | 开放获取 | CC BY-NC-SA | 请求全文 |
个性服务 |
推荐该条目 |
保存到收藏夹 |
查看访问统计 |
导出为Endnote文件 |
谷歌学术 |
谷歌学术中相似的文章 |
[Shi, C]的文章 |
[Liu, YC]的文章 |
[Zhang, P]的文章 |
百度学术 |
百度学术中相似的文章 |
[Shi, C]的文章 |
[Liu, YC]的文章 |
[Zhang, P]的文章 |
必应学术 |
必应学术中相似的文章 |
[Shi, C]的文章 |
[Liu, YC]的文章 |
[Zhang, P]的文章 |
相关权益政策 |
暂无数据 |
收藏/分享 |
除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。
修改评论