  The problem of identifying important players in a given network is of pivotal
importance for viral marketing, public health management, network security and
various other fields of social network analysis. In this work we find the most
important vertices in a graph G = (V,E) to immunize so as the chances of an
epidemic outbreak is minimized. This problem is directly relevant to minimizing
the impact of a contagion spread (e.g. flu virus, computer virus and rumor) in
a graph (e.g. social network, computer network) with a limited budget (e.g. the
number of available vaccines, antivirus software, filters). It is well known
that this problem is computationally intractable (it is NP-hard). In this work
we reformulate the problem as a budgeted combinational optimization problem and
use techniques from spectral graph theory to design an efficient greedy
algorithm to find a subset of vertices to be immunized. We show that our
algorithm takes less time compared to the state of the art algorithm. Thus our
algorithm is scalable to networks of much larger sizes than best known
solutions proposed earlier. We also give analytical bounds on the quality of
our algorithm. Furthermore, we evaluate the efficacy of our algorithm on a
number of real world networks and demonstrate that the empirical performance of
algorithm supplements the theoretical bounds we present, both in terms of
approximation guarantees and computational efficiency.
