Node Immunization on Large Graphs: Theory and Algorithms

摘要

Given a large graph, like a computer communication network, which 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 bridges of a given 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 () to estimate it. Experimental results on real graphs show that (1) the proposed ‘bridging’ score gives mining results consistent with intuition; and (2) th- proposed fast solution is up to faster than straightforward alternatives.