Node Immunization in Networks with Uncertainty

摘要

In immunization strategy, the general focus is to identify and prevent malicious attacks or malware spreading from one node to its neighboring nodes in static networks. However, in many different real-world applications, the transmission routes are uncertain or unstable. The number of uncertain edges determines the number of networks that can be produced, which are referred to as sample networks. Large number of sample networks will significantly increase the computational complexity in the network with uncertainty. In this paper, we first propose a measure to assess the spread of disease or virus in networks with uncertainty (e.g. in a technical network, connections between nodes may fail due to the unstable signal). Specifically, we introduce the concepts of excepted eigenvalue (EE) and excepted fraction of infected node (EF) to quantify the spread strength and influence of disease or viruses. The aim is to minimize the EE and EF values of the remaining network after immunizing with k nodes. Therefore, we design an algorithm based on the characteristics of degree and largest eigenvalue in uncertain networks. We also select an appropriate number of sample networks to reduce the computational cost and guarantee high accuracy level. Findings from the simulations on synthetic and real networks demonstrate the effectiveness of our proposed approach.