|
|
- 2017
一种基于结构信息的改进CNM算法
|
Abstract:
摘要： CNM(clauset-newman-moore)算法能有效划分网络社区结构,但是对应划分出的社区准确度不高。对此,结合网络结构信息提出了一种改进CNM算法。通过对输入数据进行迭代删边预处理,精简网络结构,将原始网络分为两个子网络,然后将CNM算法应用到子网络,完成社区发现。在五个不同规模数据集上的试验结果表明,改进CNM方法提高了社区发现的质量和精度,社区模块度在小规模的数据集上得到了显著提升。
Abstract: Although community detection could be effectively accomplished by CNM(clauset-newman-moore)algorithm, the accuracy of the results was unsatisfactory. Consequently, an improved CNM algorithm based on network structure information was proposed, which divided the original network into two parts by removing the edge whose edge betweenness was maximum of all iteratively. These two parts as the input data of CNM algorithm were used to detect communities. The experimental results on five different size of datasets showed that the improved CNM algorithm elevated the quality of community detection, and modularity of these communities peformed well especially in small datasets
| [1] | 胡健, 董跃华, 杨炳儒. 大型复杂网络中的社区结构发现算法[J]. 计算机工程, 2008, 34(19): 92-93. HU Jian, DONG Yuehua, YANG Bingru. Community structure discovery algorithm in large and complex network[J]. Computer Engineering, 2008, 34(19): 92-93. |
| [2] | 解邹, 汪小帆. 复杂网络中的社团结构分析算法研究综述[J]. 复杂系统与复杂性科学, 2005, 2(3): 1-12. XIE Zhou, WANG Xiaofan. An overview of algorithms for analyzing community structure in complex networks[J]. Complex Systems and Complexity Science, 2005, 2(3):1-12. |
| [3] | 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. |
| [4] | HALLAC D, LESKOVEC J, BOYD S. Network lasso: clustering and optimization in large graphs[C] //Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Sedney, Australia: ACM, 2015: 387-396. |
| [5] | KARRER B, NEWMAN M E J. Stochastic block models and community structure in networks[J]. Physical Review E, 2011, 83(1):211-222. |
| [6] | ENRIGHT A J, DONGEN S V, OUZOUNIS C A, et al. Towards real-time community detection in large networks[J]. Physical Review E, 2009, 79(6): 066107. |
| [7] | 骆志刚, 丁凡, 蒋晓舟, 等. 复杂网络社团发现算法研究新进展[J]. 国防科技大学学报, 2011, 33(1): 47-52. LUO Zhigang, DING Fan, JIANG Xiaozhou, et al. New progress on community detection in complex networks[J]. Journal of National University of Defense Technology, 2011, 33(1): 47-52. |
| [8] | 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. |
| [9] | CLAUSET A, NEWMAN M E J, MOORE C. Finding community structure in very large networks[J]. Physical Review E, 2004, 70(6): 066111. |
| [10] | XU Z, KE Y, WANG Y, et al. A model-based approach to attributed graph clustering[C] //Proceedings of the 2012 ACM Sigmod International Conference on Management of Data. Arizona, USA: ACM, 2012: 505-516. |
| [11] | NEWMAN M E J. The structure and function of complex networks[J]. SIAM Review, 2003, 45(2): 167-256. |
| [12] | 李晓佳.复杂网络中的社团结构[D].北京:北京师范大学, 2009. LI Xiaojia. Community structure in complex networks[D]. Beijing: Beijing Normal University, 2009. |
| [13] | 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 Pt 2): 036106. |
| [14] | NEWMAN M E J. Fast algorithm for detecting community structure in networks[J]. Physical Review E, 2004, 69(6): 066133. |
| [15] | NEWMAN M E J. Modularity and community structure in networks[J]. Proceedings of the National Academy of Sciences, 2006, 103(23): 8577-8582. |
| [16] | KIM M, LESKOVEC J. Latent multi-group membership graph model[J]. Computer Science, 2012:80. |
| [17] | 刘大有, 金弟, 何东晓,等. 复杂网络社区挖掘综述[J]. 计算机研究与发展, 2013, 50(10): 2140-2154. LIU Dayou, JIN Di, HE Dongxiao, et al. Community mining in complex networks[J]. Journal of Computer Research and Development, 2013, 50(10): 2140-2154. |
| [18] | DUCH J, ARENAS A. Community detection in complex networks using extremal optimization[J]. Physical Review E, 2005, 72(2): 027104. |
| [19] | AGARWAL G, KEMPE D. Modularity-maximizing graph communities via mathematical programming[J]. The European Physical Journal B, 2008, 66(3): 409-418. |
| [20] | NEWMAN M E J, GIRVAN M. Finding and evaluating community structure in networks[J]. Physical Review E, 2004, 69(2): 026113. |
| [21] | CORMEN T H, LEISERSON C E, RIVEST R L, et al. Introduction to algorithms[M]. Cambridge, USA:MIT Press, 2009. |
| [22] | WATTS D J, STROGATZ S H. Collective dynamics of‘small-world’ networks[J]. Nature, 1998, 393(6684): 440-442. |
| [23] | 赵丽娜,李慧.不可重叠社区发现算法的评价指标分析[J]. 计算机科学,2014,41(10):378-381. ZHAO Lina, LI Hui. Evaluation indicators analysis of nonoverlap community detection algorithm[J]. Computer Science, 2014, 41(10):378-381. |
