# Scalable Approximation Algorithm for Network Immunization

arXiv: https://arxiv.org/abs/1711.00784 · HTML: https://mlsanity.com/paper/1711.00784/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Nov 2017.

## Built on by (most cited first, 8 of 8)

- [Spike2Vec: An Efficient and Scalable Embedding Approach for COVID-19 Spike Sequences](https://mlsanity.com/paper/2109.05019/) (2021)
- [A k-mer Based Approach for SARS-CoV-2 Variant Identification](https://mlsanity.com/paper/2108.03465/) (2021)
- [Efficient Approximate Kernel Based Spike Sequence Classification](https://mlsanity.com/paper/2209.04952/) (2022)
- [Effective and scalable clustering of SARS-CoV-2 sequences](https://mlsanity.com/paper/2108.08143/) (2021)
- [Robust Representation and Efficient Feature Selection Allows for Effective Clustering of SARS-CoV-2 Variants](https://mlsanity.com/paper/2110.09622/) (2021)
- [Computing Graph Descriptors on Edge Streams](https://mlsanity.com/paper/2109.01494/) (2021)
- [Efficient Classification of SARS-CoV-2 Spike Sequences Using Federated Learning](https://mlsanity.com/paper/2302.08688/) (2023)
- [Characterizing SARS-CoV-2 Spike Sequences Based on Geographical Location](https://mlsanity.com/paper/2110.00809/) (2021)

## Abstract (arXiv)

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.