Minimizing the Spread of Contamination by Blocking Links in a Network

Masahiro Kimura, Kazumi Saito, Hiroshi MotodaAAAI 2008

Abstract

Controlling the spread of undesirable information or malicious software in a network often requires isolating parts of the system. While previous research has focused on node removal, blocking specific communication links is often more practical and less disruptive. This paper presents a greedy algorithm that leverages bond percolation theory to efficiently identify the most critical links to block. Evaluated on large-scale real-world datasets, the proposed method demonstrates superior performance, reducing contamination spread significantly more effectively than standard heuristics like betweenness centrality or targeting high-degree hubs.

Introduction

Whether it is a computer virus spreading through a server farm or misinformation proliferating on social media, the ability to "quarantine" network segments is crucial. Traditional strategies often focus on node removal—shutting down a user or a server entirely. However, node removal is a blunt instrument. In many scenarios, it is more feasible to block specific links (e.g., closing a network port or filtering a specific communication channel) to preserve as much network functionality as possible.

The challenge lies in the "combinatorial explosion" of choosing which $k$ links to block out of millions. This paper formalizes the contamination minimization problem: finding the optimal set of links to sever to minimize the expected number of infected nodes under the Independent Cascade (IC) model.

Methods

The researchers developed a two-pronged approach to solve this optimization problem:

  1. Greedy Strategy: The algorithm iteratively selects the single link whose removal most reduces the "contamination degree" (the average number of nodes eventually infected).
  2. Bond Percolation Estimation: To avoid the prohibitive cost of running thousands of simulations for every potential link removal, the authors utilize bond percolation from statistical physics. By treating links as "occupied" or "vacant" based on propagation probability $p$ and using Strongly Connected Component (SCC) decomposition, they can rapidly estimate the impact of removing any given link.

The method was tested on two large-scale Japanese datasets: a Blog Network (12,047 nodes, 79,920 links) and a Wikipedia Network (9,481 nodes, 245,044 links).

Results and Discussion

The proposed method consistently outperformed traditional heuristics. On the Blog network, blocking just 100 links (0.13% of the total) reduced the expected contamination area by 41%, whereas the standard "Betweenness" heuristic achieved only a 30% reduction.

Contamination reduction on the Blog network: Proposed method vs. Betweenness centrality.

A key finding is the "Hub Fallacy": while targeting high-degree nodes is effective for node removal, blocking individual links from these hubs is surprisingly ineffective. If a hub has many outgoing links, cutting a small fraction of them does little to stop the spread. This is evidenced by the massive performance gap between the proposed method and out-degree targeting.

Comparison of the proposed method (k=100) against out-degree and random link removal strategies.

As shown in the figure above, to match the contamination reduction achieved by the proposed method with only 100 links, the out-degree and random methods would need to block over 10,000 links—making the proposed strategy approximately 100 times more efficient in this context.

Conclusion

This research demonstrates that link-blocking is a fundamental and highly effective way to control network contamination. By accounting for the dynamics of spread rather than just network structure, the proposed bond-percolation-based greedy algorithm identifies critical links that structural heuristics miss. Future work includes scaling the method for even larger dynamic networks and testing its robustness across different diffusion models.

Summary updated

BibTeX
@inproceedings{kimura2008minimizing,
  author = {Masahiro Kimura and Kazumi Saito and Hiroshi Motoda},
  title = {{Minimizing the Spread of Contamination by Blocking Links in a Network}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2008},
}
Figure