Title: Spectral Methods for Immunization of Large Networks,
Abstract: Given a network of nodes, minimizing the spread of a contagion using a
limited budget is a well-studied problem with applications in network security,
viral marketing, social networks, and public health. In real graphs, virus may
infect a node which in turn infects its neighbor nodes and this may trigger an
epidemic in the whole graph. The goal thus is to select the best k nodes
(budget constraint) that are immunized (vaccinated, screened, filtered) so as
the remaining graph is less prone to the epidemic. It is known that the problem
is, in all practical models, computationally intractable even for moderate
sized graphs. In this paper we employ ideas from spectral graph theory to
define relevance and importance of nodes. Using novel graph theoretic
techniques, we then design an efficient approximation algorithm to immunize the
graph. Theoretical guarantees on the running time of our algorithm show that it
is more efficient than any other known solution in the literature. We test the
performance of our algorithm on several real world graphs. Experiments show
that our algorithm scales well for large graphs and outperforms state of the
art algorithms both in quality (containment of epidemic) and efficiency
(runtime and space complexity).