Improved Louvain method with strategy of separating isolated nodes

doi:10.11772/j.issn.1001-9081.2017.04.0970

Journal of Computer Applications ›› 2017, Vol. 37 ›› Issue (4): 970-974.DOI: 10.11772/j.issn.1001-9081.2017.04.0970

Previous Articles Next Articles

Improved Louvain method with strategy of separating isolated nodes

LI Lei, YAN Guanghui, YANG Shaowen, ZHANG Haitao

School of Electronic and Information Engineering, Lanzhou Jiaotong University, Lanzhou Gansu 730070, China

Received:2016-11-04 Revised:2016-12-05 Online:2017-04-10 Published:2017-04-19
Supported by:
This work is partially supported by National Natural Science Foundation of China (61163010), the Science Project of Lanzhou (2014-1-171), the Pre-research Fund of JinChuan Group Company Limited (JCYY2013012).

基于孤立节点分离策略的改进鲁汶算法

李雷, 闫光辉, 杨绍文, 张海韬

兰州交通大学电子与信息工程学院, 兰州 730070

通讯作者: 闫光辉
作者简介:李雷(1990-),男,甘肃天水人,硕士研究生,主要研究方向:数据挖掘、社区发现;闫光辉(1970-),男,河南商丘人,教授,博士,CCF会员,主要研究方向:数据挖掘、社交网络分析;杨绍文(1990-),男,陕西汉中人,硕士研究生,主要研究方向:社区发现;张海韬(1989-),男,甘肃白银人,硕士研究生,主要研究方向:社区发现。
基金资助:
国家自然科学基金资助项目（61163010）；兰州市科技计划项目（2014-1-171）；金川公司预研基金资助项目（JCYY2013012）。

Abstract

Abstract: Louvain Method (LM) is an algorithm to detect community in complex network based on modularity optimization. Since there is no method to calculate the gain of modularity after nodes leave their community in the existing research, a method was presented to calculate the modularity-gain after nodes leave their community based on the definition of modularity and the method for calculating the modularity-gain after nodes merge. Secondly, aiming at the problem that LM requires large memory space, an improved algorithm was proposed with the strategy of separating isolated nodes. In each iteration of the algorithm, isolated nodes of the input network were separated in advance, only the connected nodes of the input network can actually participate in the iterative process. Isolated nodes and non-isolated nodes were stored respectively when storing communities detected. The experimental results based on real networks showed that the requirement of memory space was reduced by more than 40% in the improved algorithm, and the running time of the algorithm was further reduced. Experimental results indicate that the improved algorithm has more advantages in dealing with real networks.

Key words: complex network, community detection, modularity, modularity optimization, Louvain Method (LM)

摘要： 鲁汶算法（LM）是基于模块度优化的复杂网络社区发现算法，有关模块度的现有研究中没有计算节点离开原属社区后模块度增益的方法。针对这一不足，基于模块度的定义和节点合并后模块度增益的计算方法，推导出了节点离开原属社区后模块度增益的计算方法，完善了该领域的理论研究。针对鲁汶算法对存储空间需求高的缺点，提出了基于孤立节点分离策略的改进鲁汶算法，该算法在每次迭代中将输入网络的孤立节点提前分离出去，只令其中的连通节点实际参与迭代过程，并在存储社区发现结果时将孤立节点和非孤立节点分开存储。基于真实网络的相关实验结果表明，采用孤立节点分离策略的改进方法，使算法对存储空间的需求减少了40%以上，并进一步缩短了算法的运行时间。因此，改进后的算法在处理真实网络时更具优势。

关键词: 复杂网络, 社区发现, 模块度, 模块度优化, 鲁汶算法

CLC Number:

TP301

LI Lei, YAN Guanghui, YANG Shaowen, ZHANG Haitao. Improved Louvain method with strategy of separating isolated nodes[J]. Journal of Computer Applications, 2017, 37(4): 970-974.

