Node Immunization on Large Graphs: Theory and Algorithms

Abstract—Given a large graph, like a computer communication network, which k nodes should we immunize (or monitor, or remove), to make it as robust as possible against a computer virus attack? This problem, referred to as the Node Immunization problem, is the core building block in many high-impact applications, ranging from public health, cybersecurity to viral marketing. A central component in Node Immunization is to find the best k bridges of a give graph. In this setting, we typically want to determine the relative importance of a node (or a set of nodes) within the graph, for example, how valuable (as a bridge) a person or a group of persons is in a social network. First of all, we propose a novel ‘bridging ’ score ∆λ, inspired by immunology, and we show that its results agree with intuition for several realistic settings. Since the straightforward way to compute ∆λ is computationally intractable, we then focus on the computational issues and propose a surprisingly efficient way (O(nk2 + m)) to estimate it. Experimental results on real graphs show that (1) the proposed ‘bridging ’ score gives mining results consistent with intuition; and (2) the proposed fast solution is up to 7 orders of magnitude faster than straightforward alternatives