吉林大学学报(工学版) ›› 2016, Vol. 46 ›› Issue (6): 2042-2051.doi: 10.13229/j.cnki.jdxbgxb201606038
黄岚1, 2, 李玉1, 2, 王贵参1, 2, 王岩1, 2
HUANG Lan1, 2, LI Yu1, 2, WANG Gui-shen1, 2, WANG Yan1, 2
摘要: 在复杂网络中节点相似度度量以及密度峰值聚类算法的基础上,提出了一种基于点距离和密度峰值聚类的社区发现方法。首先,提出了基于节点相似度和节点间最短距离的节点距离度量。然后,应用密度峰值聚类方法探究网络中的社区结构,密度峰值聚类算法不仅能够检测出各个社区中心并进行相应的社区扩展,而且能够避免参数选择过程。最后,通过与经典算法在真实数据集和人工合成数据集上的比较实验,充分验证了本文方法的可行性和有效性。
中图分类号:
[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. |
|