Beyond Connectivity: Master Time-Constrained Influence Maximization with ISP

TL;DR

Social influence isn't just about who you know, but when they react. This paper addresses the "Time-Constrained Influence Maximization" problem—finding the best $K$ seeds to maximize spread before a hard deadline. By introducing the Influence Spreading Path (ISP) and the MISP algorithm, the authors provide a framework that is $1000imes$ faster than standard simulations and capable of handling massive graphs like LiveJournal with 68 million edges on a single machine.

The "Time Decay" Problem in Viral Marketing

Most Influence Maximization (IM) research treats information spread as an instantaneous or step-wise process. However, in the real world, "Word-of-Mouth" has a latency. If you are promoting a concert happening in three days, an influential user who takes five days to tell their friends is essentially useless to your campaign.

Existing SOTA methods like PMIA fail here because they don't account for varying time delays ($P_{lat}$). Furthermore, the standard Monte Carlo (MC) greedy approach is too slow for production use, as simulating millions of cascades is a computational nightmare.

Methodology: The Influence Spreading Path (ISP)

The core innovation is the transformation of a social network into a logically augmented multigraph. If user $A$ can influence $B$ with different probabilities at different time lags, these are represented as multiple edges between the nodes.

The ISP Algorithm

Instead of full simulation, the algorithm identifies Influence Spreading Paths—simple paths starting from a seed set with a length (total delay) $\le T$ and a probability $\ge heta$.

• ISP: Recalculates paths for every potential seed candidate from scratch.
• MISP (Marginal Discount ISP): A massive optimization. It calculates the influence of single nodes once and then uses a discount function to estimate how much a new candidate adds to the existing seed set. This makes the running time almost constant regarding the number of seeds $K$.

Scalability and Performance

The experiments prove that ignoring time constraints leads to poor results. Seed sets chosen for a deadline of $T=1$ share only about 20-40% of nodes with seed sets chosen for $T=10$.

As shown in the charts, ISP and MISP track the "Gold Standard" (Monte Carlo) almost perfectly in terms of influence spread but do so in a fraction of the time. While PMIA and other arborescence-based methods crashed or ran out of memory on the LiveJournal dataset, MISP handled it with ease.

Key Breakthroughs:

1. Memory Efficiency: Unlike PMIA, which stores local arborescences for every node, MISP's memory footprint is dominated only by the social graph itself.
2. Parallelization: Since path calculations for individual nodes are independent, the workload can be distributed across multi-core CPUs with linear speedup.

Critical Insight

The brilliance of this work lies in the Marginal Discount formula. By approximating the overlap of influence between $S$ and a new node $v$ using the activation probabilities of $v$'s neighbors, the authors bypass the #P-hard problem of exact calculation without losing the theoretical guarantees of submodularity ($1-1/e$ approximation).

Conclusion & Future Work

The Influence Spreading Path framework bridges the gap between theoretical social network analysis and real-time marketing requirements. While the requirement to tune the threshold $heta$ is a minor hurdle, the gain in scalability is transformative. Future research could look into automating $heta$ selection or applying these "latency-aware" paths to the spread of misinformation, where the "golden hour" for debunking is a strictly time-constrained problem.