Source-linked AI summary
StaticGreedy: solving the scalability-accuracy dilemma in influence maximization
Suqi Cheng, Huawei Shen, Junming Huang, Guoqing Zhang, Xueqi Cheng
TL;DR
Influence maximization must balance guaranteed accuracy with scalability, but existing methods divide these goals between expensive greedy algorithms and less reliable heuristics. This paper identifies unguaranteed submodularity as the key issue, proposes StaticGreedy with reused Monte Carlo results, and reports major computational reductions without accuracy loss plus further dynamic speedups.
Problem
Existing influence-maximization algorithms face a scalability-accuracy dilemma: greedy methods require expensive computation, while scalable heuristics have unguaranteed accuracy.
Method
StaticGreedy strictly guarantees submodularity by reusing Monte Carlo simulation results throughout greedy seed selection, with a dynamic strategy updating candidate marginal gains.
Results
The algorithm reduces computational expense by two orders of magnitude without loss of accuracy, while dynamic updates make it 2−7 times faster than CELF-optimized StaticGreedy.
Takeaways & Limitations
Strictly guaranteed submodularity and monotonicity let the static greedy algorithm achieve the same accuracy as state-of-the-art greedy algorithms with dramatically fewer Monte Carlo simulations.
Takeaways & Limitations
The paper omits details for generalizing StaticGreedy to the linear threshold model because of space limitations.
Abstract
from arXiv · showhide
Influence maximization, defined as a problem of finding a set of seed nodes to trigger a maximized spread of influence, is crucial to viral marketing on social networks. For practical viral marketing on large scale social networks, it is required that influence maximization algorithms should have both guaranteed accuracy and high scalability. However, existing algorithms suffer a scalability-accuracy dilemma: conventional greedy algorithms guarantee the accuracy with expensive computation, while the scalable heuristic algorithms suffer from unstable accuracy. In this paper, we focus on solving this scalability-accuracy dilemma. We point out that the essential reason of the dilemma is the surprising fact that the submodularity, a key requirement of the objective function for a greedy algorithm to approximate the optimum, is not guaranteed in all conventional greedy algorithms in the literature of influence maximization. Therefore a greedy algorithm has to afford a huge number of Monte Carlo simulations to reduce the pain caused by unguaranteed submodularity. Motivated by this critical finding, we propose a static greedy algorithm, named StaticGreedy, to strictly guarantee the submodularity of influence spread function during the seed selection process. The proposed algorithm makes the computational expense dramatically reduced by two orders of magnitude without loss of accuracy. Moreover, we propose a dynamical update strategy which can speed up the StaticGreedy algorithm by 2-7 times on large scale social networks.
1. INTRODUCTION
Influence maximization seeks effective seed sets for viral marketing, but existing methods struggle to combine scalable computation with guaranteed accuracy. StaticGreedy addresses this dilemma by strictly preserving submodularity and reusing simulation results, while dynamic updates further accelerate selection.
- Motivation: Influence maximization selects a fixed-size seed set that maximizes influence spread, a fundamental problem for viral marketing.The problem is NP-hard, and greedy methods approximate the optimum using influence-spread estimates.
- Motivation: Existing algorithms face a scalability-accuracy dilemma: Monte Carlo-based greedy methods are computationally expensive, whereas heuristics offer scalability with unguaranteed accuracy.Monte Carlo reductions remain limited because many simulations are still needed for each estimation.
- Key insight: The paper identifies unguaranteed submodularity in existing greedy algorithms as the cause of their expensive computation.Large numbers of Monte Carlo simulations are used to reduce the resulting risk and approximately guarantee submodularity.
- Proposed method: StaticGreedy strictly guarantees submodularity by reusing Monte Carlo simulation results throughout greedy seed selection.The method reduces computational expense by two orders of magnitude without loss of accuracy.
2. RELATED WORK
Related work improves influence-maximization scalability through optimized greedy procedures, heuristics, and alternative optimization frameworks. These approaches reduce computation in different ways, but the reviewed greedy methods remain inefficient because influence estimation still requires many Monte Carlo simulations.
- Greedy algorithms: CELF exploits submodularity to reduce the number of influence-spread evaluations while preserving greedy selection accuracy.NewGreedy reuses Monte Carlo results for all candidate nodes in an iteration, and Mixed-Greedy combines CELF and NewGreedy.
- Greedy algorithms: Improved greedy algorithms remain inefficient because they require too many Monte Carlo simulations for influence-spread estimation.This limitation motivates heuristic methods for the independent cascade model.
- Heuristics: Degree-discount heuristics improve scalability by considering only a node’s direct influence on one-hop neighbors.The cited approach significantly decreases running time by simplifying influence estimation.
- Beyond greedy methods: Alternative approaches include simulated annealing, Shapley-value-based methods, and edge removal to accelerate influence computation.These methods move beyond the standard greedy framework.
- Competitive settings: Competitive influence-maximization studies extend diffusion models to multiple competing innovations, distance-based propagation, and wave propagation.Some work minimizes the number of seed nodes under a specified competition goal.
3. STATIC GREEDY ALGORITHM
StaticGreedy reuses a fixed set of Monte Carlo snapshots to preserve submodularity during greedy selection, addressing the scalability-accuracy dilemma. Experiments report comparable or better accuracy with far fewer simulations and faster execution than conventional greedy methods.
- Problem: Influence spread I(S) is the expected number of eventually activated nodes, maximized under a seed-set size constraint k.The paper studies the independent cascade model, where edge activation probabilities determine diffusion.
- The submodularity property: Different Monte Carlo snapshots across greedy iterations can violate submodularity and monotonicity by changing estimated marginal gains.The paper gives an example where a candidate’s marginal gain increases in a later iteration because different snapshots are used.
- StaticGreedy: StaticGreedy reuses Monte Carlo results throughout greedy selection, strictly guaranteeing submodularity and reducing computational expense by two orders of magnitude without loss of accuracy.Unlike conventional methods, it uses static snapshots rather than repeatedly estimating influence with independent simulations.
- Accuracy: 100 snapshots can usually yield a small approximation error ǫ, whereas conventional greedy methods typically require about 10,000 simulations to support submodularity guarantees.Both approaches provide a (1 −1/e −ǫ)-approximation, but ǫ has different sources in the two methods.
- Accuracy: StaticGreedy consistently approaches ground truth quickly and outperforms CELFGreedy in accuracy for both UIC and WIC models.The reported advantage remains when R is small, such as R = 100; NewGreedy behaves differently across the two models.
- Scalability: StaticGreedy requires smaller Rmin values than CELFGreedy and runs faster than the compared greedy algorithms.NewGreedy can have similarly small Rmin yet remain slower because it performs simulations in every iteration, whereas StaticGreedy simulates only initially.
- Scalability: The dynamic update strategy further decreases StaticGreedy’s running time by updating candidate marginal gains using static simulation results.This improved version is introduced after the basic StaticGreedy runtime analysis.
- Discussion: The independent-cascade idea can be generalized to the linear-threshold model, but details are omitted because of space limitations.The paper does not provide the corresponding construction or evaluation here.
4. SPEEDING UP THE STATICGREEDY
StaticGreedyDU accelerates StaticGreedy by dynamically updating candidate marginal gains using reusable Monte Carlo snapshots, avoiding recomputation from scratch.
- Dynamic update strategy: StaticGreedyDU dynamically updates candidate marginal gains after each selected seed by discounting overlap with that seed.The update uses shared influence between the selected node and other candidates.
- Algorithm: The algorithm initializes marginal gains from reachability sets across R snapshots, then repeatedly selects the candidate with maximum gain.The procedure records reachable nodes for every candidate before the seed-selection loop.
- Dynamic update strategy: StaticGreedyDU reuses static snapshots to maintain marginal gains incrementally throughout greedy selection.Reachability sets are updated by deleting nodes already covered by the selected seed.
- Complexity: For undirected graphs, StaticGreedyDU uses O(R′n) space and O(R′m + kn) total time complexity.The stated complexity includes snapshot generation, initial marginal-gain calculation, and incremental updates.
- Complexity: For directed graphs, its total time complexity is O(R′m + R′ntT + R′ntU + kR′nT nU), with reachability factors usually small in sparse networks.The directed-graph analysis also gives space complexity O(R′nnT + R′nnU).
5. EXPERIMENT
The experiment evaluates StaticGreedy against existing algorithms on six real-world networks, focusing on accuracy and scalability. The networks comprise scientific collaboration and online social networks.
- The experiments compare StaticGreedy with existing algorithms on two dimensions: accuracy in finding influential seed nodes and scalability.These objectives frame the evaluation of both solution quality and computational practicality.
- Datasets: Six real-world networks are used to demonstrate the performance of the algorithms through comparisons with existing methods.
- Datasets: The benchmark includes three undirected scientific collaboration networks and three directed online social networks.
- Datasets: The scientific collaboration networks are NetHEPT, NetPHY, and DBLP, with DBLP described as much larger than the other two.
- Datasets: The online social networks are Epinions, Slashdot, and Douban, collected from their respective websites.
5.2 Experimental results
Across UIC and WIC experiments, StaticGreedy matches the accuracy of CELFGreedy on feasible moderate networks and outperforms other methods, while substantially reducing runtime and simulations.
- Accuracy comparison: StaticGreedy achieves almost the same influence spread as CELFGreedy on NetHEPT and NetPHY under both UIC and WIC models.
- Accuracy comparison: On large-scale networks where CELFGreedy is infeasible, StaticGreedy consistently provides the best accuracy among the compared algorithms.
- Accuracy comparison: 20,000 to 100 Monte Carlo simulations reduces the simulation requirement by two orders of magnitude without loss of guaranteed accuracy.
- Running time comparison: StaticGreedyDU runs 2−7 times faster than StaticGreedyCELF across six test networks, with greater improvement on DBLP.
- Running time comparison: The static greedy algorithms reduce runtime by three orders of magnitude versus CELFGreedy while retaining guaranteed accuracy.
- Running time comparison: StaticGreedyDU is comparable in runtime to PMIA and outperforms PMIA on Epinions, Slashdot, and Douban, although PMIA accuracy is unguaranteed.
6. CONCLUSION AND FUTURE WORK
The paper addresses the scalability-accuracy dilemma by sharing Monte Carlo simulations across greedy iterations and adding dynamic marginal-gain updates. It reports comparable accuracy with far fewer simulations and broader model applicability, while identifying parameter selection and further deployment as future work.
- Existing greedy implementations create the scalability-accuracy dilemma through unguaranteed submodularity and monotonicity.
- StaticGreedy shares Monte Carlo simulations across iterations, strictly guarantees submodularity and monotonicity, and converges faster than existing greedy algorithms.
- StaticGreedy achieves the accuracy of state-of-the-art greedy algorithms while reducing required Monte Carlo simulations by two orders of magnitude.
- A dynamic update strategy makes the algorithm comparable to the most scalable heuristic algorithm by exploiting static simulation snapshots.
- The static greedy idea can be generalized to the linear threshold model.
- Future work: Future work will determine the minimum Monte Carlo simulation count R, develop parallel implementations, and test more real-world applications.