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

• • 上一篇    下一篇

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

黄岚1, 2, 李玉1, 2, 王贵参1, 2, 王岩1, 2   

  1. 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 Lan1, 2, LI Yu1, 2, WANG Gui-shen1, 2, WANG Yan1, 2   

  1. 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: 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
[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/.
[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.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 李树胜, 钟麦英. 基于PID的航空遥感三轴惯性稳定平台控制系统设计[J]. 吉林大学学报(工学版), 2011, 41(增刊1): 275 -279 .
[2] 刘松山, 王庆年, 王伟华, 林鑫. 惯性质量对馈能悬架阻尼特性和幅频特性的影响[J]. 吉林大学学报(工学版), 2013, 43(03): 557 -563 .
[3] 王同建, 陈晋市, 赵锋, 赵庆波, 刘昕晖, 袁华山. 全液压转向系统机液联合仿真及试验[J]. 吉林大学学报(工学版), 2013, 43(03): 607 -612 .
[4] 张春勤, 姜桂艳, 吴正言. 机动车出行者出发时间选择的影响因素[J]. 吉林大学学报(工学版), 2013, 43(03): 626 -632 .
[5] 肖锐, 邓宗才, 兰明章, 申臣良. 不掺硅粉的活性粉末混凝土配合比试验[J]. 吉林大学学报(工学版), 2013, 43(03): 671 -676 .
[6] 陈思国, 姜旭, 王健, 刘衍珩, 邓伟文, 邓钧忆. 车载自组网与通用移动通信系统混杂网络技术[J]. 吉林大学学报(工学版), 2013, 43(03): 706 -710 .
[7] 孟超, 孙知信, 刘三民. 基于云计算的病毒多执行路径[J]. 吉林大学学报(工学版), 2013, 43(03): 718 -726 .
[8] 仙树, 郑锦, 路兴, 张世鹏. 基于内容转发模型的P2P流量识别算法[J]. 吉林大学学报(工学版), 2013, 43(03): 727 -733 .
[9] 吕源治, 王世刚, 俞珏琼, 王小雨, 李雪松. 基于柱透镜光栅的虚模式下一维集成成像显示特性[J]. 吉林大学学报(工学版), 2013, 43(03): 753 -757 .
[10] 王丹, 李阳, 年桂君, 王珂. 非均质度量掩蔽函数在空域水印中的应用[J]. 吉林大学学报(工学版), 2013, 43(03): 771 -775 .