一种基于改进密度峰值聚类的社区发现算法
|
摘要
从复杂网络中发现可能存在的群体或社区结构是复杂网络分析的一个重要研究方向.基于密度峰值社区发现的目标是以图聚类的方式来对复杂网络进行社区划分.但是,直接应用密度峰值聚类于社区发现,还存在着如何衡量节点距离和簇中心无法自动选取等问题.在密度峰值聚类算法的基础上,提出一种基于等效电阻距离和自动选取密度峰值簇中心的社区发现算法.首先,在衡量复杂网络中节点的距离上采用了等效电阻路径长度来作为距离度量.其次,在密度峰值算法的决策图上,通过DBSCAN算法自动选取簇中心,而不是通过观察决策图人工选择,以减少人为干扰.最后,在人工合成网络和真实网络上的实验表明,提出的算法具有较高的精度和鲁棒性.
Finding possible communities or community structures from complex networks is an important research direction of complex network analysis. The goal of community discovery based on peak density is to divide complex networks into communities by means of graph clustering. However,there still remains some problems to study,such as how to measure the distance of nodes and how to select the cluster centers automatically. On the basis of the density peak clustering algorithm,a community discovery algorithm based on the equivalent resistance distance calculation and the automatic selection of density peak cluster centers is proposed. Firstly,the equivalent resistance path lengths are used to measure the distance between nodes of the complex networks. Secondly,on the decision graph of the density peak algorithm,the cluster centers are automatically selected by the DBSCAN algorithm,instead of manual selection,so as to reduce human interference. Finally,experiments on the artificial networks and the real networks show that the proposed algorithm has both high precision and strongrobustness.
Finding possible communities or community structures from complex networks is an important research direction of complex network analysis. The goal of community discovery based on peak density is to divide complex networks into communities by means of graph clustering. However,there still remains some problems to study,such as how to measure the distance of nodes and how to select the cluster centers automatically. On the basis of the density peak clustering algorithm,a community discovery algorithm based on the equivalent resistance distance calculation and the automatic selection of density peak cluster centers is proposed. Firstly,the equivalent resistance path lengths are used to measure the distance between nodes of the complex networks. Secondly,on the decision graph of the density peak algorithm,the cluster centers are automatically selected by the DBSCAN algorithm,instead of manual selection,so as to reduce human interference. Finally,experiments on the artificial networks and the real networks show that the proposed algorithm has both high precision and strongrobustness.
引文
[1]Girvan M,Newman M E J.Community structure in social and biological networks[J].Proc.Natl.Acad.Sci.USA 99,2002:7821-7826.
[2]Newman M E J.Fast algorithm for detecting community structure in networks[J].Physical reviewE,2004,69(6):066133.
[3]Raghavan U N,Albert R,Kumara S.Near linear time algorithm to detect community structures in large-scale networks[J].Phys.Rev.E 76,2007:036106.
[4]Xie J,Szymanki B K,Liu X.SLPA:uncovering overlapping communities in social networks via a speaker-listener interaction dynamic process[C].2011 11th IEEE International Conference on Data M ining Workshops,IEEE Computer Society,2011:344-349.
[5]Xu He-li,Ning Nian-wen,Niu Li-jun.Label propagation algorithm for community detection based on vertex local influence[J].Journal of Chinese Computer Systems,2017,38(6):1299-1304.
[6]Xu Cheng-lin,Chen Zhi-gang,Huang Rui,et al.LPA_LRDC tag propagation community discovery algorithm based on optimized leaderRank[J].Journal of Chinese Computer Systems,2017,38(8):1746-1750.
[7]Luo Zhi-gang,Ding Fan,Jiang Xiao-zhou,et al.Newprogress on community detection in complex networks[J].Journal of National University of Defense Technology,2011,33(1):47-52.
[8]Rodriguez A,Laio A.Clustering by fast search and find of density peaks[J].Science,2014,344(6191):1492-1496.
[9]Huang Lan,Li Yu,Wang Gui-shen,et al.Community detection method based on vertex distance and clustering of density peaks[J].Journal of Jilin University,2016,46(6):2042-2051.
[10]Jin Zhi-gang,Xu Pei-xuan.An adaptive community detection algorithm of density peak clustering[J].Journal of Harbin Institute of Technology,2018,50(5):44-51.
[11]Sui Peng.Research on community detection algorithm based on intimacy between users and density peaks[D].Changchun:Jilin University,2017.
[12]Shi Xiao-hu,Feng Guo-xiang,Li Mu,et al.Overlapping community detection method based on density peaks[J].Journal of Jilin U-niversity,2017,47(1):242-248.
[13]Jin H,Wang S,Li C.Community detectionin complex networks by density-based clustering[J].Physica A Statistical M echanics&Its Applications,2013,392(19):4606-4618.
[14]Zhou Zhi-hua.Machine learning:version 1[M].Beijing:Tsinghua University Press,2016.
[15]Luo Zhi-gang,Ding Fan,Jiang Xiao-zhou,et al.Newprogress on community detection in complex networks[J].Journal of National University of Defense Technology,2011,33(1):47-52.
[16]Lancichinetti A,Fortunato S,Radicchi F.Benchmark graphs for testing community detection algorithms[J].Physical ReviewE,78,Article ID:046110.
[17]Gergely Palla,Imre Derenyi,Illes Farkas,et al.Uncovering the overlapping community structure of complex networks in nature and society[J].Nature,2005,435(7043):814-818.
[18]Lancichinetti A,Fortunato S,Kertesz J.Detecting the overlapping and hierarchical community structure in complex networks[J].NewJournal of Physics,2009,11(3):19-44.
[5]许合利,宁念文,牛丽君.一种结合节点局部影响力的标签传播算法[J].小型微型计算机系统,2017,38(6):1299-1304.
[6]徐成林,陈志刚,黄瑞,等.用于社区发现的LPA_LRDC标签传播算法[J].小型微型计算机系统,2017,38(8):1746-1750.
[7]骆志刚,丁凡,蒋晓舟,等.复杂网络社团发现算法研究新进展[J].国防科技大学学报,2011,33(1):47-52.
[9]黄岚,李玉,王贵参,等.基于点距离和密度峰值聚类的社区发现方法[J].吉林大学学报,2016,46(6):2042-2051.
[10]金志刚,徐珮轩.密度峰值聚类的自适应社区发现算法[J].哈尔滨工业大学学报,2018,50(5):44-51.
[11]隋鹏.基于用户亲密度与密度峰值的社区发现算法研究[D].长春:吉林大学,2017.
[12]时小虎,冯国香,李牧,等.基于密度峰值的重叠社区发现算法[J].吉林大学学报(工学版),2017,47(1):242-248.
[14]周志华.机器学习:第1版[M].北京:清华大学出版社,2016.
[2]Newman M E J.Fast algorithm for detecting community structure in networks[J].Physical reviewE,2004,69(6):066133.
[3]Raghavan U N,Albert R,Kumara S.Near linear time algorithm to detect community structures in large-scale networks[J].Phys.Rev.E 76,2007:036106.
[4]Xie J,Szymanki B K,Liu X.SLPA:uncovering overlapping communities in social networks via a speaker-listener interaction dynamic process[C].2011 11th IEEE International Conference on Data M ining Workshops,IEEE Computer Society,2011:344-349.
[5]Xu He-li,Ning Nian-wen,Niu Li-jun.Label propagation algorithm for community detection based on vertex local influence[J].Journal of Chinese Computer Systems,2017,38(6):1299-1304.
[6]Xu Cheng-lin,Chen Zhi-gang,Huang Rui,et al.LPA_LRDC tag propagation community discovery algorithm based on optimized leaderRank[J].Journal of Chinese Computer Systems,2017,38(8):1746-1750.
[7]Luo Zhi-gang,Ding Fan,Jiang Xiao-zhou,et al.Newprogress on community detection in complex networks[J].Journal of National University of Defense Technology,2011,33(1):47-52.
[8]Rodriguez A,Laio A.Clustering by fast search and find of density peaks[J].Science,2014,344(6191):1492-1496.
[9]Huang Lan,Li Yu,Wang Gui-shen,et al.Community detection method based on vertex distance and clustering of density peaks[J].Journal of Jilin University,2016,46(6):2042-2051.
[10]Jin Zhi-gang,Xu Pei-xuan.An adaptive community detection algorithm of density peak clustering[J].Journal of Harbin Institute of Technology,2018,50(5):44-51.
[11]Sui Peng.Research on community detection algorithm based on intimacy between users and density peaks[D].Changchun:Jilin University,2017.
[12]Shi Xiao-hu,Feng Guo-xiang,Li Mu,et al.Overlapping community detection method based on density peaks[J].Journal of Jilin U-niversity,2017,47(1):242-248.
[13]Jin H,Wang S,Li C.Community detectionin complex networks by density-based clustering[J].Physica A Statistical M echanics&Its Applications,2013,392(19):4606-4618.
[14]Zhou Zhi-hua.Machine learning:version 1[M].Beijing:Tsinghua University Press,2016.
[15]Luo Zhi-gang,Ding Fan,Jiang Xiao-zhou,et al.Newprogress on community detection in complex networks[J].Journal of National University of Defense Technology,2011,33(1):47-52.
[16]Lancichinetti A,Fortunato S,Radicchi F.Benchmark graphs for testing community detection algorithms[J].Physical ReviewE,78,Article ID:046110.
[17]Gergely Palla,Imre Derenyi,Illes Farkas,et al.Uncovering the overlapping community structure of complex networks in nature and society[J].Nature,2005,435(7043):814-818.
[18]Lancichinetti A,Fortunato S,Kertesz J.Detecting the overlapping and hierarchical community structure in complex networks[J].NewJournal of Physics,2009,11(3):19-44.
[5]许合利,宁念文,牛丽君.一种结合节点局部影响力的标签传播算法[J].小型微型计算机系统,2017,38(6):1299-1304.
[6]徐成林,陈志刚,黄瑞,等.用于社区发现的LPA_LRDC标签传播算法[J].小型微型计算机系统,2017,38(8):1746-1750.
[7]骆志刚,丁凡,蒋晓舟,等.复杂网络社团发现算法研究新进展[J].国防科技大学学报,2011,33(1):47-52.
[9]黄岚,李玉,王贵参,等.基于点距离和密度峰值聚类的社区发现方法[J].吉林大学学报,2016,46(6):2042-2051.
[10]金志刚,徐珮轩.密度峰值聚类的自适应社区发现算法[J].哈尔滨工业大学学报,2018,50(5):44-51.
[11]隋鹏.基于用户亲密度与密度峰值的社区发现算法研究[D].长春:吉林大学,2017.
[12]时小虎,冯国香,李牧,等.基于密度峰值的重叠社区发现算法[J].吉林大学学报(工学版),2017,47(1):242-248.
[14]周志华.机器学习:第1版[M].北京:清华大学出版社,2016.