基于多目标演化聚类的大规模动态网络社区检测
|
摘要
动态网络社区检测能揭示社区结构随时间演变的规律,是目前网络社区研究领域的热点之一.基于演化聚类的方法被广泛采用,但存在2个主要问题:1)缺乏结果校正机制,容易产生"结果漂移"和"误差累积"问题;2)问题的NP-难本质,导致基于模块度的精确社区结构检测在效率上存在很大问题.针对以上问题,通过对传统演化聚类框架和离散粒子群算法的改进及有效结合,提出一种高效且有效的多目标动态社区检测方法(multi-objective discrete particle swarm optimization for dynamic network, DYN-MODPSO),主要工作包括:1)提出基于最近未来参考策略的初始聚类结果校正方法,提高动态社区检测结果的有效性;2)改进传统粒子群算法,使其能与演化聚类框架有效结合;3)提出基于去冗余的随机游走初始群体生成方法,提高传统粒子群算法中的个体多样性并保证个体的初始精度;4)提出多个体交叉算子及改进的干扰算子,提高算法的局部搜索能力与收敛能力.大量基于真实和人工动态网络数据的实验结果证实,提出的方法在效率和有效性方面,显著优于同类比较算法.
Evolutionary clustering is often utilized for dynamic network community detection to uncover the evolution of community structure over time. However, it has the following main problems: 1) The absence of error correction may lead to the result-drifting problem and the error accumulation problem; 2) the NP-hardness of modularity based community detection makes it inefficient to get an exact solution. In this paper, an efficient and effective multi-objective method, namely DYN-MODPSO(multi-objective discrete particle swarm optimization for dynamic network), is proposed, where the traditional evolutionary clustering framework and the particle swarm algorithm are modified and enhanced, respectively. The main work of this article is as follows: 1) A novel strategy, namely the recently future reference, is devised for the initial clustering result correction to make the dynamic community detection more effective; 2) the traditional particle swarm algorithm is modified so that it could be effectively integrated with the evolutionary clustering framework; 3) the de-redundancy random walk based initial population generation method is presented to improve the diversity and the initial precision of the individuals; 4) the multi-individual crossover operator and the improved interference operator are developed to enhance the local search and the convergence abilities of DYN-MODPSO. Extensive experiments conducted on the real and the synthetic dynamic networks show that the efficiency and the effectiveness of DYN-MODPSO are significantly better than those of the competitors.
Evolutionary clustering is often utilized for dynamic network community detection to uncover the evolution of community structure over time. However, it has the following main problems: 1) The absence of error correction may lead to the result-drifting problem and the error accumulation problem; 2) the NP-hardness of modularity based community detection makes it inefficient to get an exact solution. In this paper, an efficient and effective multi-objective method, namely DYN-MODPSO(multi-objective discrete particle swarm optimization for dynamic network), is proposed, where the traditional evolutionary clustering framework and the particle swarm algorithm are modified and enhanced, respectively. The main work of this article is as follows: 1) A novel strategy, namely the recently future reference, is devised for the initial clustering result correction to make the dynamic community detection more effective; 2) the traditional particle swarm algorithm is modified so that it could be effectively integrated with the evolutionary clustering framework; 3) the de-redundancy random walk based initial population generation method is presented to improve the diversity and the initial precision of the individuals; 4) the multi-individual crossover operator and the improved interference operator are developed to enhance the local search and the convergence abilities of DYN-MODPSO. Extensive experiments conducted on the real and the synthetic dynamic networks show that the efficiency and the effectiveness of DYN-MODPSO are significantly better than those of the competitors.
引文
[1]Cheng Xueqi,Jin Xiaolong,Wang Yuanzhuo,et al.Overview of big data systems and analytical techniques[J].Jounal of Software,2014,3(9):1889-1908(in Chinese)(程学旗,靳小龙,王元卓,等.大数据系统和分析技术综述[J].软件学报,2014,3(9):1889-1908)
[2]Fortunato S.Community detection in graphs[J].Physics Reports,2009,486(3):75-174
[3]Sarkar P,Moore A W.Dynamic social network analysis using latent space models[J].ACM SIGKDD Explorations Newsletter,2005,7(2):31-40
[4]Cordeiro M,Rui P S,Gama J.Dynamic community detection in evolving networks using locality modularity optimization[J].Social Network Analysis&Mining,2016,6(1):15-17
[5]Li Xiaoming,Wu Bin,Guo Qian,et al.Dynamic community detection algorithm based on incremental identification[C]Proc of the 16th IEEE Int Conf Data Mining Workshop.Piscataway,NJ:IEEE,2016:900-907
[6]Lander B,Alejandro G.Multi-objective Graph Mining Algorithms for Detecting and Predicting Communities in Complex Dynamic Networks[M].Raleigh:NCSU,2017:35-75
[7]Ma Xiaoke,Dong Di.Evolutionary nonnegative matrix factorization algorithms for community detection in dynamic networks[J].IEEE Transactions on Knowledge&Data Engineering,2017,29(5):1045-1058
[8]Stanovov V,Brester C,Kolehmainen M,et al.Why don’t you use evolutionary algorithms in big data/[J].Materials Science and Engineering,2017,173(1):12-20
[9]Chakrabarti D,Kumar R,Tomkins A.Evolutionary clustering[C]Proc of the 12th ACM SIGKDD Conf on Knowledge Discovery and Data Mining.New York:ACM,2006:554-560
[10]Kim M S,Han Jiawei.A particle-and-density based evolutionary clustering method for dynamic networks[J].Proceedings of the VLDB Endowment,2009,2(1):622-633
[11]Folino F,Pizzuti C.An evolutionary multiobjective approach for community discovery in dynamic networks[J].IEEETransactions on Knowledge and Data Engineering,2014,26(8):1838-1852
[12]Hafez A I,Alshammari E T,Hassanien A E,et al.Genetic algorithms for multi-objective community detection in complex networks[C]Proc of the 14th IEEE Int Conf on Intelligent Systems Design and Applications.New York:IEEE,2014:145-171
[13]Gong Maoguo,Cai Qing,Chen Xiaowei,et al.Complex network clustering by multiobjective discrete particle swarm optimization based on decomposition[J].IEEE Transactions on Evolutionary Computation,2014,18(1):82-97
[14]Karimi-Majd A M,Fathian M,Amiri B.A hybrid artificial immune network for detecting communities in complex networks[J].Computing,2015,97(5):483-507
[15]Knowles J D,Corne D W.Approximating the nondominated front using the pareto archived evolution strategy[J].Evolutionary Computation,2014,8(2):149-172
[16]He Dongxiao,Zhou Xu,Wang Zuo,et al.Complex network community mining-genetic algorithm based on clustering fusion[J].Acta Automatica Sinica,2010,36(8):1160-1170(in Chinese)(何东晓,周栩,王佐,等.复杂网络社区挖掘-基于聚类融合的遗传算法[J].自动化学报,2010,36(8):1160-1170)
[17]Xu Zhengguo,Zheng Hui,He Liang,et al.Self-adaptive clustering based on local density by descending search[J].Journal of Computer Research and Development,2016,53(8):1719-1728(in Chinese)(徐正国,郑辉,贺亮,等.基于局部密度下降搜索的自适应聚类方法[J].计算机研究与发展,2016,53(8):1719-1728)
[18]Ahmed M M,Hafez A I,Elwakil M M,et al.A multiobjective genetic algorithm for community detection in multidimensional social network[C]Proc of the 1st Int Conf on Advanced Intelligent System and Informatics.Berlin:Springer,2016:129-139
[19]Li Yangyang,Wang Yang,Chen Jing,et al.Overlapping community detection through an improved multi-objective quantum-behaved particle swarm optimization[J].Journal of Heuristics,2015,21(4):549-575
[20]Chen Weineng,Yang Qiang.Probability distribution based evoluionary computation algorithms for multimodal optimization[J].Journal of Computer Research and Development,2017,54(6):1185-1197(in Chinese)(陈伟能,杨强.基于概率分布的多峰演化算法[J].计算机研究与发展,2017,54(6):1185-1197)
[21]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):26-53
[22]Institute of Web Science and Technologies at the University of Koblenz-Landau.Datasets[EB/OL].(2017-04-27)[2017-07-21].http:konect.uni-koblenz.de/networks/
[2]Fortunato S.Community detection in graphs[J].Physics Reports,2009,486(3):75-174
[3]Sarkar P,Moore A W.Dynamic social network analysis using latent space models[J].ACM SIGKDD Explorations Newsletter,2005,7(2):31-40
[4]Cordeiro M,Rui P S,Gama J.Dynamic community detection in evolving networks using locality modularity optimization[J].Social Network Analysis&Mining,2016,6(1):15-17
[5]Li Xiaoming,Wu Bin,Guo Qian,et al.Dynamic community detection algorithm based on incremental identification[C]Proc of the 16th IEEE Int Conf Data Mining Workshop.Piscataway,NJ:IEEE,2016:900-907
[6]Lander B,Alejandro G.Multi-objective Graph Mining Algorithms for Detecting and Predicting Communities in Complex Dynamic Networks[M].Raleigh:NCSU,2017:35-75
[7]Ma Xiaoke,Dong Di.Evolutionary nonnegative matrix factorization algorithms for community detection in dynamic networks[J].IEEE Transactions on Knowledge&Data Engineering,2017,29(5):1045-1058
[8]Stanovov V,Brester C,Kolehmainen M,et al.Why don’t you use evolutionary algorithms in big data/[J].Materials Science and Engineering,2017,173(1):12-20
[9]Chakrabarti D,Kumar R,Tomkins A.Evolutionary clustering[C]Proc of the 12th ACM SIGKDD Conf on Knowledge Discovery and Data Mining.New York:ACM,2006:554-560
[10]Kim M S,Han Jiawei.A particle-and-density based evolutionary clustering method for dynamic networks[J].Proceedings of the VLDB Endowment,2009,2(1):622-633
[11]Folino F,Pizzuti C.An evolutionary multiobjective approach for community discovery in dynamic networks[J].IEEETransactions on Knowledge and Data Engineering,2014,26(8):1838-1852
[12]Hafez A I,Alshammari E T,Hassanien A E,et al.Genetic algorithms for multi-objective community detection in complex networks[C]Proc of the 14th IEEE Int Conf on Intelligent Systems Design and Applications.New York:IEEE,2014:145-171
[13]Gong Maoguo,Cai Qing,Chen Xiaowei,et al.Complex network clustering by multiobjective discrete particle swarm optimization based on decomposition[J].IEEE Transactions on Evolutionary Computation,2014,18(1):82-97
[14]Karimi-Majd A M,Fathian M,Amiri B.A hybrid artificial immune network for detecting communities in complex networks[J].Computing,2015,97(5):483-507
[15]Knowles J D,Corne D W.Approximating the nondominated front using the pareto archived evolution strategy[J].Evolutionary Computation,2014,8(2):149-172
[16]He Dongxiao,Zhou Xu,Wang Zuo,et al.Complex network community mining-genetic algorithm based on clustering fusion[J].Acta Automatica Sinica,2010,36(8):1160-1170(in Chinese)(何东晓,周栩,王佐,等.复杂网络社区挖掘-基于聚类融合的遗传算法[J].自动化学报,2010,36(8):1160-1170)
[17]Xu Zhengguo,Zheng Hui,He Liang,et al.Self-adaptive clustering based on local density by descending search[J].Journal of Computer Research and Development,2016,53(8):1719-1728(in Chinese)(徐正国,郑辉,贺亮,等.基于局部密度下降搜索的自适应聚类方法[J].计算机研究与发展,2016,53(8):1719-1728)
[18]Ahmed M M,Hafez A I,Elwakil M M,et al.A multiobjective genetic algorithm for community detection in multidimensional social network[C]Proc of the 1st Int Conf on Advanced Intelligent System and Informatics.Berlin:Springer,2016:129-139
[19]Li Yangyang,Wang Yang,Chen Jing,et al.Overlapping community detection through an improved multi-objective quantum-behaved particle swarm optimization[J].Journal of Heuristics,2015,21(4):549-575
[20]Chen Weineng,Yang Qiang.Probability distribution based evoluionary computation algorithms for multimodal optimization[J].Journal of Computer Research and Development,2017,54(6):1185-1197(in Chinese)(陈伟能,杨强.基于概率分布的多峰演化算法[J].计算机研究与发展,2017,54(6):1185-1197)
[21]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):26-53
[22]Institute of Web Science and Technologies at the University of Koblenz-Landau.Datasets[EB/OL].(2017-04-27)[2017-07-21].http:konect.uni-koblenz.de/networks/