IMPD: Strategic Influence Maximization in the Face of Adversarial Deactivation

TL;DR

In social networks, "Influence Maximization" (IM) is the art of picking the right nodes to start a fire. But what if there’s a firefighter actively dousing your flames? This paper introduces IMPD (Influence Maximization with Deactivation), a bilevel maturity for competitive social environments. By combining Stochastic Programming with Matheuristics, the authors show that ignoring an opponent leads to suboptimal "fragile" seeds, whereas their strategic approach yields a robust spread even under active deactivation.

Problem & Motivation: The Passive Network Fallacy

Most IM research operates on a naive assumption: the network is a static, compliant playground. In reality, competition is the norm. Whether it is a government detaining activists to stop a movement or a corporation offering counter-incentives to block a rival's viral campaign, "deactivation" is a potent force.

The authors identify a critical gap: existing models are either too simple (ignoring the opponent) or too rigid (using deterministic thresholds). Real social influence is stochastic—people have varying levels of resistance (thresholds) that are rarely known in advance. The challenge, therefore, is solving a Max-Min problem hidden inside a Stochastic process.

Methodology: The Bilevel Chess Match

The researchers formalize this as a Stackelberg Game. The Leader (Player 1) moves first to pick a seed set, anticipating that the Follower (Player 2) will then strategically deactivate $E$ nodes to damage the Leader's spread.

1. The Stochastic Core: SAA

To handle the uncertainty of the Linear Threshold (LT) model, where a node activates only if its neighbors' weight exceeds a random threshold $het{a}_i$, the authors employ Sample Average Approximation (SAA). This turns the intractable expected value calculation into a convergent empirical mean over multiple scenarios.

2. The Solution Engines: SAM & TSM

Solving a bilevel integer program is notoriously hard (NP-hard). The authors propose two "Matheuristics"—metaheuristics that call mathematical programs as subroutines:

• SAM (Simulated Annealing based Matheuristic): Uses a cooling schedule to explore seed sets, allowing "worse" moves early on to avoid local optima.
• TSM (Tabu Search based Matheuristic): Uses a short-term memory (Tabu list) and a "long-term memory" to penalize nodes that are over-selected, forcing the algorithm to explore new regions of the network.

Figure 1: The strategic difference between traditional IM (a-b) and the proposed IMPD (c). Note how anticipating deactivation changes the optimal seed choices to preserve spread.

Experiments & Results: Robustness Matters

The authors tested their methods on three network types: Erdős–Rényi (ER), Watts–Strogatz (WS, Small-world), and Barabási–Albert (BA, Scale-free).

Key Performance Identifiers:

• Accuracy: On small networks where optimal solutions could be found via brute force, SAM and TSM hit the objective with near 0% gap.
• Advantage over Heuristics: Traditional heuristics (like choosing high-degree nodes or using "IMM") failed significantly in competitive settings. In cost-based scenarios, the matheuristics outperformed simple strategies by over 30% (Table 7).
• Scalability: TSM was successfully applied to a real-world arXiv co-authorship network, demonstrating that the "promising neighbor" search strategy effectively navigates thousands of nodes.

Figure 2: Performance comparison on synthetic networks. TSM and SAM consistently reach optimal or near-optimal spread values where simple heuristics fail.

Critical Analysis & Conclusion

The real value of this work is the realization that Influence is an Interdiction Problem. By explicitly modeling the follower's reaction, the leader chooses seeds that are not just influential, but "hard to kill."

Limitations: The computational cost remains high. The SAA method requires solving the Lower Level Problem (LLP) repeatedly, which makes real-time deployment on million-node graphs difficult without further decomposition (like Benders decomposition).

Future Outlook: This framework paves the way for "Robust Viral Marketing." Future work could explore cases where the follower’s budget is unknown to the leader, leading to a "Distributionally Robust" influence maximization approach.

Takeaway: If you are planning a viral campaign in a competitive market, don't just find the hubs—find the hubs that your competitor can't afford to block.