DGS: Accelerating Target Set Selection with Greedy Deprecation

TL;DR

Researchers have developed the Deprecation based Greedy Strategy (DGS), a hybrid approach that combines the speed of simple heuristics with the precision of greedy optimization. By identifying and "deprecating" (removing) weak candidates from a pre-sorted list, DGS achieves influence results nearly identical to the industry-standard CELF algorithm but runs up to 98% faster on large-scale social datasets.

Context: The Efficiency-Accuracy Trade-off

In the world of viral marketing and Social Network Analysis (SNA), "Target Set Selection" (TSS) is the art of finding the $k$ most influential people to start a word-of-mouth campaign.

Mathematically, this is an NP-hard problem. We have two traditional choices:

1. Greedy Algorithms: Very accurate (approximating 63% of optimal), but painfully slow for "Big Data" networks.
2. Heuristics: Extremely fast (based on degree or centralities), but often "dumb" because they ignore how influence overlaps between nodes.

DGS proposes a third way: Start with a fast heuristic, then use greedy logic to prune the mistakes.

The "Why": Leveraging Sub-modularity

The core insight of the paper rests on Sub-modularity—the law of diminishing returns. In influence spread, the "value" of adding a person to your target set decreases as the set gets larger.

The authors realized that instead of searching the whole network to find the best node (the standard greedy way), they could look at a top-list of nodes and ask: "Is there anyone further down this list who actually performs better than this current candidate?" If a node is outperformed by at least $k$ nodes behind it, that node is clearly "wrongly positioned" and can be safely discarded.

Methodology: The Estimation-Marking Loop

The DGS algorithm operates in two repeating stages:

1. Estimation: It simulates the actual influence of the current candidate list using Monte Carlo simulations to find the "Marginal Contribution" of each node.
2. Marking: It identifies "Deprecation" candidates. If a node $v_i$ has a lower marginal contribution than a later node $v_j$ in the list, a relation $R$ is established.
3. Deprecation: Any node that is "beaten" by $k$ or more successors is removed from the list entirely.

Figure 1: The Iterative Flow of the Deprecation based Greedy Strategy.

Experimental Battleground: Big Data Results

The authors tested DGS across diverse networks, from Twitter followers to US Airport connections.

Performance Gains

On the Twitter dataset, applying DGS to a standard "Degree Discount" heuristic increased the total nodes influenced by 28.2%. In weighted networks like USAirport, DGS matched the performance of the gold-standard CELF algorithm perfectly.

The Speed Advantage

The real "aha!" moment is the execution time. In the EUEmail network, CELF took over 28 million milliseconds. DGS finished the task in just 0.4 million milliseconds.

Figure 2: Execution time (log scale) showing DGS (Green/Red/Cyan) significantly outperforming CELF (Yellow).

Critical Insight & Summary

The brilliance of DGS is its convergence speed. While a standard greedy algorithm must run at least $k$ iterations (where $k$ is the target set size), DGS usually converges in fewer than 10 iterations, regardless of $k$. This is because it can prune dozens of suboptimal nodes in a single "Marking" pass.

Takeaway for Practitioners: If you are working with massive graphs where standard greedy algorithms hang, don't settle for raw heuristics. A deprecation-based pruning layer can give you greedy-level accuracy at heuristic-level speeds.

Reference: Kundu, S., & Pal, S. K. (2015). Deprecation based greedy strategy for target set selection in large scale social networks. Information Sciences.