Spectral Methods for Immunization of Large Networks
- 1Lahore University of Management Sciences
- 2Information Technology University
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).
Related
- Modelling Fourier filtering wavefront sensors for power spectral density-based methods: The AOPERA tool
- Transverse Numerical Approach Combining Fluid-Structure Interaction and Model Reduction Methods of a Modular Thermal Energy Storage System to Improve the Energy Efficiency of District Heating Networks
- Spectral theory of large data with power-law latent features
- Spectral networks, finite webs, and the T3 cubic differential
- Spectral theory for dynamical large deviations in non-Markov self-interacting processes
BibTeX
@article{ahmad2026spectral,
title = {{Spectral Methods for Immunization of Large Networks}},
author = {Muhammad Ahmad and Juvaria Tariq and Mudassir Shabbir and Imdadullah Khan},
journal = {Journal of the Association for Information Systems},
year = {2026},
month = aug,
doi = {10.3127/ajis.v21i0.1563},
url = {https://aisel.aisnet.org/ajis/vol21/iss1/51},
note = {CC BY-NC-ND},
}
RIS
TY - JOUR
TI - Spectral Methods for Immunization of Large Networks
AU - Muhammad Ahmad
AU - Juvaria Tariq
AU - Mudassir Shabbir
AU - Imdadullah Khan
PY - 2026
DA - 2026/08/19
JO - Journal of the Association for Information Systems
DO - 10.3127/ajis.v21i0.1563
UR - https://aisel.aisnet.org/ajis/vol21/iss1/51
AB - 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).
SN - 1536-9323
ER -