Rumor Blocking through Online Link Deletion: A Fine-Grained Submodular Approach

TL;DR

In the era of viral misinformation, simply "debunking" rumors is often too slow. This paper proposes a surgical approach: Rumor Spread Minimization (RSM) by deleting a limited number of social links. By treating the problem as a Difference of Submodular (DS) functions, the authors developed the Marginal Decrement Strategy (MDS), which achieves significant rumor containment with minimal impact on network structure.

Background: The Cost of Viral Lies

From wildfires to stock market crashes, rumors on platforms like Facebook and Twitter cause real-world damage. While prior research focused on removing "influential nodes" (like banning accounts) or spreading "truth" to compete with lies, these methods are either too expensive or rely on flawed assumptions about human behavior.

The core insight of this study is that links (edges) are the conduits of rumors. If we can identify and "cut" the most critical links in real-time—without destroying the nodes themselves—we can starve a rumor of its reach.

The Challenge: Non-Submodularity

In optimization, submodularity is the "gold standard" because it guarantees that greedy algorithms will work well (the law of diminishing returns). However, the authors prove that RSM is not submodular.

Why? As edges are removed, the network structure changes. Deleting one edge might make a subsequent deletion more or less effective depending on the remaining paths. This "fine-grained" online process breaks the traditional mathematical guarantees.

Methodology: The MDS Strategy and DS Framework

To bypass the non-submodularity trap, the authors employ two brilliant maneuvers:

1. Marginal Decrement Perspective: Instead of calculating total spread repeatedly (expensive), they calculate how much the probability of infection drops for each node when a specific edge is removed.
2. The DS Reformulation: They construct two submodular functions—an upper bound and a lower bound—and show that the original objective is the difference between them.

The MDS Algorithm Architecture

The algorithm iteratively selects edges that maximize the reduction in rumor spread based on a "rumor spread ability" score (${\sigma }_E$).

Figure 1: The Independent Cascade (IC) model used to simulate the probabilistic spread of rumors.

Experimental Battleground

The authors tested MDS against several heavyweights:

• BPM (Bond Percolation Method)
• KED (K-edge Deletion)
• Pagerank and Out-Degree heuristics

Key Findings:

• Efficiency: On the Wikipedia dataset, removing a mere 0.08% of edges slashed the rumor's reach by nearly 50%.
• Bounding Quality: The proposed upper and lower bounds were remarkably close to the actual objective value, validating the theoretical framework.
• Performance: MDS consistently stayed below the "Rumor Spread Value" of competing greedy methods.

Figure 2: Performance comparison showing that MDS (original, upper, and lower) significantly reduces rumor spread compared to the baseline as the number of seed nodes increases.

Deep Insight: Why MDS Wins

Most edge-deletion algorithms are "coarse-grained"—they look at the graph once and pick $K$ edges. MDS is "fine-grained." It updates the influence probabilities of every node in the "ancestor set" of a deleted edge after every single step. This online update ensures that the algorithm doesn't waste its budget on edges that are already neutralized by previous deletions.

Conclusion & Future Outlook

This work shifts the focus of rumor control from account-level censorship to topological intervention. By proving that rumor blocking can be modeled as a Difference of Submodular functions, it opens the door for more sophisticated optimization tools in social media safety.

Limitations: The algorithm assumes we know the network topology and propagation probabilities ($p_{uv}$) perfectly—an assumption that remains challenging in the privacy-focused world of modern social media.