Temporal multi-path marginal coverage for finite-horizon influence maximization

Abstract

Influence maximization seeks a limited seed set that maximizes diffusion spread. Topology-based rankings are efficient but often ignore finite-horizon dynamics and seed-set redundancy, whereas simulation-assisted greedy methods can be computationally expensive. To balance effectiveness, efficiency, and interpretability, this paper proposes temporal multi-path marginal coverage (TMPMC), a deterministic surrogate for finite-horizon susceptible–infected–recovered (SIR) influence maximization. TMPMC estimates source–target probabilities through temporal path propagation, global noisy-OR aggregation over retained paths, and target-level marginal coverage. Unlike IC- or LT-oriented path approximations, TMPMC accounts for repeated infection attempts, recovery risk, feasible arrival times, and a finite propagation horizon. Its monotonicity and submodularity results apply to the surrogate objective, not to the exact stochastic SIR expectation. Across 1,000 common-random-number SIR possible worlds, TMPMC obtains a higher paired AUC than the strongest ranking or heuristic reference on all twelve networks, with an average relative gain of 6.39%. Comparisons with the same-model CELF++ reference, finite-depth IC-based cross-model RR references, and adapted learning-based references reveal a network-dependent effectiveness–efficiency trade-off rather than uniform dominance. High-precision diagnostics show strong within-budget and within-base candidate ranking fidelity, while diffusion-parameter, propagation-horizon, and unified single-thread time–memory analyses characterize robustness and computational scaling. These results support TMPMC as a training-free and interpretable surrogate when finite-horizon SIR-aware seed ranking is required.