Research On Multi-objective Optimization Of Cascading Critical Node Detection In Complex Networks

As an important method to analyze network vulnerability,critical node detection has attracted more and more researchers' attention.Traditional critical node detection focuses on the static properties of the network(network topology),while ignoring the interdependence between nodes(cascading effect).However,there exists an obvious cascading relationship between nodes in many real-world complex networks,so this thesis starts the research on the critical nodes detection based on the cascading model in the complex networks.However,most of the current cascading critical node detection algorithms focus on designing effective attack strategies,ignoring the cost of the attack,and there exists an apparent conflict between the attack effect and attack cost.To this end,the critical node detection problem based on the cascading model is transformed into a multi-objective optimization problem,while considering the cost of the attack and the effect of the attack simultaneously.Cascading critical node detection is divided into methods for synchronous attack and mehods for sequential attack.Therefore,this thesis proposes a cascading critical node detection algorithm based on multiobjective optimization in complex networks for synchronous attacks,and proposes a multiobjective cascading critical node detection algorithm for sequential attacks.The main research works of this thesis are introduced as follows:(1)This thesis addresses the problem of cascading critical node detection from the perspective of multi-objective,and proposes a cascading critical node detection algorithm based on multi-objective optimization in complex networks(MO-BCVND).In the field of cascading critical node detection,most of the current research work focuses on designing effective attack strategies to maximize the damage to the network due to the failure of critical nodes,while ignoring the cost of attacks.However,in many practical applications,decision makers usually want to achieve the best effect of attack with the least cost.Based on this,this thesis transforms the cascading critical node detection problem into a multi-objective optimization problem(BCVND),where the cost of attack and the destructiveness of the attack are optimized simultaneously.In order to solve this multi-objective optimization problem,a cascading critical node detection algorithm based on multi-objective optimization in complex networks is proposed,termed as MO-BCVND.In addition,this thesis proposes an initialization strategy based on cost reduction for increasing the diversity of the population and an adaptive local search strategy is proposed for improving the convergence rate of the population.Finally,the experimental results on 12 real-world datasets verify the effectiveness of the MO-BCVND algorithm and the proposed strategies.At the same time,MO-BCVND can obtain a set of different levels of solutions at one time,which can be used to provide a global perspective for network vulnerability analysis.(2)This thesis proposes a multi-objective cascading critical node detection algorithm for sequential attacks(MO-BCVNDSeq).From the first research work,we can find that it is an effective way to solve the problem of cascading critical node detection from the perspective of multi-objective optimization.However,in the first research work,the main concern is that the cascading critical node detection is in a synchronous attack scenario,while ignoring the sequence of the attacks.Based on this,this thesis proposes a multi-objective cascading critical node detection algorithm for sequential attacks(MO-BCVNDSeq).In addition,in order to effectively consider the characteristics of sequential series,this thesis designs individual coding and corresponding crossover and mutation operations for sequential series;in order to accelerate population convergence,this thesis proposes an localsearch strategy based on time series matrix;in order to remove redundant nodes in individual coding,this thesis proposes an individual repair strategy.Finally,the experimental results on 12 real-world datasets verify the effectiveness of the MO-BCVNDSeq algorithm and the proposed strategies.