| The propagation phenomenon happening in complex networks is commonly seen in physical and digital world,including the spread of biological viruses,computer worms,rumors in social-media,and online brand marketing.Among them,negative propagation objects such as infectious diseases,viruses,rumors are very difficult to simulate and control in the real world owing to the huge expenditure and high risk of control failure.In such situation,mathematical simulation and mimic control therefore become feasible ways in propagation crisis.However,as the increasing of network scale and problem complexity,the traditional models and control methods maybe not sufficient enough to meet the requirements of realistic propagation control.Evolutionary computation,as a typical kind of stochastic optimization methods,can be used to solve complex propagation optimization problems.However,it is faced with challenges such as insufficient adaptability and insufficient efficiency.This thesis studies on the subject of propagation simulation and control,which mainly focuses on the problems of negative propagation control(such as disease propagation control and virus propagation control)and takes evolutionary computation as the major research method.The main contributions are as follows:(1)A comprehensive study on the application of evolutionary computation(EC)in propagation problems is developed.First,we investigate the related studies about complex network propagation,and divided them into three categories: simulation,optimization,and detection & analysis.The simulation researches are developed to simulate various propagation phenomena in real world and analyze their dynamic characteristics.The optimization researches are most about minimizing negative propagation or maximizing positive propagation.The researches about propagation detection and analysis focus on the detection and analysis of fake news content,propagation source,propagation path,etc.Secondly,we introduce the application status of evolutionary computation in social propagation problems.Finally,the open issues in the design of evolutionary algorithms for solving complex network propagation problems are discussed.This study paves the way for evolutionary propagation dynamics in complex networks.(2)To meet the challenges that existing settings of continuous and abstract resources cannot simulate the real-world discrete/concrete resources well,this study designs a concrete resource description model based on an improved propagation model,to better describe the propagation phenomena and resource characteristics.Most existing researches emphasize on continuous and abstract resource allocation,which map the resources as the model parameters and the allocation of resources as the value changes of parameters,so that the negative propagation problems can be formulated as the optimization problems of continuous parameters.However,most realistic resources are some discrete commodities/services/ facilities,which have their own values and effects and whose allocation has specific mode,so that the corresponding discrete resource allocation problems are actually the complex subset selection problems.Confronted with the challenges,this study first evaluates the possible resource types in negative propagation control and defines some discrete resource types.Then a mathematical matrix is used to formulate the allocation of resources,which distinguish the resource allocation and the changes of model parameters.Next,the "cost-utility analysis" and "cost-benefit analysis" in economics are introduced to construct the cost function of each resource,the direct utility of each resource,and the overall benefit of all allocated resources.This model clarifies the connection between the control resources and the parameters of the propagation model.(3)To meet the challenges that existing continuous optimization methods can not effectively deal with the discrete optimization problems in epidemic control,and the existing discrete optimization methods are easily trapped into local optima and have low search diversity,this study proposes a swarm Optimizer with Priority-planning and Hierarchical-learning(PHSO),to provide high-quality solutions for complex discrete resource allocation problems.The proposed algorithm uses the level-based learning particle swarm algorithm as the basic classifier.Then,as the particles are divided into multiple groups,particles in the inferior group can learn from the ones in the superior group,to improve the search diversity.Next,by introducing hierarchical learning steps,the resources with high-priority can be gradually selected out,so that the convergence speed can be accelerated.Finally,based on the remaining budget,the remaining resources are selected as candidates to further improve the solution quality.Algorithm-level theoretical analysis shows that PHSO has good exploration and exploitation capabilities.In the comparative experiment,it is demonstrated that PHSO has leading advantages over some state-of-the-srt evolutionary algorithms.Finally,an application case on real-world datasets has been provided,which demonstrates the practical effectiveness of PHSO.(4)To meet the challenges that existing optimization methods are hard to deal with the high-dimensional,complex,and nonlinear objectives in propagation optimization problems happening in large-scale complex networks,this study proposes a Co-Evolutionary Algorithm with Network-Community-based Decomposition(NCD-CEA),to balance the solving efficiency and solution quality.The propagation optimization problems in large-scale complex networks encountered the “curse of dimensionality”.To solve the challenges,this study considers the neighborhood-based propagation characteristics and the properties of network community structure,and divide-and-conquer the problems.First,the proposed NCD-CEA designs a network community based dimensional decomposition strategy,which includes an improved Louvain algorithm to detect the network community structure and balance the number of communities and the size of community.Secondly,NCD-CEA includes a new alternative evolution strategy to coordinate the evolution of sub-population and the global population.The solutions generated by sub-populations are evaluated by the local fitness function to reduce the execution time.The evolution of the global population is started after a certain time interval to guide the evolution of the sub-populations,simultaneously enhance their diversity and further promote the global exploration.The proposed algorithm makes a new attempt to solve the combined discrete resource allocation problem in large networks.Experiments on various complex networks show that NCD-CEA outperforms than other competing algorithms in both convergence speed and solution quality.(5)To meet the challenges that the existing optimization methods are ill-adapted in solving the negative propagation problems with different goals and constraints,this study designs a Heuristic Majority-Voting Binary Particle Swarm Optimizer(HMV-BPSO).The algorithm includes a dichotomy-based repairing strategy is designed to quickly repair unqualified solutions.Then a heuristic factor is introduced to accelerate the convergence speed,which considers the probability distribution of the solutions and is independent from the problem.Numerous comparative experiments on different types of complex networks show the competitive performance of HMV-BPSO in solving the three kinds of problems with different goals and constraints. |
