Classic influence maximization (IM) picks k seed users to maximize spread. Real campaigns are messier: budgets are split across communities, items, or time slots, and seeds must respect per-group quotas. Many of these variants share one mathematical structure — the feasible seed sets form a matroid.

A unified framework

This work designs efficient and effective algorithms for the whole family of IM problems under a general matroid constraint, instead of a bespoke method per variant. The framework couples reverse-reachable-set sampling with matroid-aware greedy and local-search selection, retaining approximation guarantees while keeping sample complexity manageable on large graphs.

Results

On billion-edge social networks, the algorithms deliver near-state-of-the-art influence spread across multiple constraint types — partition budgets, multi-campaign coordination, and beyond — at a fraction of the running time of specialized baselines, making constrained IM practical at production scale.