[IEEE TNSE] Two-Phase Information Diffusion: Beyond the Limits of Single-Shot Viral Marketing

TL;DR

Optimization of information spread in social networks has historically been a "one-shot" game. This paper shatters that convention by proving that splitting your budget into two phases—activating some seeds, watching the ripple effect, and then dropping the remaining seeds—is mathematically and practically superior to traditional single-phase activation.

Problem & Motivation: The Uncertainty of One-Shot

In the classic Influence Maximization (IM) problem, we select $k$ seed nodes to maximize the expected number of influenced nodes under models like Independent Cascade (IC). However, the IC model is stochastic; even an optimal set of seeds can result in a "dud" cascade if the edge sampling (the "Live Graph") is unfavorable.

Existing methods (Prior Work) are largely single-phase, meaning they commit their entire budget at $t=0$. The authors argue this is inefficient. If you can observe who actually got influenced in the first few steps, you can place your remaining seeds far more effectively to cover "cold" parts of the network or avoid redundant overlaps.

Methodology: The Two-Phase Calculus

The core innovation lies in the formulation of the two-phase objective function $f(S_1)$. It isn't just about the first set $S_1$; it's the expected value of the final spread, assuming an optimal second set $S_2$ will be chosen based on the observation $Y$ at time $d$.

Key Mathematical Insight

While the single-phase objective function $\sigma (S)$ is submodular (exhibiting diminishing returns), the two-phase function $f(S_1)$ is not necessarily submodular. This makes the optimization harder. The authors prove that $f(S_1)$ is, however, subadditive, and they propose a "Farsighted" approach that anticipates the second phase's potential.

The FACE Algorithm

To handle the complexity and non-submodularity, the authors employ the Fully Adaptive Cross Entropy (FACE) method. Unlike greedy algorithms that can get stuck, FACE iteratively updates a probability distribution over the nodes, converging on a set that maximizes the two-phase spread while simultaneously optimizing the split between $k_1$ and $k_2$.

Fig 1. A motivating example showing how two-phase diffusion avoids redundancy compared to single-phase activation.

Experiments & Results: The "1:2" Rule

The authors tested their framework on the NetHEPT dataset (15k nodes) and the Les Miserables network.

1. The Performance Leap

Two-phase diffusion consistently outperformed single-phase diffusion. In the Weighted Cascade (WC) model, the gain was significant (~7-10%).

2. The Optimal Budget Split

One of the most practical findings is the budget allocation. If you have no strict deadline, you shouldn't split the budget 50/50. Instead:

• Allocate ~1/3 to Phase 1: Just enough to "probe" the network and see how the information flows.
• Allocate ~2/3 to Phase 2: Use the majority of your resources to target segments the first wave missed.

Table 1. Improvement of two-phase over single-phase across different models ($k=300$).

3. The Temporal Trade-off

If time is money (modeled by a decay function ${\delta }^t$), the advantage of the two-phase approach diminishes. If the information loses value quickly ($\delta <0.85$), the delay of waiting for Phase 2 outweighs the benefit of better node selection.

Fig 2. Optimal $k_1$ vs. Delay $d$: Most strategies favor a short delay with high $k_1$ when time decay is present.

Critical Insight & Conclusion

This paper provides a rigorous transition from static IM to adaptive IM.

• Takeaway: Myopic algorithms (those that don't "look ahead" but just act optimally at the moment) actually perform surprisingly well compared to complex farsighted ones, making two-phase strategies viable for massive networks.
• Limitations: The model assumes the "marketer" can perfectly observe who is influenced in real-time. In reality, there is a "tracking gap" that might degrade performance.
• Future Work: The logical next step is Continuous-time Diffusion or N-phase optimization, where the budget is trickled into the network dynamically.

Ultimately, this research suggests that in the world of viral marketing, patience is not just a virtue—it is a measurable ROI.