基于点距离和密度峰值聚类的社区发现方法

doi:10.13229/j.cnki.jdxbgxb201606038

吉林大学学报(工学版) ›› 2016, Vol. 46 ›› Issue (6): 2042-2051.doi: 10.13229/j.cnki.jdxbgxb201606038

基于点距离和密度峰值聚类的社区发现方法

黄岚^{1, 2}, 李玉^{1, 2}, 王贵参^{1, 2}, 王岩^{1, 2}

1.吉林大学计算机科学与技术学院,长春 130012;
2.吉林大学符号计算与知识工程教育部重点实验室,长春 130012

收稿日期:2015-10-26 出版日期:2016-11-20 发布日期:2016-11-20
通讯作者: 王岩(1978-),男,副教授,博士.研究方向:网络结构分析与生物信息学.E-mail:wy6868@jlu.edu.cn
作者简介:黄岚(1974-),女,教授,博士生导师.研究方向:社区发现,数据挖掘,商务智能.
基金资助:
国家自然科学基金项目(61472159,61572227)

Community detection method based on vertex distance and clustering of density peaks

HUANG Lan^{1, 2}, LI Yu^{1, 2}, WANG Gui-shen^{1, 2}, WANG Yan^{1, 2}

1.College of Computer Science and Technology, Jilin University, Changchun 130012, China;
2.Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education, Jilin University, Changchun 130012, China

Received:2015-10-26 Online:2016-11-20 Published:2016-11-20

摘要/Abstract

摘要： 在复杂网络中节点相似度度量以及密度峰值聚类算法的基础上,提出了一种基于点距离和密度峰值聚类的社区发现方法。首先,提出了基于节点相似度和节点间最短距离的节点距离度量。然后,应用密度峰值聚类方法探究网络中的社区结构,密度峰值聚类算法不仅能够检测出各个社区中心并进行相应的社区扩展,而且能够避免参数选择过程。最后,通过与经典算法在真实数据集和人工合成数据集上的比较实验,充分验证了本文方法的可行性和有效性。

关键词: 计算机应用, 社区发现, 节点距离, 密度峰值聚类, 复杂网络

Abstract: Based on vertex similarity in complex network and density peaks clustering, a community detection method is proposed. First, a vertex distance calculation based on vertex similarity and the shortest distance between vertexes is proffered. Then, the density peaks clustering method is applied to detect the community structure in network. The density peaks clustering method not only allows the detection of the community centers to establish the epicenter for community expansion, but also avoids the process of selecting parameters. The proposed method is compared with the classic algorithms on both real-world networks and synthetic networks. Experimental results demonstrate that the proposed community detection method is practicable and effective.

Key words: computer application, community detection, vertex distance, density peaks clustering(DPC), complex network

中图分类号:

TP301.6

黄岚, 李玉, 王贵参, 王岩. 基于点距离和密度峰值聚类的社区发现方法[J]. 吉林大学学报(工学版), 2016, 46(6): 2042-2051.

HUANG Lan, LI Yu, WANG Gui-shen, WANG Yan. Community detection method based on vertex distance and clustering of density peaks[J]. 吉林大学学报(工学版), 2016, 46(6): 2042-2051.

参考文献

