基于网络效率最优的关键节点识别方法
|
摘要
准确合理地找出网络中的关键节点并加以保护,对提高网络的鲁棒性、稳定性有着重要的意义。因此,从优化的角度提出一种基于网络效率最优的关键节点识别方法。通过网络结构赋权构造一种网络鲁棒性测度函数,以此为目标函数利用萤火虫算法进行优化搜索,其中在离散化的基础上,用佳点集的思想构造初始序列,采用分区寻优的方法快速搜索满足测度函数的最优序列,在搜索过程中通过增加可变全局吸引力和自适应随机项,使得优化搜索能够准确收敛,实现对网络关键节点的识别。实验分析结果表明,所提方法识别效果更佳,对不同的网络结构具有一定通用性,所用改进萤火虫算法收敛速度更快,准确性更高。
Finding the key nodes in a network and taking measures to protect them is significant to improve the robustness and stability of the network.Therefore,a key node recognition method based on optimal network efficiency was developed from the perspective of optimization.A network robustness objective function was constructed by weighting the network,and firefly algorithm was utilized so that the optimal value was searched with the object function.The initial sequence was constructed according to good points set.Moreover,the optimal sequence that satisfied the objective function quickly was found with the help of partition optimization.During the search process,by adding variable global attraction and adaptive terms,the optimal search converged more accurately,so as to recognize the key nodes in the network.Results of simulations show that the proposed method performs better than the previous ones and it is applicable to different network structures.Furthermore,the modified firefly algorithm converges faster and more accurately.
Finding the key nodes in a network and taking measures to protect them is significant to improve the robustness and stability of the network.Therefore,a key node recognition method based on optimal network efficiency was developed from the perspective of optimization.A network robustness objective function was constructed by weighting the network,and firefly algorithm was utilized so that the optimal value was searched with the object function.The initial sequence was constructed according to good points set.Moreover,the optimal sequence that satisfied the objective function quickly was found with the help of partition optimization.During the search process,by adding variable global attraction and adaptive terms,the optimal search converged more accurately,so as to recognize the key nodes in the network.Results of simulations show that the proposed method performs better than the previous ones and it is applicable to different network structures.Furthermore,the modified firefly algorithm converges faster and more accurately.
引文
[1]REN Zhuoming,SHAO Feng,LIU Jianguo,et al.Node importance measurement based on the degree and clustering coefficient information[J].Acta Physica Sinica,2013,62(12):522-526(in Chinese).[任卓明,邵凤,刘建国,等.基于度与集聚系数的网络节点重要性度量方法研究[J].物理学报,2013,62(12):522-526.]
[2]Wang T,Dai W,Jiao P,et al.Identifying influential nodes in dynamic social networks based on degree-corrected stochastic block model[J].International Journal of Modern Physics B,2016,30(16):0092-0100.
[3]Sun Z,Wang B,Sheng J,et al.Identifying influential nodes in complex networks based on weighted formal concept analysis[J].IEEE Access,2017,5(99):3777-3789.
[4]Singh R,Chakraborty A,Manoj BS,et al.GFT centrality:A new node importance measure for complex networks[J].Physica A Statistical Mechanics&Its Applications,2017,487(5):185-195.
[5]Zeng A,Zhang CJ.Ranking spreaders by decomposing complex networks[J].Physics Letters A,2013,377(14):1031-1035.
[6]Liu JG,Ren ZM,Guo Q.Ranking the spreading influence in complex networks[J].Physica A Statistical Mechanics&Its Applications,2013,392(18):4154-4159.
[7]Deng Y,Wu J,Tan YJ.Optimal attack strategy of complex networks based on tabusearch[J].Physica A Statistical Mechanics&Its Applications,2016,442(1):74-81.
[8]SUN Yu,YAO Peiyang,ZHANG Jieyong,et al.Node attack strategy of complex networks based on optimization theory[J].Journal of Electronics&Information Technology,2017,39(3):518-524(in Chinese).[孙昱,姚佩阳,张杰勇,等.基于优化理论的复杂网络节点攻击策略[J].电子与信息学报,2017,39(3):518-524.]
[9]WANG Jiasheng, WU Xiaoping,CHEN Yongqiang.Invulnerability simulation of weighted complex networks with different information[J].Journal of Central South University(Science and Technology),2013,44(5):1887-1894(in Chinese).[王甲生,吴晓平,陈永强.不同信息条件下加权复杂网络抗毁性仿真研究[J].中南大学学报(自然科学版),2013,44(5):1887-1894.]
[10]Liu J,Xiong Q,Shi W,et al.Evaluating the importance of nodes in complex networks[J].Physica A Statistical Mechanics&Its Applications,2016,452(1):209-219.
[11]Yang XS. Nature-inspired metaheuristic algorithms[M].Beckington:Luniver Press,2008.
[12]YU Hongtao,GAO Liqun,HAN Xichang.Discrete artificial firefly algorithm for solving traveling salesman problems[J].Journal of South China University of Technology(Natural Science Edition),2015,43(1):126-131(in Chinese).[于宏涛,高立群,韩希昌.求解旅行商问题的离散人工萤火虫算法[J].华南理工大学学报(自然科学版),2015,43(1):126-131.]
[13]Zhang B,Hong Q,Sun SC,et al.A novel hybrid ant colony optimization and particle swarm optimization algorithm for inverse problems of coupled radiative and conductive heat transfer[J].Thermal Science,2016,20(2):23-23.
[14]Zhang LN,Liu LQ,Yuan GN,et al.Modified firefly algorithm using randomized mechanisms[C]//Evolutionary Computation.IEEE,2016:2255-2261.
[15]RUAN Yirun,LAO Songyang,WANG Junde,et al.Node importance measurement based on neighborhood similarity in complex network[J].Acta Physica Sinica,2017,66(3):365-373(in Chinese).[阮逸润,老松杨,王竣德,等.基于领域相似度的复杂网络节点重要度评估算法[J].物理学报,2017,66(3):365-373.]
[16]HAN Zhongming,CHEN Yan,LI Mengqi,et al.An efficient node influence metric based on triangle in complex networks[J].Acta Physica Sinica,2016,65(16):285-296(in Chinese).[韩忠明,陈炎,李梦琪,等.一种有效的基于三角结构的复杂网络节点影响力度量模型[J].物理学报,2016,65(16):285-296.]
[17]YU Hui,LIU Zun,LI Yongjun.Key nodes in complex networks identified by multi-attribute decision-making method[J].Acta Physica Sinica,2013,62(2):46-54(in Chinese).[于会,刘尊,李勇军.基于多属性决策的复杂网络节点重要性综合评价方法[J].物理学报,2013,62(2):46-54.]
[18]XIAO Yunpeng,LI Songyang,LIU Yanbing.An information diffusion dynamic model based on social influence and mean-field theory[J].Acta Physica Sinica,2017,66(3):227-239(in Chinese).[肖云鹏,李松阳,刘宴兵.一种基于社交影响力和平均场理论的信息传播动力学模型[J].物理学报,2017,66(3):227-239.]
[2]Wang T,Dai W,Jiao P,et al.Identifying influential nodes in dynamic social networks based on degree-corrected stochastic block model[J].International Journal of Modern Physics B,2016,30(16):0092-0100.
[3]Sun Z,Wang B,Sheng J,et al.Identifying influential nodes in complex networks based on weighted formal concept analysis[J].IEEE Access,2017,5(99):3777-3789.
[4]Singh R,Chakraborty A,Manoj BS,et al.GFT centrality:A new node importance measure for complex networks[J].Physica A Statistical Mechanics&Its Applications,2017,487(5):185-195.
[5]Zeng A,Zhang CJ.Ranking spreaders by decomposing complex networks[J].Physics Letters A,2013,377(14):1031-1035.
[6]Liu JG,Ren ZM,Guo Q.Ranking the spreading influence in complex networks[J].Physica A Statistical Mechanics&Its Applications,2013,392(18):4154-4159.
[7]Deng Y,Wu J,Tan YJ.Optimal attack strategy of complex networks based on tabusearch[J].Physica A Statistical Mechanics&Its Applications,2016,442(1):74-81.
[8]SUN Yu,YAO Peiyang,ZHANG Jieyong,et al.Node attack strategy of complex networks based on optimization theory[J].Journal of Electronics&Information Technology,2017,39(3):518-524(in Chinese).[孙昱,姚佩阳,张杰勇,等.基于优化理论的复杂网络节点攻击策略[J].电子与信息学报,2017,39(3):518-524.]
[9]WANG Jiasheng, WU Xiaoping,CHEN Yongqiang.Invulnerability simulation of weighted complex networks with different information[J].Journal of Central South University(Science and Technology),2013,44(5):1887-1894(in Chinese).[王甲生,吴晓平,陈永强.不同信息条件下加权复杂网络抗毁性仿真研究[J].中南大学学报(自然科学版),2013,44(5):1887-1894.]
[10]Liu J,Xiong Q,Shi W,et al.Evaluating the importance of nodes in complex networks[J].Physica A Statistical Mechanics&Its Applications,2016,452(1):209-219.
[11]Yang XS. Nature-inspired metaheuristic algorithms[M].Beckington:Luniver Press,2008.
[12]YU Hongtao,GAO Liqun,HAN Xichang.Discrete artificial firefly algorithm for solving traveling salesman problems[J].Journal of South China University of Technology(Natural Science Edition),2015,43(1):126-131(in Chinese).[于宏涛,高立群,韩希昌.求解旅行商问题的离散人工萤火虫算法[J].华南理工大学学报(自然科学版),2015,43(1):126-131.]
[13]Zhang B,Hong Q,Sun SC,et al.A novel hybrid ant colony optimization and particle swarm optimization algorithm for inverse problems of coupled radiative and conductive heat transfer[J].Thermal Science,2016,20(2):23-23.
[14]Zhang LN,Liu LQ,Yuan GN,et al.Modified firefly algorithm using randomized mechanisms[C]//Evolutionary Computation.IEEE,2016:2255-2261.
[15]RUAN Yirun,LAO Songyang,WANG Junde,et al.Node importance measurement based on neighborhood similarity in complex network[J].Acta Physica Sinica,2017,66(3):365-373(in Chinese).[阮逸润,老松杨,王竣德,等.基于领域相似度的复杂网络节点重要度评估算法[J].物理学报,2017,66(3):365-373.]
[16]HAN Zhongming,CHEN Yan,LI Mengqi,et al.An efficient node influence metric based on triangle in complex networks[J].Acta Physica Sinica,2016,65(16):285-296(in Chinese).[韩忠明,陈炎,李梦琪,等.一种有效的基于三角结构的复杂网络节点影响力度量模型[J].物理学报,2016,65(16):285-296.]
[17]YU Hui,LIU Zun,LI Yongjun.Key nodes in complex networks identified by multi-attribute decision-making method[J].Acta Physica Sinica,2013,62(2):46-54(in Chinese).[于会,刘尊,李勇军.基于多属性决策的复杂网络节点重要性综合评价方法[J].物理学报,2013,62(2):46-54.]
[18]XIAO Yunpeng,LI Songyang,LIU Yanbing.An information diffusion dynamic model based on social influence and mean-field theory[J].Acta Physica Sinica,2017,66(3):227-239(in Chinese).[肖云鹏,李松阳,刘宴兵.一种基于社交影响力和平均场理论的信息传播动力学模型[J].物理学报,2017,66(3):227-239.]