JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE) ›› 2017, Vol. 47 ›› Issue (1): 37-41.doi: 10.6040/j.issn.1672-3961.1.2016.180

Previous Articles     Next Articles

An improved CNM algorithm based on network structure information

LYU Zhen1,2, LI Suxue1,2, ZHANG Chuanting1,2, YUAN Dongfeng1,2*   

  1. 1. School of Information Science and Engineering, Shandong University, Jinan 250100, Shandong, China;
    2. Collaborative Innovation Center of China Rainbow Project, Jinan 250100, Shandong, China
  • Received:2016-03-31 Online:2017-02-20 Published:2016-03-31

PDF (PC)

708

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.

Key words: community detection, improved CNM algorithm, structure information, edge betweenness, modularity

CLC Number: 

  • TP391
[1] KIM M, LESKOVEC J. Latent multi-group membership graph model[J]. Computer Science, 2012:80.
[2] KARRER B, NEWMAN M E J. Stochastic block models and community structure in networks[J]. Physical Review E, 2011, 83(1):211-222.
[3] 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.
[4] NEWMAN M E J. The structure and function of complex networks[J]. SIAM Review, 2003, 45(2): 167-256.
[5] 胡健, 董跃华, 杨炳儒. 大型复杂网络中的社区结构发现算法[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.
[6] 刘大有, 金弟, 何东晓,等. 复杂网络社区挖掘综述[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.
[7] 解邹, 汪小帆. 复杂网络中的社团结构分析算法研究综述[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.
[8] 李晓佳.复杂网络中的社团结构[D].北京:北京师范大学, 2009. LI Xiaojia. Community structure in complex networks[D]. Beijing: Beijing Normal University, 2009.
[9] 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.
[10] 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.
[11] 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.
[12] 骆志刚, 丁凡, 蒋晓舟, 等. 复杂网络社团发现算法研究新进展[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.
[13] NEWMAN M E J. Fast algorithm for detecting community structure in networks[J]. Physical Review E, 2004, 69(6): 066133.
[14] 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.
[15] DUCH J, ARENAS A. Community detection in complex networks using extremal optimization[J]. Physical Review E, 2005, 72(2): 027104.
[16] AGARWAL G, KEMPE D. Modularity-maximizing graph communities via mathematical programming[J]. The European Physical Journal B, 2008, 66(3): 409-418.
[17] NEWMAN M E J, GIRVAN M. Finding and evaluating community structure in networks[J]. Physical Review E, 2004, 69(2): 026113.
[18] CLAUSET A, NEWMAN M E J, MOORE C. Finding community structure in very large networks[J]. Physical Review E, 2004, 70(6): 066111.
[19] CORMEN T H, LEISERSON C E, RIVEST R L, et al. Introduction to algorithms[M]. Cambridge, USA:MIT Press, 2009.
[20] WATTS D J, STROGATZ S H. Collective dynamics of‘small-world’ networks[J]. Nature, 1998, 393(6684): 440-442.
[21] 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.
[22] NEWMAN M E J. Modularity and community structure in networks[J]. Proceedings of the National Academy of Sciences, 2006, 103(23): 8577-8582.
[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.
[1] FENG Ai-min1, LIU Xue-jun1, CHEN Bin2. Structure large margin one-class classifier [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2010, 40(3): 6-12.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
Copyright 2018 © Editorial office of Journal of Shandong University (Engineering Science)
Supported by Beijing Magtech Co.Ltd