Beyond Max Coverage: Optimizing Budget and Time in Social Influence

TL;DR

While most research focuses on maximizing the "spread" of information, this paper tackles the inverse: How can we minimize the cost and time required to reach a specific audience? By introducing MINTSS and MINTIME, the authors provide the first rigorous approximation guarantees for budget-efficient and time-sensitive viral marketing.

The Missing Dimensions of Viral Marketing

Since the seminal work of Kempe et al. (2003), the "Influence Maximization" (MAXINF) problem has dominated the field. It asks: "Given $k$ seeds, maximize the expected coverage." However, real-world campaigns often ask different questions:

1. MINTSS: "I need to reach 10,000 people. What is the smallest (cheapest) group of influencers I can hire?"
2. MINTIME: "I have a budget for 50 influencers and need to reach 10,000 people. How can I reach them as fast as possible?"

The authors identify that budget, coverage, and time are three orthogonal dimensions. Previous work focused on the first two, leaving the temporal aspect largely unexplored.

Methodology: The Power of Bicriteria and Tricriteria Approximations

Both MINTSS and MINTIME are NP-hard. The authors reformulate these problems by allowing "slack" in some constraints to achieve provable bounds.

1. MINTSS (Minimizing Budget)

The authors treat MINTSS as a Real-valued Submodular Set Cover (RSSC) problem. They prove that a greedy algorithm, which iteratively picks seeds with the highest marginal gain per unit cost, yields a bicriteria approximation.

• The Bound: If the optimal seed set size is $OPT$, the greedy algorithm produces a set of size $\le OPT\cdot (1+\ln (g/ϵ))$, where $ϵ$ is the allowed shortfall from the target coverage $g$.

2. MINTIME (Minimizing Propagation Steps)

MINTIME is significantly harder. The paper shows that even approximating MINTIME within a constant factor is impossible unless P=NP. However, they discover a "sweet spot": if you allow the budget to increase by a logarithmic factor, you can solve the timing problem perfectly.

• The Insight: By applying the GREEDY-MINTSS logic across different time-steps using a linear search ($t=1,2,\dots ,n$), we can find the minimum time needed to hit coverage $g$ with a slightly boosted budget.

Note: The paper utilizes the Independent Cascade (IC) and Linear Threshold (LT) models to simulate propagation, where influence is treated as a stochastic process over a directed graph.

Experimental Results: Where Heuristics Fail

The authors tested their algorithms against common heuristics like PageRank, High-Degree, and PMIA on academic (NetHEPT) and microblogging (Meme) networks.

Key Findings:

• High-Influence Scenarios: In networks with high transition probabilities (e.g., $p=0.1$), the gap between Greedy and simple heuristics is massive. For a target of 1,000 nodes, GREEDY used ~50 seeds, while others needed over 100.
• Time Sensitivity: Seed selection is critical for speed. As shown in the results, relaxing the budget slightly can reduce the propagation time by over 50%.

Note: Graphs in the paper illustrate that while heuristics like PMIA (Maximum Influence Arborescence) perform well in sparse, low-influence settings, they struggle to keep pace with the Greedy approach as the target coverage increases.

Critical Insight & Conclusion

The true value of this paper lies in its hardness results. By proving that we cannot approximate MINTIME without allowing budget or coverage slack, the authors define the theoretical limits of what is possible in social network analysis.

The Takeaway: For practitioners, the message is clear—efficiency in viral marketing isn't just about picking "big" nodes; it’s about understanding the diminishing returns of submodular functions. To reach a goal faster, don't just add more seeds; optimize the set specifically for the time-to-coverage curve.

Limitations: The study assumes static influence probabilities, which may not hold in real-world scenarios where user interest wanes over time. Future work exploring dynamic edge weights would be a natural extension of this framework.