# Combinatorial Trace Method for Network Immunization

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Dec 2019.

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

- [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)
- [PWM2Vec: An Efficient Embedding Approach for Viral Host Specification from Coronavirus Spike Sequences](https://mlsanity.com/paper/2201.02273/) (2022)
- [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)
- [Reads2Vec: Efficient Embedding of Raw High-Throughput Sequencing Reads Data](https://mlsanity.com/paper/2211.08267/) (2022)
- [Efficient Analysis of COVID-19 Clinical Data using Machine Learning Models](https://mlsanity.com/paper/2110.09606/) (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)
- [Locally Weighted Mean Phase Angle (LWMPA) Based Tone Mapping Quality Index (TMQI-3)](https://mlsanity.com/paper/2109.08774/) (2021)

## Abstract (arXiv)

Immunizing a subset of nodes in a network - enabling them to identify and withstand the spread of harmful content - is one of the most effective ways to counter the spread of malicious content. It has applications in network security, public health policy, and social media surveillance. Finding a subset of nodes whose immunization results in the least vulnerability of the network is a computationally challenging task. In this work, we establish a relationship between a widely used network vulnerability measure and the combinatorial properties of networks. Using this relationship and graph summarization techniques, we propose an efficient approximation algorithm to find a set of nodes to immunize. We provide theoretical justifications for the proposed solution and analytical bounds on the runtime of our algorithm. We empirically demonstrate on various real-world networks that the performance of our algorithm is an order of magnitude better than the state of the art solution. We also show that in practice the runtime of our algorithm is significantly lower than that of the best-known solution.