[1] Girvan M, Newman M E J. Community structure in social and biological networks[J]. Proceedings of the National Academy of Sciences,2002,99(12):7821-7826.
[2] Newman M E J, Girvan M. Finding and evaluating community structure in networks[J]. Physical Review E,2004,69(2):026113.
[3] Newman M E J. Fast algorithm for detecting community structure in networks[J]. Physical Review E,2004,69(6):066133.
[4] Clauset A, Newman M E J, Moore C. Finding community structure in very large networks[J]. Physical Review E,2004,70(6):066111.
[5] Zhu X, Ghahramani Z, Lafferty J. Semi-supervised learning using gaussian fields and harmonic functions[C]∥ICML, Washington DC,USA,2003:912-919.
[6] Raghavan U N, Albert R, Kumara S. Near linear time algorithm to detect community structures in large-scale networks[J]. Physical Review E,2007,76(3):036106.
[7] Barber M J, Clark J W. Detecting network communities by propagating labels under constraints[J]. Physical Review E,2009,80(2):026129.
[8] Liu X, Murata T. Advanced modularity-specialized label propagation algorithm for detecting communities in networks[J]. Physica A: Statistical Mechanics and its Applications,2010,389(7):1493-1500.
[9] Rosvall M, Bergstrom C T. An information-theoretic framework for resolving community structure in complex networks[J]. Proceedings of the National Academy of Sciences,2007,104(18):7327-7331.
[10] Rosvall M, Bergstrom C T. Maps of random walks on complex networks reveal community structure[J]. Proceedings of the National Academy of Sciences,2008,105(4):1118-1123.
[11] Pons P, Latapy M. Computing Communities in Large Networks using Random Walks[M]. Berlin Heidelberg:Springer,2005:284-293.
[12] Lancichinetti A, Radicchi F, Ramasco J J, et al. Finding statistically significant communities in networks[J]. PLoS One,2011,6(4):e18961.
[13] Lancichinetti A, Fortunato S. Consensus clustering in complex networks[J]. Scientific Reports,2012,2:00336.
[14] 周春光,曲鹏程,王曦,等. DSNE: 一个新的动态社会网络分析算法[J]. 吉林大学学报:工学版, 2008,38(2):408-413.
Zhou Chun-guang,Qu Peng-cheng,Wang Xi, et al. DSNE: a new dynamic social network analysis algorithm[J]. Journal of Jilin University (Engineering and Technology Edition),2008,38(2):408-413.
[15] 才华,周春光,卢廷玉,等. 重叠社区结构的挖掘算法[J]. 吉林大学学报:工学版,2009,39(4):1035-1040.
Cai Hua,Zhou Chun-guang,Lu Ting-yu,et al. OCSMA:an algorithm to mine overlapping community structure in networks[J]. Journal of Jilin University (Engineering and Technology Edition),2009,39(4):1035-1040.
[16] Huang L,Wang G S,Wang Y,et al. Link clustering with extended link similarity and EQ evaluation division[J]. PLoS One,2013,8(6):e66005.
[17] Rodriguez A,Laio A. Clustering by fast search and find of density peaks[J]. Science,2014,344(6191):1492-1496.
[18] Hennig C, Hausdorf B. Design of dissimilarity measures: a new dissimilarity between species distribution areas[DB/OL].[2015-09-24].https://www.ucl.ac.uk/statistics/research/pdfs/rr273.pdf.
[19] Shao J,Han Z,Yang Q,et al. Community detection based on distance dynamics[C]∥Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Sydney,Australia,2015:1075-1084.
[20] Zachary W W. An information flow model for conflict and fission in small groups[J]. Journal of Anthropological Research, 1977,33(4):452-473.
[21] Lusseau D, Schneider K, Boisseau O J, et al. The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations[J]. Behavioral Ecology and Sociobiology,2003,54(4):396-405.
[22] Gleiser P M, Danon L. Community structure in jazz[J]. Advances in Complex Systems,2003,6(4):565-573.
[23] Watts D J, Strogatz S H. Collective dynamics of ‘small-world’ networks[J]. Nature,1998,393(6684):440-442.
[24] Lancichinetti A, Fortunato S, Radicchi F. Benchmark graphs for testing community detection algorithms[J]. Physical Review E,2008,78(4):046110.
[25] 孙延维,彭智明,李健波.基于粒子群优化与模糊聚类的社区发现算法[J].重庆邮电大学学报:自然科学版,2015,27(5):660-666.
Sun Yan-zhi,Peng Zhi-ming,Li Jian-bo. Community detection algorithm based on particle swarm optimization and fuzzy clustering [J].Journal of Chongqing University of Posts and Telecommunications(Natural Science Edition),2015,27(5):660-666.
[26] Lancichinetti A, Fortunato S, Kertész J. Detecting the overlapping and hierarchical community structure in complex networks[J]. New Journal of Physics,2009,11(3):033015.
[27] MultiplexNMI package[DB/OL].[2015-09-28]. https://sites.google.com/site/andrealancichinetti/files.
[28] Igraph R package[DB/OL].[2015-09-24].https://igraph.org/r/.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

基于点距离和密度峰值聚类的社区发现方法

Community detection method based on vertex distance and clustering of density peaks

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 10

[1]	刘富,宗宇轩,康冰,张益萌,林彩霞,赵宏伟. 基于优化纹理特征的手背静脉识别系统[J]. 吉林大学学报(工学版), 2018, 48(6): 1844-1850.
[2]	王利民,刘洋,孙铭会,李美慧. 基于Markov blanket的无约束型K阶贝叶斯集成分类模型[J]. 吉林大学学报(工学版), 2018, 48(6): 1851-1858.
[3]	金顺福,王宝帅,郝闪闪,贾晓光,霍占强. 基于备用虚拟机同步休眠的云数据中心节能策略及性能[J]. 吉林大学学报(工学版), 2018, 48(6): 1859-1866.
[4]	赵东,孙明玉,朱金龙,于繁华,刘光洁,陈慧灵. 结合粒子群和单纯形的改进飞蛾优化算法[J]. 吉林大学学报(工学版), 2018, 48(6): 1867-1872.
[5]	刘恩泽,吴文福. 基于机器视觉的农作物表面多特征决策融合病变判断算法[J]. 吉林大学学报(工学版), 2018, 48(6): 1873-1878.
[6]	欧阳丹彤, 范琪. 子句级别语境感知的开放信息抽取方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1563-1570.
[7]	刘富, 兰旭腾, 侯涛, 康冰, 刘云, 林彩霞. 基于优化k-mer频率的宏基因组聚类方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1593-1599.
[8]	桂春, 黄旺星. 基于改进的标签传播算法的网络聚类方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1600-1605.
[9]	刘元宁, 刘帅, 朱晓冬, 陈一浩, 郑少阁, 沈椿壮. 基于高斯拉普拉斯算子与自适应优化伽柏滤波的虹膜识别[J]. 吉林大学学报(工学版), 2018, 48(5): 1606-1613.
[10]	车翔玖, 王利, 郭晓新. 基于多尺度特征融合的边界检测算法[J]. 吉林大学学报(工学版), 2018, 48(5): 1621-1628.
[11]	赵宏伟, 刘宇琦, 董立岩, 王玉, 刘陪. 智能交通混合动态路径优化算法[J]. 吉林大学学报(工学版), 2018, 48(4): 1214-1223.
[12]	黄辉, 冯西安, 魏燕, 许驰, 陈慧灵. 基于增强核极限学习机的专业选择智能系统[J]. 吉林大学学报(工学版), 2018, 48(4): 1224-1230.
[13]	傅文博, 张杰, 陈永乐. 物联网环境下抵抗路由欺骗攻击的网络拓扑发现算法[J]. 吉林大学学报(工学版), 2018, 48(4): 1231-1236.
[14]	曹洁, 苏哲, 李晓旭. 基于Corr-LDA模型的图像标注方法[J]. 吉林大学学报(工学版), 2018, 48(4): 1237-1243.
[15]	侯永宏, 王利伟, 邢家明. 基于HTTP的动态自适应流媒体传输算法[J]. 吉林大学学报(工学版), 2018, 48(4): 1244-1253.