CELF is the classic lazy-greedy workhorse for influence maximization: exploit submodularity to skip marginal-gain re-evaluations. But on large graphs its remaining evaluations — each a batch of Monte-Carlo diffusion simulations — are still the bottleneck.

The residual idea

RCELF tracks residual gains: instead of re-simulating a candidate's spread from scratch each round, it maintains and updates residual estimates of how much a candidate can still add given the seeds chosen so far. This tightens the lazy-evaluation pruning substantially while preserving the (1 − 1/e − ε) approximation guarantee of the greedy framework.

Results

Across standard IM benchmarks, RCELF delivers the same seed quality as CELF-style baselines at significantly lower running time, making simulation-based greedy IM viable on much larger graphs. This was my first research project, started during my undergraduate years at SUSTech.