Disintegrating Complex Networks Based On Link Prediction

With the rapid development of information technology, the human society entered the network era since entering the 21 st century. Networks such as Internet, telecommunications networks, power grids, transportation networks, and a variety of social networks, logistics network are become gradual expansion of the size, more complex of the structure and increasingly powerful of the function, it can be said that our lives are surrounded by various networks. However, except for the convenience they bring to human life, they produce a series of serious problems. In major cases, networks are beneficial, including examples like the Internet, the power-grids and the transportation, which we need to maximize their function. Over the past decade, on the contary, the outbreak and spread of virus like SARS, H1N1 and Ebola is more frequent and difficult to control; the sabotage of the terrorists is more rampant after 9/11. We want to minimum those networks with harmful function, such as epidemic spreading networks, terrorist networks through immunization, disturbances, collapse and other means to destroy its network structure, so that the network function is not working properly. Thus, the study of network disintegration has a broad application background. From random failure, intentional attack to disintegration based on incomplete information, as a focus, the study of disintegration model for complex networks is increasingly of great theoretical significance and application importance as an challenging topics of complex network theory.In this paper, guided by complex network and link prediction theory and regarding the less attention, especially in the case of incomplete link information, we introduce the link prediction into the network disintegration problem with incomplete link information. Using methods of statistical physics, graph theory, matrix theory, operation research, game theory, probability theory, mathematical statistics and computer simulation, we present a novel disintegration model by link prediction to recover missing links between nodes. The main results and contributions of this dissertation are as follows:(1) Introduce link prediction into the complex network disintegration model. We study and use link prediction in a new viewpoint of complex network. Considering incomplete information, link prediction technology which has the function of the data mining, forecasting and network evolution remodeling has been introduced into network disintegration modeling to effectively restore the missing parts of the network structure information. Cpmparied with random prediction, the link prediction algorithms improve prediction accuracy and efficiency more than 10 times. In the network disintegration view, it foucs on whether to find important nodes instead whether accurately recover the missing links. Some wrong links resulting in decreased accuracy of prediction, but does not affect if they help us find important nodes to enhance the disintegration effect of network.(2) Present a novel disintegration model in complex network by using link prediction. This article studies thoroughly and systematically the modeling, analysis by describing disintegration information, disintegration method, disintegration result and link prediction quantitatively. We did simulation analysis experiments in the scale-free networks and ER stochastic model. The study found that in scale-free networks, the model significantly improves the effect of complex networks' disintegration. But because ER network nodes' connected is a probability of the event itself is random, it is difficult to calculate their similarity. Thus, the model effect have not evidently increased.(3) Found the comic effect of link prediction. We find with surprise that if the magnitude of missing link information is small, the effect of network disintegration with link prediction can be better than the case of complete link information. We refer to this phenomenon as the “comic effect” of link prediction, which means that the network is reshaped by link prediction just like an exaggerated but characteristic comic. The attackers concern how to capture those nodes that have great impact on the network structure and function. It seems that the link prediction has a sharpening function as drawing tools, with a portrait photo, to display it as a comic, not as clear as the original photo but reflects the character feature in the highlight which play a crucial role in network disintegration.(4) The model effect of disrupt the 9.11 terrorist network is investigated. We use the terrorist organization's network as the background and the 9.11 hijackers network as the target network for application research. with relationships between the characters as a modeling perspective, we use the software Gephi to draw hijackers network structure. Then we analysis the effect of the model and link predicted on the target network. Studies show that our model have an outstanding performance.