MOEA/D-ADACO: Balancing Cost and Control in Social Network Rumor Suppression

TL;DR

Controlling the spread of "pollutants" (rumors or malware) in social networks is typically viewed as a "top-K node" selection problem. This paper argues that the fixed-$K$ approach is flawed. Instead, it proposes a biobjective model that simultaneously maximizes suppression effect and minimizes control cost. To solve this, the authors developed MOEA/D-ADACO, an Ant Colony Optimization variant that adaptively decides how many and which nodes to block, outperforming traditional greedy and genetic algorithms in both quality and speed.

Problem & Motivation: The Hidden Cost of "Blocking"

Most existing literature on influence minimization focuses solely on the "Effect": How many nodes can we save by blocking a set $S$?

However, there are two major blind spots in this SOTA logic:

1. Fixed Dimension: We don't actually know if blocking 10 nodes or 100 nodes is "best."
2. Operational Cost: In a professional social network, blocking a high-degree node (like a key influencer) isn't free—it damages the network's service quality and connectivity.

The authors' insight is to treat this as a Multiobjective Optimization Problem (MOP). They use Expected Diffusion Value (EDV) to measure effect and PageRank (PR) values to quantify the "cost" of blocking specific nodes.

Methodology: Ant Colony meets Decomposition

The core of the paper is MOEA/D-ADACO. It builds on the MOEA/D (Decomposition) framework, which breaks a complex biobjective front into a set of single-objective subproblems.

1. Dual-Pheromone Mechanism

Unlike standard ACO, this algorithm uses two types of "chemical trails":

• $\sigma$ (Dimension Pheromone): Guides the ants on the optimal number of nodes to select.
• $au$ (Node Pheromone): Guides the ants on which specific nodes are the most "cost-effective" for suppression.

2. Adaptive Dimension Selection

Before an ant starts picking nodes, it "decides" on a dimension size $d$ based on the strength of the $\sigma$ pheromone. This allows the population to explore solutions of different sizes simultaneously, eventually converging on the most efficient set sizes for the Pareto Front.

Experiments & Results

The authors tested their model on six real-world datasets, including Facebook, Google+, and Twitter.

SOTA Comparison

Compared to the classic Hill-Climbing (HC) greedy algorithm and NSGA-II/III, the proposed method found much more diverse and efficient trade-offs.

• Effectiveness: MOEA/D-ADACO achieved higher Hypervolume (HV) scores, meaning its Pareto Front was closer to the theoretical optimum.
• Efficiency: Because ACO avoids the heavy computational overhead of "Nondominated Sorting" (the bottleneck of NSGA algorithms), MOEA/D-ADACO was significantly faster. In the Deezer dataset, it ran 21 times faster than NSGA-III.

Visual Evidence of Convergence

The convergence curves show that while NSGA-II often struggles to improve after initial iterations in large-scale networks, MOEA/D-ADACO continues to refine the front, thanks to the collective intelligence of the ant groups sharing pheromones.

Critical Insight: Why it Works

The success of this work lies in its Inductive Bias. Social networks are naturally discrete and combinatorial. Ant Colony Optimization is inherently designed for discrete path-finding. By adding the adaptive dimension selection, the authors transformed the "fixed-set" constraint into an optimization variable, allowing the algorithm to discover that "less is often more"—blocking a few strategic low-cost nodes can be more efficient than blocking many high-cost ones.

Conclusion

The paper effectively demonstrates that pollutant control in social networks is not just about power, but about efficiency. MOEA/D-ADACO provides a robust, fast, and flexible tool for administrators to manage network health without destroying the network's value.

Limitations: The model assumes a static network. In real-world scenarios, social ties evolve, and a dynamic version of this ACO model would be the next logical step for researchers in this field.