一种针对网络结构破坏下鲁棒影响力最大化问题的Memetic算法  

A Memetic Algorithm for Solving the Robust Influence Maximization Problem Towards Network Structural Perturbances

作　　者：王帅 刘静 WANG Shuai;LIU Jing(School of Intelligent Systems Engineering,Sun Yat-Sen University,Shenzhen,Guangdong 518107;School of Artificial Intelligence,Xidian University,Xi’an 710071)

机构地区：[1]中山大学智能工程学院,广东深圳518107 [2]西安电子科技大学人工智能学院,西安710071

出　　处：《计算机学报》2021年第6期1153-1167,共15页Chinese Journal of Computers

基　　金：国家科技部科技创新2030重大项目(2018AAA0101302);国家自然科学基金面上项目(61773300)资助.

摘　　要：复杂网络问题的建模与应用是目前研究的热点之一.如何从网络中选择具有信息传播能力的成员,即影响力最大化问题,引发了广泛的关注.目前的研究主要集中在如何将网络上的信息传播过程建模,以及如何选择可靠的传播种子节点.这些工作一定程度上帮助我们了解了网络上的信息传播过程,但是已有研究并未考虑外界因素对于网络系统的影响,比如结构损毁对于网络连通性以及网络上信息传播过程造成的干扰.这使得目前的影响力最大化问题解决方案无法鲁棒地应对现实中的多种应用场景.针对这一不足,本文从结构受损的角度定义了鲁棒影响力最大化问题,在已有工作的基础上设计了对应的性能衡量指标.在该指标的指导下,设计了尝试解决鲁棒影响力最大化(Robust Influence Maximization,RIM)问题的Memetic算法(Memetic Algorithm,MA),记为MA-RIM,其目的是寻找具有鲁棒信息传播能力的种子节点.多种网络上的实验结果验证了MA-RIM算法在解决鲁棒影响力最大化问题上的有效性.The complex network has attracted broad attention in recent researches.This filed maintains a series of challenging problems,including the community detection,the robustness optimization,the social network analysis,and the information diffusion process.Much progress has been made in previous studies in summarizing the dynamics of different networked systems and enhancing the performance of networks.Meanwhile,the rapid development of social network services attracts millions of users to attend the network-based information spreading process.Consequently,a growing interest can be found on the influence maximization problem,which is generally defined as selecting system members with considerable ability to spread influence.Existing studies mainly concentrated on how to model the information spreading process on networked systems,and corresponding seed selection strategies to reach a better influence level.In these studies,the structure of network keeps almost unchanged,and the constructed model and obtained seeds may be only effective on current status.However,little attention has been paid to the complicated application environment of networks.Potential failures tend to cause damages on network structures.Such failures always hinder the related influence spreading process,and the structure of networks tend to be disturbed as well.The existence of uncertainty and failures prevents a robust utilization of current solutions on realistic scenarios,and a thorough study is still required.Considering such deficiency,we intend to define the robust influence maximization problem(RIM),and a rational performance metric has been designed based on existing studies.In terms of the information diffusion process,the designed metric employs a numerical evaluation strategy to estimate the performance of seeds in a specific state of the inputted network.The reliability of such strategy was verified in several pilot studies.Then,in terms of the network destruction process,we focus on link-based attacks and the whole process of losing

关 键 词：复杂网络 影响力最大化问题 鲁棒性 优化 MEMETIC算法 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]