论文研究-一种基于密度峰值聚类的社区发现算法 .pdf
需积分: 3 102 浏览量
2019-08-19
20:28:13
上传
评论
收藏 349KB PDF 举报
http://www.paper.edu.cn
- 1 -
中国科技论文在线
一种基于密度峰值聚类的社区发现算法
#
白亮
1
，赵越
2
，杜航原
2*
（1. 山西大学智能信息处理研究所，太原 030006；
2. 山西大学计算机与信息技术学院，太原 030006）5
基金项目：国家自然科学基金（61305073）；高等学校博士学科点专项科研基金（20131401120001）
作者简介：白亮（1982 年-），男，副教授，硕导，主要研究方向：机器学习. E-mail: bailiang@sxu.edu.cn
摘要： 社区发现是网络数据挖掘的一个重要研究内容，被用于探索复杂网络中潜在的类结构。针对网络数
据，本文对一种密度峰值聚类算法“Clustering by fast search and find of density peaks”（DP）进
行了扩展，提出了新的节点局部密度和节点之间的相似性度量，使得该算法能够有效应用于网络社区发现
中。新扩展的算法不仅继承了原算法能够发现任意形状的类结构的优点，而且能有效快速地处理网络数据。10
最后，通过在真实网络数据上的实验分析展示了新算法的有效性。
关键词：计算机应用；复杂网络；社区发现；密度峰值聚类
中图分类号：TN92; O41
A new community detection algorithm based on 15
density-peaks clustering
BAI Liang
1
, ZHAO Yue
2
, DU Hangyuan
2
(1. Institute of Intelligent Information Processing
，
Taiyuan 030006;
2. School of Computer and Information Technology, Shanxi University, Taiyuan 030006)
Abstract: Community detection is an important technique, which is used to discover the cluster 20
structure on networks. The density clustering algorithm "Clustering by fast search and find of density
peaks"(DP) is extended for network data. This paper proposes a new local density and dissimilarity
measure for nodes, so that the DP algorithm can be applied to the community discovery on networks.
The extended algorithm not only inherits the advantages of the original algorithm which can find the
class structure of any shape, but also it can quickly and effectively process network data. Finally, the 25
experimental analysis on several real network data shows the effectiveness of the new algorithm.
Key words: Computer application technology; Complex networks; Community detection; Density
peaks clustering
30
0 引言
最近，由于数据在众多复杂系统中被建模为网络
[1]
，如社交网络和生物网络等，越来越
多学者关注于复杂网络的聚类结构分析。在网络分析中，聚类结构也被称为“社区结构”
[2][3]
，
它是网络的一个重要性质。直观理解，在复杂网络中，一个社区（簇）由一组节点的连接群
构成，这些节点相互联系非常紧密但与网络中其它密集群的节点连接稀疏。社区发现的目标
35
是通过使用网络的拓扑信息来识别社区。它可以被视为图聚类过程，已成为一种探索和理解
网络如何工作的重要任务之一
[4]
。为了解决社区发现的问题，各种各样的图聚类方法已经发
展
[5]
，包括潜在空间模型
[6]
、非负矩阵分解
[7]
、块模型近似
[8]
、谱聚类
[9][10][11]
和模块最大化
[12][13][14]
。根据不同的用户需求，这些模型有着不同的社区定义或聚类标，已经成功的应用
到了不同的领域。然而，它们大部分是基于特征提取和层次聚类策略完成社区发现。这些操
40
作的计算成本高昂，限制了它们在处理大规模网络上的效率。为此，我希望将一种快速的密
度聚类算法“Clustering by fast search and find of density peaks”（DP）
[15]
应用于社区发现中。
资源评论
