  Viral spread on large graphs has many real-life applications such as malware
propagation in computer networks and rumor (or misinformation) spread in
Twitter-like online social networks. Although viral spread on large graphs has
been intensively analyzed on classical models such as
Susceptible-Infectious-Recovered, there still exits a deficit of effective
methods in practice to contain epidemic spread once it passes a critical
threshold. Against this backdrop, we explore methods of containing viral spread
in large networks with the focus on sparse random networks. The viral
containment strategy is to partition a large network into small components and
then to ensure the sanity of all messages delivered across different
components. With such a defense mechanism in place, an epidemic spread starting
from any node is limited to only those nodes belonging to the same component as
the initial infection node. We establish both lower and upper bounds on the
costs of inspecting inter-component messages. We further propose
heuristic-based approaches to partition large input graphs into small
components. Finally, we study the performance of our proposed algorithms under
different network topologies and different edge weight models.
