Title: Spectral Measure of Invulnerability of Complex Networks
Funding agency: National Natural Science Foundation of China
Grant reference: 60904065
Total funding: CNY 170,000
Period: Jan 2010-Dec 2012
PI: Jun Wu
Abstract: In the majority of cases, networks are beneficial, however, many times it may also be harmful, such as terrorist network and disease spreading network. It has become an urgent challenging problem to disintegrate these harmful networks by various methods such as immunization, block, isolation, disturbance and attack. The core task of network disintegration is to identify the critical nodes. Aiming at the problem of incomplete information in network disintegration, this project creatively introduces the new idea of link prediction and try to recover partial missing information based on link prediction, which may improve the effect of network disintegration. Based on the formal descriptions of network information, disintegration strategy, disintegration cost, disintegration effect and link prediction, this project firstly establishes the disintegration model of complex networks with incomplete information and investigates the impact of missing information on the effect of network disintegration. Then this project studies the methods of algorithm selection of link prediction and the optimal faction of prediction. Lastly, this project proposes the optimization model of disintegration strategy based on link prediction and presents the solution algorithm. This project will provide a new approach to solve the problem of network disintegration with incomplete information, such as the counterterrorism, disease immunity, military confrontation and so on. Moreover, it will provide an important reference for the application of link prediction in other fields.