The Robustness Optimization Of Complex Networks

The optimization of complex networks is a popular research topic based on thedevelopment of perturbation theory. Two key measures that can reflect the robustnessof complex networks are connectivity and synchronization. According to differentstandards, complex networks can be divided into static wired networks and dynamicwireless networks. In this thesis, with the purpose of robustness optimization of thecomplex networks, we propose two schemes that can optimize the connectivity ofstatic wired networks and the synchronization of dynamic wireless ad hoc networksbased on the relevant perturbation theory, respectively. Moreover, the optimization ofrobustness in complex networks is actually an application of robustness analysis, andit is useful as a guidance for building real world networks. The major contributions ofthis thesis are listed as follows:Firstly, we derive the spectral density expression of BA scale-free networks. Ouroptimization scheme of connectivity is based on the spectral density, therefore it isnecessary to derive the spectral density expression of the object models. RegardingBA scale-free networks, no previous paper has given the exact formula of its spectraldensity. In this thesis, combining with existing theories, we propose the spectraldensity mathematical expression of BA networks.Secondly, regarding the connectivity, most of the existing optimization methodsare based on algebraic connectivity by adding one or two links. Moreover, thesemethods do not consider that the change of the topology may lead to the change of theoriginal networks’ property. They neither indicate whether more links could be addedinto the original networks. Therefore, in this thesis, we choose subgraph centrality asthe optimization objective and propose an optimization scheme to add more links.The application of spectral density in this scheme can guarantee that the networktopology property remains unchanged. Then, combining with the spectral densityformula of these two networks, we obtain the optimal spectrum for each network. Tocompare the structural differences between these two networks, we define a metric,denoted as MD, where its value is derived by assigning different weights to differenteigenvalues and calculating their mean square error. Finally, through extensive simulations, we get the number of links that needs to be added to various networksunder our optimization scheme. Through analyzing the experimental results, we findout the relationship between the required number of links and the related parametersof the networks.Finally, regarding the synchronization, the ad hoc network is the research objectof this thesis. We propose a scheme that can remove mobile nodes one by one. In theprocess of optimization, the second smallest eigenvalue of the Laplacian matrix ischosen as theoretical basis for our optimization. We propose two schemes based onthe minimum degree and the spectrum of Laplacian matrix, respectively. Then,through simulations, we make a quantitative analysis of the relationship between thenumber of deleted nodes and the transmission radius when the network achieves theoptimal synchronization. We also make a qualitative analysis of the number of deletednodes and the size of network, the suspend time and the moving speed of the mobilenodes. Finally, we conclude that the synchronization scheme based on node degree isequivalent to the synchronization scheme based on the spectrum of Laplacian matrix.In summary, the idea of the robustness optimization proposed in this thesis couldserve as some guidances for building real world networks.