一种基于结构信息的改进CNM算法

doi:10.6040/j.issn.1672-3961.1.2016.180

山东大学学报(工学版) ›› 2017, Vol. 47 ›› Issue (1): 37-41.doi: 10.6040/j.issn.1672-3961.1.2016.180

一种基于结构信息的改进CNM算法

吕振^1,2,李苏雪^1,2,张传亭^1,2,袁东风^1,2*

1. 山东大学信息科学与工程学院, 山东济南 250100;2. 山东省中国虹计划协同创新中心, 山东济南 250100

收稿日期:2016-03-31 出版日期:2017-02-20 发布日期:2016-03-31
通讯作者: 袁东风(1958— ),男,四川安岳人,教授,博士,主要研究方向为5G关键技术,云计算与大数据. E-mail:dfyuan@sdu.edu.cn E-mail:zhenlv_2011@163.com
作者简介:吕振(1992— ),女,山东潍坊人,硕士研究生,主要研究方向为数据挖掘.E-mail:zhenlv_2011@163.com
基金资助:
山东省自主创新及成果转化重大专项基金资助项目(2014ZZCX03401)

An improved CNM algorithm based on network structure information

LYU Zhen^1,2, LI Suxue^1,2, ZHANG Chuanting^1,2, YUAN Dongfeng^1,2*

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

摘要/Abstract

摘要： CNM(clauset-newman-moore)算法能有效划分网络社区结构,但是对应划分出的社区准确度不高。对此,结合网络结构信息提出了一种改进CNM算法。通过对输入数据进行迭代删边预处理,精简网络结构,将原始网络分为两个子网络,然后将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.

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

中图分类号:

TP391

吕振,李苏雪,张传亭,袁东风. 一种基于结构信息的改进CNM算法[J]. 山东大学学报(工学版), 2017, 47(1): 37-41.

LYU Zhen, LI Suxue, ZHANG Chuanting, YUAN Dongfeng. An improved CNM algorithm based on network structure information[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2017, 47(1): 37-41.

参考文献

[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.

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed

一种基于结构信息的改进CNM算法

An improved CNM algorithm based on network structure information

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 2

多维度评价

本文评价

推荐阅读 0

[1]	王鑫,陆静雅,王英. 面向推荐的用户兴趣扩展方法[J]. 山东大学学报(工学版), 2017, 47(2): 71-79.
[2]	冯爱民1,刘学军1,陈斌2. 结构大间隔单类分类器[J]. 山东大学学报(工学版), 2010, 40(3): 6-12.