| 引用本文: | 金志刚,徐珮轩.密度峰值聚类的自适应社区发现算法[J].哈尔滨工业大学学报,2018,50(5):44.DOI:10.11918/j.issn.0367-6234.201704101 |
| JIN Zhigang,XU Peixuan.An adaptive community detection algorithm of density peak clustering[J].Journal of Harbin Institute of Technology,2018,50(5):44.DOI:10.11918/j.issn.0367-6234.201704101 |
|
| 摘要: |
| 为减少社区发现算法中参数的选择对社区划分的影响, 同时使算法能够自适应地进行社区划分, 本文提出一种基于核密度估计的密度峰值聚类的社区发现算法KDED.首先, 定义一种基于信任度的距离度量, 将社交网络中的用户关系量化为距离矩阵, 使用矩阵元素的大小度量用户关系的紧密程度；然后对距离矩阵进行核密度估计, 统计各个节点在网络中的影响大小，结合热扩散模型改进计算流程，使其自适应不同规模的数据集以提高计算精度；结合密度峰值聚类原理和社区属性确定社区中心节点后, 可根据节点间的距离得到社区内部层次结构和社区外部的自然结构；最后将剩余节点按距离分配到相应的社区当中以完成社区划分.仿真结果表明：通过可视化软件可观察到，通过KDED算法得到的社区划分结果具有清晰的自然结构和内部层次结构；随着社区规模的提升以及划分难度增加, KDED算法具有出色的稳定性；在真实数据集以及LFR基准网络上均得到较为接近真实划分结果的社区划分, 自适应性良好, 验证算法的可行性与有效性.
|
| 关键词: 社区发现 密度峰值聚类 信任度 核密度估计 自适应 |
| DOI：10.11918/j.issn.0367-6234.201704101 |
| 分类号:TP393 |
| 文献标识码:A |
| 基金项目:国家自然科学基金(61571318) |
|
| An adaptive community detection algorithm of density peak clustering |
|
JIN Zhigang,XU Peixuan
|
|
(School of Electrical and Information Engineering, Tianjin University, Tianjin 300072, China)
|
| Abstract: |
| In order to reduce the influence of the selection of parameters in community detection algorithm on the results of community partitioning and detect adaptively, a community detection algorithm called KDED based on kernel density estimation for density peak clustering is proposed. Firstly, a distance measure based on trust is defined, and the user relationship in the social network is quantified as a distance matrix. Then the kernel density is estimated by the distance matrix to calculate the influence of each node on the network. The thermal diffusion model improves the computational flow so that it adapts to different sizes of data sets to improve computational accuracy. The clustering center is determined by density peak clustering principle and community property, and the node is allocated to the corresponding community which can obtain the hierarchical structure within the community and the natural structure among the community. The simulation results show that it can be observed by the visualization software that the community division result obtained by the KDED algorithm has a clear natural structure and internal hierarchical structure. The KDED algorithm has the best stability with the increase in the size of the community and the difficulty of detection compared with the classical algorithm. And it gets a community partition closer to the real partition in the real data set and the LFR benchmark network, which verifies the feasibility and effectiveness of the algorithm.
|
| Key words: community detection density peak clustering trust degree kernel density estimation adaptive |
