Australasian Journal of Information Systems
ISSN 1449-8618
2017
Shared — curated by The Gufo editorial team
Spectral Methods for Immunization of Large Networks
Muhammad Ahmad*, Juvaria Tariq, Mudassir Shabbir, Imdadullah Khan
Received: 2026-10-23 · Published: 2017-11-06
© 2017 The Author(s) and the original publisher.
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 neighbour 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).
Summary
This paper tackles the problem of stopping an infection from spreading across a network when you can only protect a limited number of nodes in advance. Because an infected node can pass the contagion to its neighbours, a single infection can cascade through an entire graph, and finding the optimal set of nodes to immunize is computationally intractable for all practical epidemic models, even on moderately sized graphs.
The authors propose a new approach based on spectral graph theory, which uses mathematical properties of a graph's structure to judge how relevant or important each node is to the spread of an epidemic. Building on this idea, they design an efficient approximation algorithm for choosing which nodes to immunize, backed by theoretical guarantees showing it runs faster than existing methods. Tests on real-world networks confirm that the algorithm scales well to large graphs and beats current state-of-the-art approaches both in how effectively it contains the epidemic and in its runtime and memory efficiency.
Plain-language summary by The Gufo; the paper is the authors’ own text.
Key findings
- Selecting the optimal set of nodes to immunize against an epidemic is computationally intractable in all practical models, even for moderately sized graphs.
- The paper introduces a spectral graph theory-based method for defining node relevance and importance in the context of epidemic spread.
- The proposed approximation algorithm has theoretical running-time guarantees that make it more efficient than existing solutions in the literature.
- Experiments on real-world graphs show the algorithm scales well to large networks and outperforms state-of-the-art algorithms in both epidemic containment quality and computational efficiency.