李雷, 闫光辉, 杨绍文, 张海韬. 基于孤立节点分离策略的改进鲁汶算法[J]. 计算机应用, 2017, 37(4): 970-974.

References

[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] NEWMAN M E, GIRVAN M. Finding and evaluating community structure in networks[J]. Physical Review E: Statistical, Nonlinear and Soft Matter Physics, 2004, 69(2 Pt 2):026113.
[3] BRANDES U, DELLING D, GAERTLER M, et al. On finding graph clusterings with maximum modularity[C]//Proceedings of the 33rd International Conference on Graph-Theoretic Concepts in Computer Science. Piscataway, NJ: IEEE, 2007:121-132.
[4] NEWMAN M E J. Fast algorithm for detecting community structure in networks[J]. Physical Review E: Statistical, Nonlinear and Soft Matter Physics, 2004, 69(6 Pt 2):066133.
[5] CLAUSET A, NEWMAN M E J, MOORE C. Finding community structure in very large networks[J]. Physical Review E: Statistical, Nonlinear and Soft Matter Physics, 2004, 70(6 Pt 2):066111.
[6] DUCH J, ARENAS A. Community detection in complex networks using extremal optimization[J]. Physical Review E: Statistical, Nonlinear and Soft Matter Physics, 2005, 72(2 Pt 2):027104.
[7] LV Z, HUANG W. Iterated tabu search for identifying community structure in complex networks[J]. Physical Review E: Statistical, Nonlinear and Soft Matter Physics, 2009, 80(2 Pt 2):026130.
[8] BLONDEL V D, GUILLAUME J L, LAMBIOTTE R, et al. Fast unfolding of communities in large networks[J]. Journal of Statistical Mechanics Theory & Experiment, 2008, 2008(10):155-168.
[9] LIU X, MURATA T. Advanced modularity-specialized label propagation algorithm for detecting communities in networks[J]. Physica A: Statistical Mechanics & Its Applications, 2009, 389(7):1493-1500.
[10] GACH O, HAO J K. A memetic algorithm for community detection in complex networks[C]//PPSN 2012: Proceedings of the 12th International Conference on Parallel Problem Solving from Nature. Berlin: Springer, 2012:327-336.
[11] LANCICHINETTI A, FORTUNATO S. Community detection algorithms: a comparative analysis[J]. Physical Review E: Statistical, Nonlinear and Soft Matter Physics, 2009, 80:056117.
[12] DE MEO P, FERRARA E, FIUMARA G, et al. Generalized Louvain method for community detection in large networks[EB/OL].[2016-03-10]. https://arxiv.org/pdf/1108.1502v2.pdf.
[13] GACH O, HAO J K. Improving the louvain algorithm for community detection with modularity maximization[C]//Proceedings of the 11th International Conference on Artificial Evolution, LNCS 8752. Berlin: Springer, 2013:145-156.
[14] BHOWMICK S, SRINIVASAN S. A template for parallelizing the louvain method for modularity maximization[M]//MUKHERJEE A, CHOUDHURY M, PERUANI F, et al. Dynamics on and of Complex Networks. Berlin: Springer, 2013, 2:111-124.
[15] 刘瑶, 康晓慧, 高红, 等. 基于节点亲密度和度的社会网络社团发现方法[J]. 计算机研究与发展, 2015, 52(10):2363-2372.(LIU Y, KANG X H, GAO H, et al. A community detecting method based on the node intimacy and degree in social network[J]. Journal of Computer Research and Development, 2015, 52(10):2363-2372.)
[16] FORTUNATO S, BARTHÉLEMY M. Resolution limit in community detection[J]. Proceedings of the National Academy of Sciences of the United States of America, 2007, 104(1):36-41.
[17] KLIMT B, YANG Y. Introducing the Enron corpus[EB/OL].[2016-03-10]. https://bklimt.com/papers/2004_klimt_ceas.pdf.
[18] YANG J, LESKOVEC J. Defining and evaluating network communities based on ground-truth[J]. Knowledge & Information Systems, 2012, 42(1):745-754.
[19] 王莉, 程学旗. 在线社会网络的动态社区发现及演化[J]. 计算机学报, 2015, 38(2):219-237.(WANG L, CHENG X Q. Dynamic community in online social network[J]. Chinese Journal of Computers, 2015, 38(2):219-237.)

