采用PageRank和节点聚类系数的标签传播重叠社区发现算法
|
摘要
基于标签传播的社区发现算法可以检测出复杂网络的重叠社区结构,因此提出了一种基于PageRank和节点聚类系数的重叠社区发现算法。该算法使用PageRank算法对节点的影响力进行排序,可以稳定社区发现结果,节点的聚类系数是一个与节点相关的值,使用节点聚类系数修改算法的参数并限制每个节点拥有最多标签的数量值,可以提高社区挖掘的质量。在人工网络和真实世界的网络上测试,实验验证了该算法能够有效地检测出重叠社区,并具有可接受的时间效率和算法复杂度。
Considering the fact that the community detection algorithm based on label propagation can detect overlapping community structures of complex networks, an overlapping community detection algorithm COPRAPC(community overlap propagation algorithm based on PageRank and clustering coefficient) was proposed. The algorithm used PageRank algorithm to rank the influence of nodes, which can stabilize the community finding results. The parameter of node clustering coefficient was a node-related parameter, which can be used to modify the parameters of the algorithm and limit the maximum number of labels each node, so as to improve the quality of community mining. Experiments on artificial networks and real-world networks show that the algorithm can effectively detect overlapping communities, and the algorithm has acceptable time efficiency and algorithm complexity.
Considering the fact that the community detection algorithm based on label propagation can detect overlapping community structures of complex networks, an overlapping community detection algorithm COPRAPC(community overlap propagation algorithm based on PageRank and clustering coefficient) was proposed. The algorithm used PageRank algorithm to rank the influence of nodes, which can stabilize the community finding results. The parameter of node clustering coefficient was a node-related parameter, which can be used to modify the parameters of the algorithm and limit the maximum number of labels each node, so as to improve the quality of community mining. Experiments on artificial networks and real-world networks show that the algorithm can effectively detect overlapping communities, and the algorithm has acceptable time efficiency and algorithm complexity.
引文
[1] 水超, 陈洪辉, 陈涛, 等. 力导向模型的复杂网络社区挖掘算法[J]. 国防科技大学学报, 2014, 36(4): 163-168.SHUI Chao, CHEN Honghui, CHEN Tao, et al. A community detect algorithm on force-directed model[J]. Journal of National University of Defense Technology, 2014, 36(4): 163-168. (in Chinese)
[2] Palla G, Derényi I, Farkas I, et al. Uncovering the overlapping community structures of complex networks in nature and society[J]. Nature, 2005, 435(7043): 814-818.
[3] Shen H W, Cheng X Q, Cai K, et al. Detect overlapping and hierarchical community structure in networks [J]. Physica A: Statistical Mechanics & Its Applications, 2009, 388(8): 1706-1712.
[4] Lancichinetti A, Fortunato S, Kertész J. Detecting the overlapping and hierarchical community structure of complex networks [J]. New Journal of Physics, 2008, 11(3): 19-44.
[5] 张兴义, 郑雯, 王从涛, 等. 基于单步添加团的重叠社团检测算法[J]. 华南理工大学学报 (自然科学版), 2016, 44(9): 24-31.ZHANG Xingyi, ZHENG Wen, WANG Congtao, et al. An overlapping community detection algorithm based on addtion of a clique at each step [J]. Journal of South China University of Technology (Natural Science Edition), 2016, 44(9): 24-31.(in Chinese)
[6] Ahn Y Y, Bagrow J P, Lehmann S. Link communities reveal multiscale complexity in networks [J]. Nature, 2010, 466(7307): 761-764.
[7] Jin D, Gabrys B, Dang J W. Combined node and link partitions method for finding overlapping communities in complex networks [J]. Scientific Reports, 2015, 5: 8600.
[8] Gregory S. Finding overlapping communities in networks by label propagation [J]. New Journal of Physics, 2010, 12(10): 103018.
[9] Wu Z H, Lin Y F, Gregory S, et al. Balanced multi-label propagation for overlapping community detection in social networks [J]. Journal of Computer Science and Technology, 2012, 27(3): 468-479.
[10] 张昌理, 王一蕾, 吴英杰, 等.基于信息熵和局部相关性的多标签传播重叠社区发现算法 [J].小型微型计算机系统, 2016, 37(8): 1645-1650.ZHANG Changli, WANG Yilei, WU Yingjie, et al. Muti-label propagation algorithm for overlapping community discovery based on information entropy and local correlation[J]. Journal of Chinese Computer System, 2016, 37(8): 1645-1650.(in Chinese)
[11] Cui Y Z, Wang X Y, Li J Q. Detecting overlapping communities in networks using the maximal sub-graph and the clustering coefficient [J]. Physica A: Statistical Mechanics & Its Applications, 2014, 405: 85-91.
[12] Mohan A, Kunnakadan S, Neelakantan B, et al. A scalable model for efficient information diffusion in large real world networks [C]//Proceedings of International Conference on Next Generation Intelligent Systems, Kottayam, 2017.
[13] 孙道平, 高原, 谢隽, 等. 一种用于中药方剂网络重叠社区发现的改进COPRA算法[J]. 南京大学学报(自然科学), 2013, 49(4): 483-490.SUN Daoping, GAO Yuan, XIE Jun, et al. An improved COPRA algorithm applied to traditional Chinese medicine formula network [J]. Journal of Nanjing University (Natural Sciences), 2013, 49(4): 483-490.(in Chinese)
[14] 陈羽中, 施松, 陈国龙, 等.基于节点层级与标签传播增益的重叠社区发现[J].模式识别与人工智能, 2015, 28(4): 289-298.CHEN Yuzhong, SHI Song, Chen Guolong, et al. Overlapping community discovery based on node hierarchy and label propagation gain[J]. Pattern Recognition & Artificial Intelligence, 2015, 28(4): 289-298.(in Chinese)
[15] Xie J R, Szymanski B K. Towards linear time overlapping community detection in social networks [C]//Proceedings of Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining, 2012: 25-36.
[16] Nicosia V, Mangioni G, Carchiolo V, et al. Extending the definition of modularity to directed graphs with overlapping communities [J]. Journal of Statistical Mechanics: Theory and Experiment, 2009(3): 03024.
[17] Naik A, Maeda H, Kanojia V, et al. Scalable twitter user clustering approach boosted by personalized PageRank[J]. Springer International Publishing AG, 2017: 472-485.
[18] Katzir L, Hardiman S J. Estimating clustering coefficients and size of social networks via random walk[C]//Proceedings of the 22nd International Conference on World Wide Web, 2013: 539-550.
[2] Palla G, Derényi I, Farkas I, et al. Uncovering the overlapping community structures of complex networks in nature and society[J]. Nature, 2005, 435(7043): 814-818.
[3] Shen H W, Cheng X Q, Cai K, et al. Detect overlapping and hierarchical community structure in networks [J]. Physica A: Statistical Mechanics & Its Applications, 2009, 388(8): 1706-1712.
[4] Lancichinetti A, Fortunato S, Kertész J. Detecting the overlapping and hierarchical community structure of complex networks [J]. New Journal of Physics, 2008, 11(3): 19-44.
[5] 张兴义, 郑雯, 王从涛, 等. 基于单步添加团的重叠社团检测算法[J]. 华南理工大学学报 (自然科学版), 2016, 44(9): 24-31.ZHANG Xingyi, ZHENG Wen, WANG Congtao, et al. An overlapping community detection algorithm based on addtion of a clique at each step [J]. Journal of South China University of Technology (Natural Science Edition), 2016, 44(9): 24-31.(in Chinese)
[6] Ahn Y Y, Bagrow J P, Lehmann S. Link communities reveal multiscale complexity in networks [J]. Nature, 2010, 466(7307): 761-764.
[7] Jin D, Gabrys B, Dang J W. Combined node and link partitions method for finding overlapping communities in complex networks [J]. Scientific Reports, 2015, 5: 8600.
[8] Gregory S. Finding overlapping communities in networks by label propagation [J]. New Journal of Physics, 2010, 12(10): 103018.
[9] Wu Z H, Lin Y F, Gregory S, et al. Balanced multi-label propagation for overlapping community detection in social networks [J]. Journal of Computer Science and Technology, 2012, 27(3): 468-479.
[10] 张昌理, 王一蕾, 吴英杰, 等.基于信息熵和局部相关性的多标签传播重叠社区发现算法 [J].小型微型计算机系统, 2016, 37(8): 1645-1650.ZHANG Changli, WANG Yilei, WU Yingjie, et al. Muti-label propagation algorithm for overlapping community discovery based on information entropy and local correlation[J]. Journal of Chinese Computer System, 2016, 37(8): 1645-1650.(in Chinese)
[11] Cui Y Z, Wang X Y, Li J Q. Detecting overlapping communities in networks using the maximal sub-graph and the clustering coefficient [J]. Physica A: Statistical Mechanics & Its Applications, 2014, 405: 85-91.
[12] Mohan A, Kunnakadan S, Neelakantan B, et al. A scalable model for efficient information diffusion in large real world networks [C]//Proceedings of International Conference on Next Generation Intelligent Systems, Kottayam, 2017.
[13] 孙道平, 高原, 谢隽, 等. 一种用于中药方剂网络重叠社区发现的改进COPRA算法[J]. 南京大学学报(自然科学), 2013, 49(4): 483-490.SUN Daoping, GAO Yuan, XIE Jun, et al. An improved COPRA algorithm applied to traditional Chinese medicine formula network [J]. Journal of Nanjing University (Natural Sciences), 2013, 49(4): 483-490.(in Chinese)
[14] 陈羽中, 施松, 陈国龙, 等.基于节点层级与标签传播增益的重叠社区发现[J].模式识别与人工智能, 2015, 28(4): 289-298.CHEN Yuzhong, SHI Song, Chen Guolong, et al. Overlapping community discovery based on node hierarchy and label propagation gain[J]. Pattern Recognition & Artificial Intelligence, 2015, 28(4): 289-298.(in Chinese)
[15] Xie J R, Szymanski B K. Towards linear time overlapping community detection in social networks [C]//Proceedings of Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining, 2012: 25-36.
[16] Nicosia V, Mangioni G, Carchiolo V, et al. Extending the definition of modularity to directed graphs with overlapping communities [J]. Journal of Statistical Mechanics: Theory and Experiment, 2009(3): 03024.
[17] Naik A, Maeda H, Kanojia V, et al. Scalable twitter user clustering approach boosted by personalized PageRank[J]. Springer International Publishing AG, 2017: 472-485.
[18] Katzir L, Hardiman S J. Estimating clustering coefficients and size of social networks via random walk[C]//Proceedings of the 22nd International Conference on World Wide Web, 2013: 539-550.