Link Prediction In Complex Networks And Its Application In Networks Disintegration

Complex networks describe a wide range of systems in nature and society.Examples include the Internet,metabolic networks,electric power grids,supply chains,urban road networks,and the world trade web among many others.The study of complex networks has become an important area of multidisciplinary research involving physics,mathematics,biology,social sciences,informatics,and other theoretical and applied sciences.Due to its broad applications,research on the structural robustness of complex networks,i.e.,the ability to endure threats and survive accidental events,has received growing attention and has become one of the central topics in the complex network research.In the majority of cases,networks are beneficial,such as power grids and Internet,where we want to preserve their function.Many studies have considered methods for maximizing the structural robustness of these beneficial networks.In another situation by which this paper is motivated,however,we want to disintegrate a network if it is harmful,such as immunizing a population in social networks or suppressing the virus propagation in computer networks.The immunization problem is mathematically equivalent to asking how to disintegrate a given network with a minimum number of node removals,which is very important since in most cases the number of immunization doses is limited or very expensive.Other examples of network disintegration include destabilizing terrorist networks,preventing financial contagion,controlling the rumor diffusion,and perturbing cancer networks.In the early works on network disintegration,it was usually assumed that the attacker can obtain perfect information on the network structure,in other words,they assumed that the observed networks are complete.However,the complete information of network structure is not always available in realistic cases.Growing attention has been paid to the study of network disintegration with imperfect information.In this paper we focus on an important and frequent scenario of imperfect information,such that part of links(i.e.,interactions between nodes)are missing in the observed network.In many real networks,such as food webs,terrorist networks,sexual contact networks,protein-protein interaction networks,and disease relationship networks,it is easy to obtain the information of nodes,but difficult to detect the relations or interactions between nodes,which is usually costly or even infeasible.The missing links may reduce the network disintegration performance.To address this problem,a potential approach is to recover the missing links(or part of the missing links),which remind us the so-called "link prediction" problem.Link prediction algorithms aim at estimating the likelihood of the existence of a link between two nodes based on the observed network structure and the attributes of nodes.Therefore,before the attack we can use one of the link prediction algorithms to recover parts of the missing links and then identify the targets based on the "improved" network.This dissertation considers the introduction of link prediction to solve the complex network collapse problem under incomplete information conditions.At the same time,it conducts in-depth research on complex network link prediction problems,focusing on "how to describe network disintegration information,introducing and implementing link prediction","How to calculate the structural predictability of the network itself" and "How to build a link prediction accuracy evaluation system".In this dissertation,we deeply and systematically studied the modeling problem of complex network collapse under incomplete information conditions,and solved key technical problems such as prediction algorithm selection,prediction ratio determination and prediction accuracy evaluation in the link prediction process.The main research work and innovations of the thesis are as follows:(1)Introduce a new method based on spectrum to measure link predictability.By analyzing the characteristic spectrum of the network,we proposed the network link predictability index.By calculating the index,it is possible to obtain how difficulty the target network can be predicted before choosing algorithm,and to solve whether the problem is an unpredictable network or an inappropriate algorithm.The results are useful with the selection and matching of complex network and link prediction algorithms.(2)Introduce link prediction into the complex network disintegration model.Study and use link prediction in a new viewpoint of complex network.Improve the disintegration result by using link prediction recover part of missing information effetely.(3)Reveal the link prediction comic effect.We found with surprise that if the magnitude of missing link information is not too large,the effect of network disintegration with the assistance of link prediction even can be better than the case of complete link information.We called this phenomenon the “comic effect” of link prediction.Although,the link prediction does not recover the missing information completely,but it reshapes the network just like an exaggerated but characteristic comic.(4)Propose a new index based on edge significance: Structural Precision.We characterize the edge significance in the network topology into two aspects: improving the clustering characteristics and maintaining the global connectivity.The results show that the indices could give a comprehensive evaluation to algorithms and describe algorithmic accuracies with network structure.(5)Design and realize a complex network attack modeling and analysis demonstrate system.This system can demonstrate generating network,hiding some information,link prediction and attacking with sorts of strategy.