Breaking the 1-1/e Barrier: Superior Influence Maximization via Semidefinite Programming

TL;DR

Most influence maximization research has been stuck at the $1-1/e\approx 0.632$ approximation ratio for decades due to a reliance on submodular greedy algorithms. This paper challenges that status quo by introducing a time-sensitive model and an SDP-based (Semidefinite Programming) algorithm that pushes the approximation ratio to 0.857 for online social networks.

Context: Why IC and LT Models are Failing

For years, the Independent Cascade (IC) and Linear Threshold (LT) models have governed the study of viral marketing. However, these models assume that influence can ripple through a network forever. In reality, modern social media topics are "flashes in the pan"—they vanish as quickly as they appear.

The authors argue that two factors are missing from traditional models:

1. Time Sensitivity: Influence doesn't propagate endlessly; it dies out after a few hops.
2. Influence Transitivity: Calculating influence based on shortest paths and specific hop limits ($M$) and probability thresholds ($heta$) is more reflective of real-world "active phases" of information.

Methodology: From Greedy to SDP

The core innovation lies in treating Influence Maximization not as a submodular greedy selection problem, but as a Quadratic Integer Program.

1. The Model Transformation

The influence factor $p(u,v)$ is calculated based on node degrees and historical action logs. By introducing a hop limit $M$, the authors turn the complex cascade process into a one-step operation after calculating transitive influence factors.

2. Semidefinite Relaxation

The problem is relaxed into a vector space where each node $u_i$ is represented by a vector $v_i$ on a unit sphere. The optimization goal becomes: $\max \sum p_{ij}\frac{(1+v_0\cdot v_i-v_0\cdot v_j-v_i\cdot v_j)}{4}$ Using a hyperplane rounding technique, the algorithm separates nodes into "seeds" and "non-seeds" with a much higher theoretical guarantee than simple greedy approaches.

Experimental Validation

Using the Netscience social network dataset, the authors compared their SDP-based methods (Alg 1 and Alg 2) against Degree-Greedy and Random baselines.

Key Findings:

• Efficiency: Introducing thresholds $M=6$ and $heta=0.1$ reduced running time from 53.76s to 4.49s for 400-node graphs—a 12x speedup with minimal performance loss.
• Superiority: In the unconstrained seed set case, Algorithm 1 consistently yielded influence spreads nearly 35-40% higher than the Degree-Greedy baseline.
• Size Constraints: In cases where seed size was restricted (e.g., 30% or 40% of the network), the advantage of SDP remained, though it narrowed as the size constraint became stricter.

Critical Insight: The "Lasserre" Advantage

For the constrained case, the paper utilizes the Lasserre SDP hierarchy. This is a powerful (though computationally heavy) mathematical tool that provides a computer-assisted proof: when the seed-to-node ratio $\delta$ is between 0.36 and 0.64, the approximation ratio is guaranteed to be higher than $1-1/e$. This effectively mathematically "proves" that submodularity is not the only way to achieve high-quality seed sets.

Conclusion and Future Outlook

This paper is a significant departure from the "greedy-centric" research of the mid-2000s. By incorporating transitivity constraints and higher-order optimization (SDP), it provides a blueprint for more accurate viral marketing in the era of short-lived social media trends.

The primary limitation identified is the computational complexity of SDP for massive graphs. Future work likely involves approximating these SDP solutions using spectral methods or distributed optimization to scale to millions of nodes.