《计算机应用研究》|Application Research of Computers

一种优化标签传播过程的重叠社区发现算法

Overlapping communities detection during process of improvement of label propagation

免费全文下载 (已被下载 次)  
获取PDF全文
作者 赵雨露,张曦煌
机构 江南大学 物联网工程学院,江苏 无锡 214122
统计 摘要被查看 次,已被下载
文章编号 1001-3695(2018)03-0765-04
DOI 10.3969/j.issn.1001-3695.2018.03.026
摘要 随着社区规模的不断扩大,基于标签传播思想的重叠社区发现算法得到较大发展。经典重叠社区发现算法虽然很好地利用了标签随机传播特性实现了重叠社区发现,但是也导致该算法输出结果很不稳定、社区生成质量较差。为克服采用最新的ClusterRank为所有节点排序降低随机性带来的结果稳定性差的弊端,引入最大社区节点数以控制最大社区节点数目,防止远大于其他社区的Monster出现。采用真实数据集和人工网络验证,结果证实,改良后算法可行有效。
关键词 重叠社区;标签传播;ClusterRank;节点重要性
基金项目 江苏省产学研合作项目(BY2015019-30)
本文URL http://www.arocmag.com/article/01-2018-03-026.html
英文标题 Overlapping communities detection during process of improvement of label propagation
作者英文名 Zhao Yulu, Zhang Xihuang
机构英文名 SchoolofInternetofThingsEngineering,JiangnanUniversity,WuxiJiangsu214122,China
英文摘要 With the expansion of community size, overlapping community detection algorithm based on label propagation gains a promising expectation. Classic overlapping community finding algorithm makes good use of label random propagation characteristics in order to achieve overlap community discovery. However, it results in unstable output of algorithm and poor community production quality. This paper used the latest ClusterRank to sort all nodes reduces the disadvantages of random results of stability; introduced node number of the largest community to control the maximum number of community node to prevent those which were much larger than the Monster appearing in other communities. The real-world data sets and artificial network authentication confirm that the improved algorithm is feasible and effective.
英文关键词 overlapping communities; label propagation; ClusterRank; node importance
参考文献 查看稿件参考文献
  [1] Girvan M, Newman M E J. Community structure in social and biological networks[J] . Proceedings of the National Academy of Sciences of the United States of America, 2002, 99(12):7821-7826.
[2] Raghavan U N, Albert R, Kumara S. Near linear time algorithm to detect community structures in large-scale networks[J] . Physical Review E Statistical Nonlinear & Soft Matter Physics, 2007, 76(3 Pt 2):036106.
[3] Zhu Xiaojin, Ghahramani Z. Learning from labeled and unlabeled data with label propagation, TR CMU-CALD-02-107[R] . [S. l. ] :Carnegie Mellon University, 2002.
[4] Cordasco G, Gargano L. Community detection via semi-synchronous label propagation algorithms[C] //Proc of IEEE International Workshop on Business Applications of Social Network Analysis. 2010:1-8.
[5] Sun Heli, Huang Jianbin, Zhong Xiang, et al. Label propagation with α-degree neighborhood impact for network community detection[J] . Computational Intelligence & Neuroscience, 2014, 2014:130689.
[6] Zhao Yuxin, Li Shenghong, Chen Xiuzhen. Community detection using label propagation in entropic order[C] //Proc of IEEE International Conference on Computer and Information Technology. 2012:18-24.
[7] Gregory S. Finding overlapping communities in networks by label propagation[J] . New Journal of Physics, 2009, 12(10):2011-2024.
[8] Xie Jierui, Kelley S, Szymanski B K. Overlapping community detection in networks:the state-of-the-art and comparative study[J] . ACM Computing Surveys, 2012, 45(4):115-123.
[9] 商源纯. 复杂网络中的重叠社区发现算法研究[D] . 北京:北京交通大学, 2011.
[10] Wu Zhihao, Lin Youfang, 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.
[11] 刘世超, 朱福喜, 甘琳. 基于标签传播概率的重叠社区发现算法[J] . 计算机学报, 2016, 39(4):717-729.
[12] Gaiteri C, Chen Mingming, Szymanski B, et al. Identifying robust communities and multi-community nodes by combining top-down and bottom-up approaches to clustering[J] . Scientific Reports, 2015, 5:16361.
[13] Leung I X L, Hui Pan, Liò P, et al. Towards real-time community detection in large networks[J] . Physical Review E Statistical Nonlinear & Soft Matter Physics, 2008, 79(6):853-857.
[14] Chen Duanbing, Gao Hui, Lyu L, et al. Identifying influential nodes in large-scale directed networks:the role of clustering[J] . PLOS One, 2013, 8(10):e77455.
[15] Lyu Linyuan, Chen Duanbing, Ren Xiaolong, et al. Vital nodes identification in complex networks[J] . Physics Reports, 2016, 650:1-63.
[16] Zachary W W. An information flow model for conflict and fission in small groups1[J] . Journal Anthropological Research, 1977, 33(4):452-473.
[17] Lancichinetti A, Fortunato S, Radicchi F. Benchmark graphs for testing community detection algorithms[J] . Physical Review E Statistical Nonlinear & Soft Matter Physics, 2008, 78(2):561-570.
[18] Lancichinetti A, Fortunato S, Kertész J. Detecting the overlapping and hierarchical community structure of complex networks[J] . New Journal of Physics, 2009, 11(3):19-44.
[19] Newman M E, Girvan M. Finding and evaluating community structure in networks[J] . Physical Review E Statistical Nonlinear & Soft Matter Physics, 2004, 69(2 Pt 2):026113.
[20] 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 & Experiment, 2009, 2009(3):3166-3168.
[21] Li Qian, Zhou Tao, Lyu Linyan, et al. Identifying influential sprea-ders by weighted LeaderRank[J] . Physica A Statistical Mechanics & Its Applications, 2013, 404(24):47-55.
[22] Burt R S, Minor M J. Applied network analysis:a methodological introduction[J] . Canadian Journal of Sociology, 1983, 63(3):195-222.
[23] Jin Di, Yang Bo, Baquero C, et al. Markov random walk under constraint for discovering overlapping communities in complex networks[J] . Journal of Statistical Mechanics Theory & Experiment, 2013, 2011(5):P05031.
收稿日期 2016/10/31
修回日期 2016/12/8
页码 765-768
中图分类号 TP301.6
文献标志码 A