基于共邻节点相似度的社区划分算法
|
摘要
复杂网络中的社区结构能帮助人们认识网络的基本结构及其功能。针对目前多数社区划分算法准确率低、复杂度高的问题,提出了一种基于共邻节点相似度的社区划分算法。首先,为了计算节点间相似度值,提出了相似度模型,该模型通过将被测节点对的邻居节点引入一并计算,提高了相似度度量的准确性;然后,计算节点局部影响力值,能客观地表现出节点在所处网络中的重要性;其次,结合节点相似度值和节点局部影响力值对节点进行层次聚类,完成网络社区结构的初步划分;最后,通过聚合初步划分的子社区,获得复杂网络的最优模块度值。仿真结果表明,在网络的社区特征模糊时,与新的基于局部相似度的社区发现算法(CDALS)相比,所提算法的准确率提高了14%,证明了所提提法更能够准确、有效地划分复杂网络的社区结构。
The community structure in complex networks can help people recognize basic structure and functions of network. Aiming at the problems of low accuracy and high complexity of most community division algorithms, a community division algorithm based on similarity of common neighbor nodes was proposed. Firstly, a similarity model was proposed in order to calculate the similarity between nodes. In the model, the accuracy of similarity measurement was improved by calculating the tested node pairs and their neighbor nodes together. Secondly, local influence values of nodes were calculated, objectively showing the importances of nodes in the network. Thirdly, the nodes were hierarchically clustered according to the similarity and local influence values of nodes, and preliminary division of network community structure was completed. Finally, the preliminary divided sub-communities were clustered until the optimal modularity value was obtained. The simulation results show that compared with the new Community Detection Algorithm based on Local Similarity(CDALS), the proposed algorithm has the accuuracy improved by 14%, which proves that the proposed algorithm can divide the community structure of complex networks accurately and effectively.
The community structure in complex networks can help people recognize basic structure and functions of network. Aiming at the problems of low accuracy and high complexity of most community division algorithms, a community division algorithm based on similarity of common neighbor nodes was proposed. Firstly, a similarity model was proposed in order to calculate the similarity between nodes. In the model, the accuracy of similarity measurement was improved by calculating the tested node pairs and their neighbor nodes together. Secondly, local influence values of nodes were calculated, objectively showing the importances of nodes in the network. Thirdly, the nodes were hierarchically clustered according to the similarity and local influence values of nodes, and preliminary division of network community structure was completed. Finally, the preliminary divided sub-communities were clustered until the optimal modularity value was obtained. The simulation results show that compared with the new Community Detection Algorithm based on Local Similarity(CDALS), the proposed algorithm has the accuuracy improved by 14%, which proves that the proposed algorithm can divide the community structure of complex networks accurately and effectively.
引文
[1] STROGATZ S H.Exploring complex networks [J].Nature,2001,410:268-276.
[2] SCHEFFER M.Complex systems:foreseeing tipping points[J].Nature,2010,467(7314):411-412.
[3] KARSAI M,KIVEL M,PAN R K,et al.Small but slow world:How network topology and burstiness slow down spreading[J].Physical Review E,2011,83(2):025102.
[4] 吴泓润,覃俊,易云飞,等.基于优化理论的社区无标度网络模型[J].计算机学报,2015,38(2):337-348.(WU H R,TAN J,YI Y F,et al.A model of community-structure and scale-free network based on optimization theory[J].Chinese Journal of Computers,2015,38(2):337-348.)
[5] 付立冬,马小科,聂靖靖.进化谱分算法检测动态网络社团结构[J].西安电子科技大学学报(自然科学版),2018,45(2):43-47(FU L D,MA X K,NIE J J.Evolutionary spectral approach to finding communities in dynamic networks [J].Journal of Xidian University (Natural Science),2018,45(2):43-47.)
[6] 刘冰玉,王翠荣,王聪,等.基于动态主题模型融合多维数据的微博社区发现算法[J].软件学报,2017,28(2):246-261.(LIU B Y,WANG C R,WANG C,et al.Microblog community discovery algorithm based on dynamic topic model with multidimensional data fusion[J].Journal of Software,2017,28(2):246-261.)
[7] 付立东,聂靖靖.基于进化谱分方法的动态社团检测[J].计算机科学,2018,45(2):171-174.(FU L D,NIE J J.Dynamic community detection based on evolutionary spectral method [J].Computer Science,2018,45(2):171-174.)
[8] ALBERT R,JEONG H,BARABASI A L.The diameter of the World Wide Web [J].Nature,1999,401(6):130-131.
[9] 顾亦然,陈雨晴.一种新的基于局部相似度的社区发现算法[J].南京邮电大学学报(自然科学版),2017,37(5):196-203.(GU Y R,CHEN Y Q.New community detection algorithm based on local similarity[J].Journal of Nanjing University of Posts and Telecommunications (Natural Science Edition),2017,37(5):196-203.)
[10] 梁宗文,杨帆,李建平.基于节点相似性度量的社团结构划分方法[J].计算机应用,2015,35(5):1213-1217.(LIANG Z W,YANG F,LI J P.Community structure detection based on node similarity in complex network[J].Journal of Computer Applications,2015,35(5):1213-1217.)
[11] 刘旭,易东云.基于局部相似性的复杂网络社区发现方法[J].自动化学报,2011,37(12):1520-1529.(LIU X,YI D Y.Complex network community detection by local similarity[J].Acta Automatica Sinica,2011,37(12):1520-1529.)
[12] CHEN Q,WU T T,FANG M.Detecting local community structures in complex networks based on local degree central nodes [J].Physica A:Statistical Mechanics and its Applications,2013,392(3):529-537.
[13] BLONDEL V D,GUILLAUME J L,LAMBIOTTE R,et al.Fast unfolding of communities in large networks[J].Journal of Statistical Mechanics:Theory and Experiment,2008(10):1-12.
[14] LAMBIOTTE R,DELVENNE J C,BARAHONA M.Laplacian dynamics and multiscale modular structure in networks[J].ArXiv Preprint,2008,2008:0812.1770.
[15] CLAUSET A,NEWMAN M E J,MOORE C.Finding community structure in very large networks[J].Physical Review E,2004,70(6):066111.
[16] NEWMAN M E J.Fast algorithm for detecting community structure in networks[J].Physical Review E,2004,69(6):066133.
[17] GIRVAN M,NEWMAN M E J.Community structure in social and biological networks[J].Proceedings of the National Academy of Sciences of Sciences of the United States of America,2002,99(12):7821-7826.
[18] NEWMAN M E,GIRVAN M.Finding and evaluating community structure in networks.[J].Physical Review E,2004,69(2):026113.
[19] DANON L,DIAZ-GUILERA A,DUCH J,et al.Comparing community structure identification[J].Journal of Statistical Mechanics:Theory and Experiment,2005,2005(9):P09008.
[20] ZACHARY W W.An information flow model for conflict and fission in small groups1[J].Journal of Anthropological Research,1977,33(4):452-473.
[2] SCHEFFER M.Complex systems:foreseeing tipping points[J].Nature,2010,467(7314):411-412.
[3] KARSAI M,KIVEL M,PAN R K,et al.Small but slow world:How network topology and burstiness slow down spreading[J].Physical Review E,2011,83(2):025102.
[4] 吴泓润,覃俊,易云飞,等.基于优化理论的社区无标度网络模型[J].计算机学报,2015,38(2):337-348.(WU H R,TAN J,YI Y F,et al.A model of community-structure and scale-free network based on optimization theory[J].Chinese Journal of Computers,2015,38(2):337-348.)
[5] 付立冬,马小科,聂靖靖.进化谱分算法检测动态网络社团结构[J].西安电子科技大学学报(自然科学版),2018,45(2):43-47(FU L D,MA X K,NIE J J.Evolutionary spectral approach to finding communities in dynamic networks [J].Journal of Xidian University (Natural Science),2018,45(2):43-47.)
[6] 刘冰玉,王翠荣,王聪,等.基于动态主题模型融合多维数据的微博社区发现算法[J].软件学报,2017,28(2):246-261.(LIU B Y,WANG C R,WANG C,et al.Microblog community discovery algorithm based on dynamic topic model with multidimensional data fusion[J].Journal of Software,2017,28(2):246-261.)
[7] 付立东,聂靖靖.基于进化谱分方法的动态社团检测[J].计算机科学,2018,45(2):171-174.(FU L D,NIE J J.Dynamic community detection based on evolutionary spectral method [J].Computer Science,2018,45(2):171-174.)
[8] ALBERT R,JEONG H,BARABASI A L.The diameter of the World Wide Web [J].Nature,1999,401(6):130-131.
[9] 顾亦然,陈雨晴.一种新的基于局部相似度的社区发现算法[J].南京邮电大学学报(自然科学版),2017,37(5):196-203.(GU Y R,CHEN Y Q.New community detection algorithm based on local similarity[J].Journal of Nanjing University of Posts and Telecommunications (Natural Science Edition),2017,37(5):196-203.)
[10] 梁宗文,杨帆,李建平.基于节点相似性度量的社团结构划分方法[J].计算机应用,2015,35(5):1213-1217.(LIANG Z W,YANG F,LI J P.Community structure detection based on node similarity in complex network[J].Journal of Computer Applications,2015,35(5):1213-1217.)
[11] 刘旭,易东云.基于局部相似性的复杂网络社区发现方法[J].自动化学报,2011,37(12):1520-1529.(LIU X,YI D Y.Complex network community detection by local similarity[J].Acta Automatica Sinica,2011,37(12):1520-1529.)
[12] CHEN Q,WU T T,FANG M.Detecting local community structures in complex networks based on local degree central nodes [J].Physica A:Statistical Mechanics and its Applications,2013,392(3):529-537.
[13] BLONDEL V D,GUILLAUME J L,LAMBIOTTE R,et al.Fast unfolding of communities in large networks[J].Journal of Statistical Mechanics:Theory and Experiment,2008(10):1-12.
[14] LAMBIOTTE R,DELVENNE J C,BARAHONA M.Laplacian dynamics and multiscale modular structure in networks[J].ArXiv Preprint,2008,2008:0812.1770.
[15] CLAUSET A,NEWMAN M E J,MOORE C.Finding community structure in very large networks[J].Physical Review E,2004,70(6):066111.
[16] NEWMAN M E J.Fast algorithm for detecting community structure in networks[J].Physical Review E,2004,69(6):066133.
[17] GIRVAN M,NEWMAN M E J.Community structure in social and biological networks[J].Proceedings of the National Academy of Sciences of Sciences of the United States of America,2002,99(12):7821-7826.
[18] NEWMAN M E,GIRVAN M.Finding and evaluating community structure in networks.[J].Physical Review E,2004,69(2):026113.
[19] DANON L,DIAZ-GUILERA A,DUCH J,et al.Comparing community structure identification[J].Journal of Statistical Mechanics:Theory and Experiment,2005,2005(9):P09008.
[20] ZACHARY W W.An information flow model for conflict and fission in small groups1[J].Journal of Anthropological Research,1977,33(4):452-473.