DDSE: Breaking the Efficiency Bottleneck in Social Influence Maximization

TL;DR

The Influence Maximization (IM) problem—finding the $K$ most influential nodes in a network—has long been a tug-of-war between the accuracy of Greedy Algorithms and the speed of Heuristics. DDSE (Degree-Descending Search Evolution) ends this conflict by utilizing an evolutionary framework that replaces time-consuming Monte Carlo simulations with a smart estimation function (EDV) and a structural search strategy (DDS), reaching speeds 100,000 times faster than state-of-the-art greedy baselines.

Context: The #P-Hard Curse

Since Kempe et al. (2003) formalized IM as a discrete optimization problem, the "Gold Standard" has been the Greedy Algorithm. However, Greedy is a victim of its own success. To evaluate the "influence" of a node set, it must simulate the diffusion process thousands of times. Even "Lazy Forward" optimizations like CELF struggle with large-scale graphs containing millions of edges, as the core estimation remains a #P-hard problem.

Methodology: The DDSE Breakthrough

The authors argue that we don't need exact influence values during the search process; we need relative rankings that are computationally cheap.

1. The Proxy: Expected Diffusion Value (EDV)

Instead of simulating an entire cascade, DDSE uses the EDV function. This metric calculates the expected number of direct neighbors activated by a seed set $S$: $EDV(S)=k+{\sum }_{i\in N_S^{(1)}\setminus S}(1-(1-p{)}^{au(i)})$ This formula allows the algorithm to evaluate a candidate solution instantly, removing the need for Monte Carlo iterations.

2. The Strategy: Degree-Descending Search (DDS)

While "Degree Centrality" (picking the highest-degree nodes) is a common heuristic, it is often suboptimal because influential nodes tend to cluster. DDSE introduces DDS, which uses degree as a priority but injects randomness. Instead of picking the absolute top node, it selects randomly from an "up-bound" range of high-degree nodes. This provides the necessary exploration for the evolutionary algorithm.

3. Evolutionary Framework

The DDSE architecture integrates these concepts into a classic Evolutionary Algorithm (EA) loop:

• Initialization: Seeding the population using DDS-based high-degree nodes.
• Mutation & Crossover: Using DDS to swap nodes, ensuring the search stays within the "high-potential" structural areas of the graph.
• Local Search: A final neighborhood-based optimization to fine-tune the seed set.

Experiments & Performance

The authors tested DDSE on arXiv co-authorship datasets (NetScience, NetGRQC, NetHEP).

1. Speed Comparison

The most striking result is the runtime. While CELF takes hundreds or thousands of seconds to find 50 seeds, DDSE finishes in milliseconds.

• Efficiency Gain: 5 orders of magnitude faster than CELF.
• Versus Other EAs: 10x faster than SAEDV (Simulated Annealing).

2. Accuracy Comparison

Despite the speed, DDSE doesn't sacrifice performance. In terms of "Influence Spread" (the number of people reached), DDSE curves are nearly identical to CELF and significantly higher than standard PageRank or Degree heuristics.

Critical Insight & Practical Value

The Success of DDSE lies in its Inductive Bias. By baking the "Degree-Descending" assumption into the evolutionary operators, the algorithm doesn't waste time exploring low-degree nodes that are mathematically unlikely to be optimal seeds.

Limitations:

• The EDV is a local estimator. In networks with extremely long, thin "chains" of influence, a purely local estimate might underperform global simulation-based methods.
• The algorithm’s performance depends on the tuning of the "DDS range," which might vary across different topological structures (e.g., scale-free vs. random networks).

Conclusion

DDSE represents a shift from "computationally intensive precision" to "structurally aware estimation." For real-time viral marketing or social sensing where decisions must be made in seconds on large-graphs, DDSE provides a robust, scalable alternative to the aging greedy paradigm.