Research Progress of Fuzzy Overlapping Community Detection in Complex Networks
XIAO Jing1, ZHANG Yongjian1, XU Xiaoke1,2
1.College of Information and Communication Engineering, Dalian Minzu University, Dalian 116600, China; 2.Guizhou Provincial Key Laboratory of Public Big Data, Guizhou University, Guiyang 550025, China
Abstract：Through expanding value space, fuzzy overlapping detection redefines the fuzzy membership degree, which can not only improve the detection accuracy of the complicated community structures, but also explore the overlapping features of nodes and communities. In this paper, we firstly give the explanation of the difference between crisp and fuzzy overlapping detection, and then summarize their related researches. To clearly state the fuzzy overlapping detection, we introduce the available work by dividing them into five classes on the acquisition method of fuzzy membership degree, including expanded label propagation, nonnegative matrix factorization, edge nodes based two-phase detection, fuzzy clustering and fuzzy modularity optimization. The advances and challenges of the fuzzy modularity optimization based on evolutionary algorithms are discussed in detail. At last some future research topics are given
[1]Su J H, Havens T C. Quadratic program-based modularity maximization for fuzzy community detection in social networks [J]. IEEE Transactions on Fuzzy Systems, 2015, 23(5):13561371. [2]Su J H, Havens T C. Community detection in social networks using a genetic algorithm [C]. Proc of IEEE International Conference on Fuzzy Systems (FUZZ-IEEE). Beijing, China, 2014: 20392046. [3]Havens T C, Bezdek J C, Leckie C. A soft modularity function for detecting fuzzy communities in social networks [J]. IEEE Transactions on Fuzzy Systems, 2013, 21(6):11701175. [4]Xie J R, Kelley S, Szymanski B K. Overlapping community detection in networks: the state of the art and comparative study [J]. ACM Computing Surveys, 2013, 45(4):137. [5]Golsefid S M M, Zarand M H F, Bastani S S. Fuzzy community detection model in social networks [J]. International Journal of Intelligent Systems, 2015, 30:12271244. [6]Gregory S. Fuzzy overlapping communities in networks [J]. Journal of Statistical Mechanics-Theory and Experiment, 2011, 2: P02017. [7]Kundu S, Pal S K. Fuzzy-rough community in social networks [J]. Pattern Recognition Letters, 2015, 67,145152. [8]Bennett L, Kittas A, Liu S S. Community structure detection for overlapping modules through mathematical programming in protein interaction networks [J]. Plos One, 2014, 9(11):e112821e112821. [9]刘世超,朱福喜,甘琳. 基于标签传播概率的重叠社区发现算法[J].计算机学报, 2015, 38(47):117. Liu Shichao, Zhu Fuxi, Gan Lin. A label-propagation-Probability-based algorithm for overlapping community detection [J]. Chinese Journal of Computers, 2015, 38(47):117. [10] Nicosia V, Mangioni G, Malgeri M. Extending the definition of modularity to directed graphs with overlapping communities [J]. Journal of Statistical Mechanics-Theory and Experiment, 2009(3):31663168. [11] Psorakis I, Roberts S, Ebden M, et al. Overlapping community detection using Bayesian non-negative matrix factorization [J]. Physical Review E, 2011, 83(6 Pt 2):15091520. [12] Zhao K, Zhang S W, Pan Q. Fuzzy analysis for overlapping community structure of complex network [C]. Proc CCDC, 2010: 39763981. [13] Palla G, Derényi I, Farkas I. Uncovering the overlapping community structure of complex networks in nature and society [J]. Nature, 2005, 435(7043): 814818. [14] Farkas I, Abel D, Palla G, et al. Weighted network modules [J]. New J Phys, 2007, 9(6):180198. [15] Palla G, Dernyi I, Farkas I, et al. Uncovering the overlapping community structure of complex networks in nature and society [J]. Nature, 2005, 435: 814818. [16] Kumpula J M, Kivela M, Kaski K, et al. Sequential algorithm for fast clique percolation [J]. Phys Rev E 2008, 78(2):18151824. [17] Ahn Y Y, Bagrow J P, Lehmann S. Link communities reveal multiscale complexity in networks [J]. Nature, 2010, 466(7307): 761764. [18] Kim Y, Jeong H. Map equation for link communities [J]. Physical Review E, 2011, 84(2):14021409. [19] 朱牧,孟凡荣,周勇. 基于链接密度聚类的重叠社区发现算法[J]. 计算机研究与发展,2013,50(12):25202530. Zhu Mu, Meng Fanrong, Zhou Yang. Density-based link clustering algorithm for overlapping community detection [J]. Journal of Computer Research and Development, 2013,50(12):25202530. [20] Wu Z, Lin Y. Wan H, et al. A fast and reasonable method for community detection with adjustable extent of overlapping [C]. Proc of International Conference on Intelligent Systems & Knowledge Engineering. 2010:376379. [21] Fortunato S. Community detection in graphs [J]. Phys Rep, 2010, 486(35):75174. [22] Lancichinetti A, Fortunato S, Kertesz J. Detecting the overlapping and hierarchical community structure of complex networks [J]. New Journal of Physics, 2008, 11(3):1944. [23] Lee C, Reid F, McDaid A. Detecting highly overlapping community structure by greedy clique expansion [C]. Proceedings of the 4th International Workshop on Social Network Mining and Analysis. ACM, Washington DC, USA, 2010, 3342. [24] Coscia M, Rossetti G, Giannotti F, et al. DEMON: a local first discovery method for overlapping communities [C]. proc of the 18th ACM SIGKDD Int Conf on Knowledge Discovery and Data Ming. New York: ACM, 2012:615623. [25] Lancichinetti A, Radicchi F, Ramasco J J, et al. Finding statistically significant communities in networks [J]. Plos One, 2010, 6(4):336338. [26] Jin D, Yang B, Baquero C, et al. A markov random walk under constraint for discovering overlapping communities in complex networks [J]. Journal of Statistical Mechanics: Theory and Experiment, 2011,2011(5):50. [27] 陈俊宇,周刚,南煜,等.一种半监督的局部扩展式重叠社区发现方法[J].计算机研究与发展,2016,53(6): 13761388. Chen Junyu, Zhou Gang, Nan Yu, et al. Semi-supervised local expansion method for overlapping community detection [J]. Journal of Computer Research and Development, 2016,53(6): 13761388. [28] Blondel V D, Guillaume J L, Lambiotte R. Fast unfolding of communities in large networks [J]. Journal of Statistical Mechanics Theory & Experiment, 2015, 30(2):155168. [29] Shen H W, Cheng X Q, Guo J F. Quantifying and identifying the overlapping community structure in networks [J]. Journal of Statistical Mechanics Theory & Experiment, 2009, 2009(7):07042. [30] Wang X, Li L, Cheng Y. An overlapping module identification method in protein-protein interaction networks [J]. BMC Bioinformatics, 2012, 13 (Suppl):343347. [31] Franca F O D, Coelho G P. Identifying overlapping communities in complex networks with multimodal optimization [J]. IEEE Congress on Evolutionary Computation, Cancún, México, 2013: 269276. [32] 张英杰,龚中汉, 陈乾坤. 基于免疫离散差分进化算法的复杂网络社区发现[J].自动化学报, 2015,41(4):749757. Zhang Yingjie, Gong Zhonghan, Chen Qiankun. Community detection in complex networks using immune differential evolution algorithm [J]. Acta Automatica Sinica, 2015, 41(4):749757. [33] 金弟, 刘杰, 杨博, 等. 局部搜索与遗传算法结合的大规模复杂网络社区探测[J]. 自动化学报, 2011, 37(7): 873882. Jin Di, Liu Jie, Yang Bo, et al. Genetic algorithm with local search for community detection in large-scale complex networks [J]. Acta Automatica Sinica, 2011, 37(7): 873882. [34] 金弟, 杨博, 刘杰, 等. 复杂网络簇结构探测——基于随机游走的蚁群算法[J]. 软件学报, 2012, 23(3): 451464. Jin Di, Yang Bo, Liu Jie, et al. An colony optimization based on random walk for community detection in complex networks [J]. Journal of Software, 2012, 23(3): 451464. [35] Zhou X, Liu Y H, Zhang J D. An ant colony based algorithm for overlapping community detection in complex networks [J]. Physica A, 2015,427:289301. [36] 黄发良,肖南峰. 基于线图与 PSO 的网络重叠社区发现[J]. 自动化学报, 2011,37(9):11401144. Huang Faliang, Xiao Nanfeng. Discovering overlapping communities based on line graph and PSO [J]. Acta Automatica Sinica, 2011,37(9):11401144. [37] Pizzuti C. A multi-objective genetic algorithm for community detection in networks [C]. Proceedings of the 21st IEEE International Conference on Tools with Artificial Intelligence, 2009, 379386. [38] 刘辰龙.基于进化算法的社区检测及其在个性化推荐的应用[D].西安:西安电子科技大学,2014. Liu Chenlong. Evolutionary community detection algorithms and their applications in personalized recommendation [D]. Xi'an: Xidian University, 2014. [39] Wu Z H, Lin Y F, 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):468479. [40] Qiang H, Yan G. A method of personalized recommendation based on multi-label propagation for overlapping community detection [J]. System science, engineering design and manufacturing informatization (ICSEM), 2012 3rd International Conference on IEEE, 2012, 1: 360364. [41] Gregory S. Finding overlapping communities in networks by label propagation [J]. New Journal of Physics, 2009, 12(10):20112024. [42] Xie J, Szymanski B K. Towards linear time overlapping community detection in social networks [C]. Proc PAKDD Conf, 2012, 2536. [43] Zhao K, Zhang SW, Pan Q. Fuzzy analysis for overlapping community structure of complex network [C]. Proc CCDC, 2010, 39763981. [44] Psorakis I, Roberts S, Ebden M, et al. Overlapping community detection using Bayesian non-negative matrix factorization [J]. Physical Review E, 2011, 83(6 Pt 2):15091520. [45] 李玉翔, 李弼程, 郭志刚. 基于非负矩阵分解的网络重叠社区发现研究[J]. 系统仿真学报,2014,26(3):643649. Li Yuxiang, Li Bicheng, Guo Zhigang. Research on overlapping community detection in networks using non-negative matrix factorization [J]. Journal of System Simulation, 2014, 26(3):643649. [46] Zhang S H, Wang R S, Zhang X S. Uncovering fuzzy community structure in complex networks [J]. Physical Review E (S15502376), 2007, 76(4): 046103.1046103.7. [47] 刘勇.复杂网络的非重叠与重叠社区检测方法[D].西安:西安电子科技大学,2014. Liu Yong. Method for non-overlapping and overlapping communities detection in complex networks [D]. Xi'an: Xidian University, 2014. [48] 陈俊宇,周 刚,熊小兵. 一种采用邻居投票机制的重叠社区发现方法[J]. 小型微型计算机系统, 2014, 35(10):22722277. Chen Junyu, Zhou Gang, Xiong Xiaobing. Detection overlapping community structure with neighbor voting [J]. Journal of Chinese Computer Systems, 2014, 35(10): 22722277. [49] Bennett L, Kittas A, Liu S S. Community structure detection for overlapping modules through mathematical programming in protein interaction networks [J]. Plos One, 2014, 9(11):e112821e112821. [50] Liu J. Detecting the fuzzy clusters of complex networks [J]. Pattern Recognit, 2010, 43:13341345. [51] Wang W J, Liu D, Liu X, et al. Fuzzy overlapping community detection based on local random walk and multidimensional scaling [J]. Phys A, 2013, 392(24): 65786586. [52] 李刘强,桂小林,安健,等. 采用模糊层次聚类的社会网络重叠社区检测算法[J].西安交通大学学报, 2015,49(2):713. Li Liuqiang, Gui Xiaolin, An Jian, et al. Overlapping community detection algorithm based on fuzzy hierarchical clustering in social network [J]. Journal of Xi'an Jiaotong University, 2015,49(2):713. [53] Suman K D, Sankar K P. Fuzzy-rough community in social networks [J]. Pattern Recognition Letters, 2015, 67,145152. [54] Nepusz T, Petroczi A, Negyessy L, et al. Fuzzy communities and the concept of bridgeness in complex networks [J]. Phys Rev E, 2008, 77(1):119136. [55] Zhang S, Wang R, Zhang X. Identification of overlapping community structure in complex networks using fuzzy c-means clustering [J]. Physica A Statistical Mechanics & Its Applications, 2007, 374(1):483490. [56] Liu J. Fuzzy modularity and fuzzy community structure in networks [J]. Physics of Condensed Matter, 2010, 77(4): 547557. [57] Zhan W H, Guan J H, Chen H H, et al. Identifying overlapping communities in networks using evolutionary method [J]. Physica A, 2016,442:182192. [58] 刘瑶,康晓慧,高红,等. 基于节点亲密度和度的社会网络社团发现方法[J]. 计算机研究与发展,2015,52(10):23632372. Liu Yao, Kang Xiaohui, Gao Hong, et al. A community detection method based on the node intimacy and degree in social network [J]. Journal of Computer Research and Development, 2015, 52(10): 23632372. [59] Blondel V D, Guillaume J L, Lambiotte R, et al. Fast unfolding of communities in large networks [J]. Journal of Statistical Mechanics: Theory and Experiment, 2008: P10008. [60] 冷作福. 基于贪婪优化技术的网络社区发现算法研究[J]. 电子学报, 2014,42(4):723729. Leng Zuofu. Community detection in complex networks based on greedy optimization [J]. Acta Electronica Sinica, 2014, 42(4): 723729. [61] Guimera R, Amaral L.Functional cartography of complex metabolic networks [J]. Nature, 2005, 433: 895900. [62] Medus A, Acuna G, Dorso C. Detection of community structures in networks via global optimization [J]. Physica A: Statistical Mechanics and Its Applications, 2005, 358: 593604. [63] Ruan J, Zhang W. Identifying network communities with a high resolution [J]. Physical Review E, 2008, 77: 112. [64] 陈国强, 王宇平.基于极值优化模块密度的复杂网络社区检测[J]. 华中科技大学学报(自然科学版),2011,39(4):8285. Chen Guoqiang, Wang Yuping. Community detection in complex networks using extremal optimization modularity density [J]. Journal of Huazhong University of Science and Technology(Natural Science Edition), 2011, 39(4): 8285. [65] Aloise D, Cafieri S, Caporossi G, et al. Column generation algorithms for exact modularity maximization in networks [J]. Physical Review E, 2010, 82: 046112. [66] Bennett L, Liu S, Papageorgiou L G, et al. Detection of disjoint and overlapping modules in weighted complex networks [J]. Advances in Complex Systems, 2012, 15: 11500. [67] 黄发良, 张师超, 朱晓峰. 基于多目标优化的网络社区发现方法[J]. 软件学报, 2013, 24(9):20622077. Huang Faliang, Zhang Shichao, Zhu Xiaofeng. Discovering network community based on multi-objective optimization [J]. Journal of Software, 2013, 24(9): 20622077. [68] Tasgin M, Bingol A. Communities detection in complex networks using genetic algorithms [C]. Proc Eur Conf Complex Syst, 2006, 16. [69] Pizzuti C. Community detection in social networks with genetic algorithms [C]. Proc 10th Annu Conf Genetic Evol comput, 2008, 11371138. [70] Shen H, Cheng X, Cai K, et al. Detect overlapping and hierarchical community structure in networks [J]. Physical A: Statistical Mechanics and its Applications, 2009,388:17061712. [71] 周东青,王星,程嗣怡,等. 离散粒子群社区检测算法[J]. 系统工程与电子技术, 2016,38(2):428433. Zhou Dongqing, Wang Xing, Cheng Siyi, et al. Community detection algorithm via discrete PSO [J]. Systems Engineering and Electronics, 2016, 38(2): 428433. [72] Bi X J, Xiao J. Classification-based self-adaptive differential evolution with fast and reliable convergence performance [J]. Soft Computing, 2011, 15(8):15811599. [73] 王艳娇,肖婧.基于改进人工蜂群算法的高维多目标优化[J].中南大学学报(自然科学版),2015,46(6):21092117. Wang Yanjiao, Xiao Jing. Optimization of multi-objective problems based on artificial bee colony algorithm [J]. Journal of Central South University(Science and Technology), 2015, 46(6): 21092117. [74] Esmat R, Hossein N, Saeid S. GSA: a gravitational search algorithm [J]. Information Sciences, 2009,179, 22322248. [75] Cuevas E, Cienfuegos M, Zaldívar D, et al. A swarm optimization algorithm inspired in the behavior of the social-spider [J]. Expert Systems with Applications, 2013,40 (16):63746384. [76] 肖婧,毕晓君,王科俊.基于全局排序的高维多目标进化算法研究[J].软件学报,2015,26(7):15741583. Xiao Jing, Bi Xiaojun, Wang Kejun. Research of global ranking based many-objective optimization[J]. Journal of Software, 2015, 26(7):15741583. [77] 索勃,李战怀,陈群,等.基于信息流动分析的动态社区发现方法[J]. 软件学报, 2014,25(3):547559. Suo Bo, Li Zhanhuai, Chen Qun, et al. Dynamic community detection based on information flow analysis [J]. Journal of Software, 2014, 25(3):547559. [78] 国琳,左万利,彭涛. 基于隶属度的社会化网络重叠社区发现及动态集群演化分析[J]. 电子学报, 2016, 44(3):587594. Guo Lin, Zuo Wanli, Peng Tao. Overlapping community detection and dynamic group evolution analysis based on the degree of membership in social network [J]. Acta Electronica Sinica, 2016, 44(3):587594.