Improved Louvain method with strategy of separating isolated nodes

基于孤立节点分离策略的改进鲁汶算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

[1]	CAI Biao, LI Ruicen, WU Yuanyuan. Impact and enhancement of similarity features on link prediction [J]. Journal of Computer Applications, 2021, 41(9): 2569-2577.
[2]	LI Yafang, LIANG Ye, FENG Weiwei, ZU Baokai, KANG Yujian. Deep network embedding method based on community optimization [J]. Journal of Computer Applications, 2021, 41(7): 1956-1963.
[3]	LI Ping, WANG Fen, CHEN Qidong, SUN Jun. Discrete random drift particle swarm optimization algorithm for solving multi-objective community detection problem [J]. Journal of Computer Applications, 2021, 41(3): 803-811.
[4]	Jicheng CHEN, Hongchang CHEN. Community detection method based on tensor modeling and evolutionary K-means clustering [J]. Journal of Computer Applications, 2021, 41(11): 3120-3126.
[5]	SHENG Jun, LI Bin, CHEN Ling. Recommendation algorithm based on modularity and label propagation [J]. Journal of Computer Applications, 2020, 40(9): 2606-2612.
[6]	LI Chunying, TANG Yong, XIAO Zhenghong, LI Tiansong. Influential scholar recommendation model in academic social network [J]. Journal of Computer Applications, 2020, 40(9): 2594-2599.
[7]	LUO Xiangyu, LI Jianan, LUO Xiaoxia, WANG Jia. Improved community evolution relationship analysis method for dynamic graphs [J]. Journal of Computer Applications, 2020, 40(8): 2313-2318.
[8]	ZHENG Wenping, YUE Xiangdou, YANG Gui. Improved label propagation algorithm based on random walk [J]. Journal of Computer Applications, 2020, 40(12): 3423-3429.
[9]	CHENG Qiwei, CHEN Qimai, HE Chaobo, LIU Hai. Overlapping community detection method based on improved symmetric binary nonnegative matrix factorization [J]. Journal of Computer Applications, 2020, 40(11): 3203-3210.
[10]	LI Shasha, LIANG Dongyang, YU Jie, JI Bin, MA Jun, TAN Yusong, WU Qingbo. Research team mining algorithm based on teacher-student relationship [J]. Journal of Computer Applications, 2020, 40(11): 3198-3202.
[11]	LIU Yuyang, LI Longjie, SHAN Na, CHEN Xiaoyun. Link prediction method fusing clustering coefficients [J]. Journal of Computer Applications, 2020, 40(1): 28-35.
[12]	YUAN Peiyan, CAI Yunyun. Content offloading scheme of greedy strategy in mobile edge computing system [J]. Journal of Computer Applications, 2019, 39(9): 2664-2668.
[13]	FU Lidong, HAO Wei, LI Dan, LI Fan. Community dividing algorithm based on similarity of common neighbor nodes [J]. Journal of Computer Applications, 2019, 39(7): 2024-2029.
[14]	WANG Xilong, WANG Jicheng, LUO Cheng, TIAN Xiuxia. Evolutionary game model under synergistic effect of time scale and selection preference [J]. Journal of Computer Applications, 2019, 39(6): 1824-1828.
[15]	ZHANG Xi, ZHU Li, LIU Luhui, ZHAN Hanglong, LU Yanmin. Intelligent risk contagion mechanism of interbank market credit lending based on multi-layer network [J]. Journal of Computer Applications, 2019, 39(5): 1507-1511.