The Analysis,Evolutionary Optimization,and Application Of The Robustness Of Complex Networks

The complex network is an interdisciplinary research crossing computational mathematics,physics,computer science,biology,and so on.Network theories and methodologies provide solutions to analyze the structure of large-scale systems,the function dynamics of systems members,the distribution discipline of functional clusters,etc.Different systems with various structures sustain different tasks,and these systems are often exposed to complicated application environments,where damages like natural disasters or intentional ruin may disturb the normal function of networked systems.Considering this situation,a robust system,which can still keep partly functional even suffering from attacks or errors,is desirable.In order to evaluate the invulnerability of networks against damages and provide the guidance for potential performance enhancement processes,the robustness of networks has attracted increasing attention in recent studies,which is the focus of this thesis.Focusing on the robustness of networks,this thesis first concentrates on the correlation study between network performances and network structural metrics.Based on the obtained conclusions,we have studied the robustness evaluation and optimization problems under multiple scenarios,and several high-efficient and effective optimization methods are successfully designed.Further,the robustness evaluation and optimization techniques have been extended into the study of social activity analysis on networks.The topics including evolutionary games,the community structure and the influence spreading process have shown great values in the in-depth application of network robustness.These studies explore more potential applications of robust networks,and enrich the techniques for networks' performance analysis.The developed methods provide useful tools for solving realistic dilemmas.The major work of this thesis can be summarized as follows,1.Many metrics have been designed to evaluate the structural features of networks from different aspects.But,some important issues,such as the relationship between these metrics and network performances and the correlation between different metrics have not been thoroughly studied.Taking scale-free networks as an example,we manage to generate networks with different scaling exponents and assortativity,and evaluate the performance of these networks using several measures to show the correlation between structural features and network robustness.The experimental results show that networks with smooth degree distribution and assortative structure tend to perform well under malicious attacks.Also,related analyses have been applied to networks with multiple layers.The obtained analytical conclusion is useful for the construction and performance enhancement of networks.2.The topological rewiring has been proven to be effective in improving networks' performances.Existing studies provide several evaluation and optimization methods for different attack models,but a simultaneous co-optimization on multiple types of attacks is scarce.Related experiments indicate there exists independence between optimization processes guided by different measures,which leads to the situation that only partial improvements on the robustness can be achieved utilizing single-objective optimization methods on networks.This thesis takes both malicious attacks and cascading failures into account,and intends to design networks with comprehensive robustness with the help of a normalization performance measure and the multi-agent genetic algorithm.The effectiveness of the method is validated on various network data.3.Existing methods may require prohibitive computational cost,which is caused by the dependence of search processes on performance measures.A possible solution is to avoid invoking high-cost measures frequently and keep the efficacy of the optimization methods as well.The graph embedding technique has been applied to represent networks with lowdimension vectors,based on which,surrogate models have been introduced into the optimization of networks.An ensemble consisting of several different surrogates is devised to estimate the robustness values of networks at low cost.Optimization strategies towards single-objective or multi-objective network robustness enhancement tasks are also designed.The results on different networks validate that the utilization of surrogates contributes to the computational efficiency of searching processes,and a sharp reduction on necessary running time has been reached.4.A series of evolutionary game models have been introduced,and some studies indicated the importance of the robustness of evolution for networks.In this thesis,we investigate the robustness of evolution under edge-based attacks,which also demonstrates the marked influence induced by structural damages on cooperative behaviors.Combined with the robustness of networks,we model the construction of robust and cooperative networks as a multi-objective problem,and some potential applications of this problem have been shown.For solving such a problem,different operators have also been devised to cater to plain or directed networks,and the designed multi-objective evolutionary algorithms have been validated through experiments.5.Community structures give descriptions to functional clusters in a system,and the robustness of communities also dominates some dynamical processes of networks.The deficiency of existing measures for community robustness has been shown through comparable experiments.Reliable measures are given in this thesis for both node-based and edge-based attacks,which work as performance indicators in corresponding optimization processes.Meanwhile,networks with multiple layers are also considered,a rational extension of the existing measure has been made to guide the community robustness enhancement on this kind of networks.Further,we also focus on the robustness of signed networks with attributive information,and the effect of different structural balance results on the invulnerability of signed networks has been revealed.6.Last but not least,we also intend to solve the influence maximization problem on networks with multiple layers,and a measure that evaluates the spreading ability of seeds on multilayer networks is designed.With the help of structural information,an evolutionary seed selection strategy has been devised.Furthermore,we study the robustness of information spreading process against structural damages.The experiments indicate that the loss of structural connectivity gives the clear restraint to the information spreading ability of seeds,and seeds with robust spreading ability is of necessity in applications.