PaperlayerView exact revision on arXiv

Source-linked AI summary

Influence Maximization: Near-Optimal Time Complexity Meets Practical Efficiency

Youze Tang, Xiaokui Xiao, Yanchen Shi

arXiv:1404.0900v2cs.SIcs.DB

TL;DR

Influence maximization needs efficient methods that retain approximation guarantees on large social networks. TIM combines a triggering-model algorithm with near-linear expected time and practical heuristics, achieving strong guarantees and large-scale empirical efficiency.

  • Problem

    Existing influence-maximization methods either sacrifice practical efficiency for approximation guarantees or sacrifice guarantees for efficiency, limiting guaranteed methods on sizable networks.

  • Method

    TIM uses a two-phase triggering-model algorithm that computes a sampling threshold and returns a (1−1/e−ε)-approximate solution with high probability.

  • Results

    Across evaluated social networks, TIM outperforms state-of-the-art guaranteed solutions by up to four orders of magnitude in running time and processes a 1.4-billion-edge graph in under one hour.

  • Takeaways & Limitations

    TIM provides practical influence maximization at billion-edge scale while retaining non-trivial approximation guarantees.

  • Takeaways & Limitations

    The surrounding comparison includes prior guaranteed methods with substantial overheads, including Greedy's O(kmnr) cost and RIS's correlation-related inefficiency.

Abstract

from arXiv · show

Given a social network G and a constant k, the influence maximization problem asks for k nodes in G that (directly and indirectly) influence the largest number of nodes under a pre-defined diffusion model. This problem finds important applications in viral marketing, and has been extensively studied in the literature. Existing algorithms for influence maximization, however, either trade approximation guarantees for practical efficiency, or vice versa. In particular, among the algorithms that achieve constant factor approximations under the prominent independent cascade (IC) model or linear threshold (LT) model, none can handle a million-node graph without incurring prohibitive overheads. This paper presents TIM, an algorithm that aims to bridge the theory and practice in influence maximization. On the theory side, we show that TIM runs in O((k+\ell) (n+m) \log n / ε^2) expected time and returns a (1-1/e-ε)-approximate solution with at least 1 - n^{-\ell} probability. The time complexity of TIM is near-optimal under the IC model, as it is only a \log n factor larger than the Ω(m + n) lower-bound established in previous work (for fixed k, \ell, and ε). Moreover, TIM supports the triggering model, which is a general diffusion model that includes both IC and LT as special cases. On the practice side, TIM incorporates novel heuristics that significantly improve its empirical efficiency without compromising its asymptotic performance. We experimentally evaluate TIM with the largest datasets ever tested in the literature, and show that it outperforms the state-of-the-art solutions (with approximation guarantees) by up to four orders of magnitude in terms of running time. In particular, when k = 50, ε= 0.2, and \ell = 1, TIM requires less than one hour on a commodity machine to process a network with 41.6 million nodes and 1.4 billion edges.

1. INTRODUCTION

Influence maximization seeks influential seed nodes, but existing methods struggle to combine strong approximation guarantees with practical efficiency. TIM addresses this gap with near-optimal theory, practical optimizations, and experiments on billion-edge networks.

  • Problem: Influence maximization selects k nodes that directly and indirectly influence the largest number of nodes under a diffusion model.The problem has important applications in viral marketing.
  • Prior work: Kempe et al.’s greedy approach provides (1 −1/e −ε)-approximate solutions but is computationally expensive, motivating methods that reduce overhead.Subsequent algorithms often trade approximation guarantees for practical efficiency, or vice versa.
  • Theory: TIM returns a (1−1/e−ε)-approximate solution with at least 1−n^−ℓ probability in O((k+ℓ)(m+n)log n/ε^2) expected time under the triggering model.Its time complexity is only a log n factor above the Ω(m+n) lower bound under the IC model for fixed k, ℓ, and ε.
  • Practice: TIM’s heuristic optimizations improve computation efficiency by up to 100-fold without compromising theoretical assurances.The paper also provides theoretical analysis comparing state-of-the-art approximation-guaranteed solutions asymptotically.
  • Experiments: Up to four orders of magnitude in running-time improvement were observed over state-of-the-art approximation-guaranteed solutions.With k = 50, ε ≥0.2, and ℓ= 1, TIM processed a network with 41.6 million nodes and 1.4 billion edges in less than one hour.
  • Experiments: Experiments used the largest datasets reported in the literature and showed that TIM can efficiently handle graphs with more than a billion edges.The authors present this as evidence that influence maximization can be practical while retaining strong theoretical guarantees.

2. PRELIMINARIES

The preliminaries define influence maximization under the IC model and review Greedy and RIS approaches. They emphasize the accuracy–efficiency trade-offs motivating TIM.

  • 2.1 Problem Definition: The IC process activates seeds first, gives each newly activated node one probabilistic activation attempt, and preserves activation thereafter.An edge from an activated node to an inactive neighbor succeeds with its propagation probability at the next timestamp.
  • 2.1 Problem Definition: Influence maximization seeks a size-k seed set with maximum expected spread under a diffusion model.Under the IC model, spread is the number of nodes activated when propagation converges.
  • 2.2 Kempe et al.’s Greedy Approach: Greedy iteratively adds the node with the largest expected-spread increase, but estimating expected spread is #P-hard.Monte Carlo measurements provide approximate estimates and can yield a (1 −1/e −ε)-approximate solution with high probability.
  • 2.2 Kempe et al.’s Greedy Approach: O(kmnr) time makes Greedy computationally expensive because it estimates the spread of O(kn) candidate sets using r measurements.Most candidate-set estimations are unnecessary because each iteration only needs the best candidate.
  • 2.3 Borgs et al.’s Method: RIS generates random reverse reachable sets and selects k nodes covering the largest number of them through greedy maximum coverage.Overlap with a random RR set corresponds probabilistically to activating its sampled target node.
  • 2.3 Borgs et al.’s Method: RIS’s near-linear complexity still entails practical overhead because correlated RR sets require a large threshold, producing an ε^-3 term.Correlation can cause frequent node appearances and make maximum RR-set coverage less representative of influence maximization quality.

3. PROPOSED SOLUTION

TIM combines parameter estimation with greedy node selection over random reverse-reachable sets. This design yields a near-optimal expected running time while preserving a (1−1/e−ε) approximation guarantee with high probability.

  • TIM overview: TIM estimates a lower bound on the optimal expected spread, derives θ, and then selects k nodes covering many of θ random RR sets.The two phases are parameter estimation and node selection.
  • TIM overview: Independent RR-set sampling avoids the correlation issue caused by RIS’s threshold-based sampling.TIM fixes the number of sampled RR sets in advance, conditional on θ.
  • Node selection: The node-selection phase uses greedy maximum coverage: each iteration adds the node covering the most remaining RR sets.Covered RR sets are removed after each of k selections.
  • Node selection: RR sets are generated by randomized breadth-first search over incoming edges, and covered-set fractions estimate expected influence.The estimator satisfies E[n · FR(S)] = E[I(S)].
  • Parameter estimation: θ must exceed a threshold involving OPT, but TIM estimates a suitable lower bound because OPT is unknown.The parameter-estimation algorithm returns KPT* within [KPT/4, OPT] with high probability.
  • Guarantees: O((k + ℓ)(m + n) log n/ε^2) expected time and a (1−1/e−ε)-approximate solution with at least 1−n^−ℓ probability characterize TIM’s guarantee.The running time is only a log n factor above the Ω(m + n) lower bound for fixed k, ℓ, and ε.

4. EXTENSIONS

TIM+ refines the estimated spread lower bound to reduce sampling overhead without changing TIM’s asymptotic guarantee. The approach also extends TIM and TIM+ from IC to the more general triggering model.

  • TIM+: TIM+ inserts an intermediate refinement step that turns KPT* into a potentially tighter lower bound for OPT.It applies greedy maximum coverage to RR sets from the last iteration of parameter estimation.
  • TIM+: The refinement estimates the expected spread of a selected size-k set using fresh RR sets and scales the estimate down by 1 + ε′.This produces KPT′, which is combined with KPT* to form KPT+.
  • TIM+: TIM+ uses KPT+ to compute θ before running TIM’s node-selection algorithm, reducing the number of RR sets when KPT* substantially underestimates OPT.The refinement targets the practical overhead caused by an overly small lower bound.
  • TIM+: TIM+ retains TIM’s time complexity and returns a (1−1/e−ε)-approximate solution with at least 1−3n^−ℓ probability.The success probability can be raised to 1−n^−ℓ by increasing ℓ by a factor of 1 + log 3/log n.
  • Triggering model: The triggering model generalizes IC by assigning each node a distribution over subsets of its incoming neighbors.Independent inclusion of incoming neighbors recovers the IC model as a special case.
  • Triggering model: Under the triggering model, random RR sets are generated through sampled triggering graphs and randomized BFS.The RR-set overlap probability equals the probability that the seed set activates the selected node.
  • Triggering model: Under the triggering model, TIM and TIM+ retain O((k + ℓ)(m + n) log n/ε^2) expected time and (1−1/e−ε) approximation guarantees.The theorem gives success probability at least 1−2 · n^−ℓ.

5. THEORETICAL COMPARISONS

TIM and TIM+ improve asymptotic efficiency over RIS and have a more explicit approximation analysis than Greedy. The comparison identifies substantially higher worst-case computational cost for Greedy.

  • RIS comparison: TIM and TIM+ are asymptotically faster than RIS by a factor of ℓ log n/ε.All three methods provide the same stated approximation form under the IC model.
  • Greedy comparison: Greedy’s required Monte Carlo sample count r is formally characterized to achieve a (1−1/e−ε) approximation with high probability.The paper supplies an explicit sufficient lower bound on r.
  • Greedy comparison: O(k^3ℓmn^2ε^−2 log n/OPT) is Greedy’s resulting time complexity even when OPT is known in advance.Because OPT ≤ n, this is much worse than TIM and TIM+’s expected time.

6. ADDITIONAL RELATED WORK

Related work extends influence maximization through algorithmic optimizations, heuristics, and alternative problem settings. These approaches address computational cost or broaden the formulation beyond the paper’s setting.

  • Algorithmic approaches: Prior work optimizes Greedy by avoiding expected-spread evaluations for many node sets, reducing its computation cost.This line of work remains centered on improving Greedy’s efficiency.
  • Algorithmic approaches: Heuristic methods reduce computation by pruning low-probability paths, partitioning networks into communities, or estimating expected influence.These approaches prioritize efficient solution derivation.
  • Alternative settings: Other studies consider different propagation models, competing parties, or predefined termination times.Those settings differ from the influence-maximization setting addressed here.

7. EXPERIMENTS

The experiments evaluate TIM and TIM+ across propagation models and datasets, comparing their running time, expected spreads, memory use, and internal efficiency mechanisms. TIM+ generally delivers strong efficiency and competitive or better influence quality, while performance depends on k, ε, model, and dataset characteristics.

  • Comparison with CELF++ and RIS: TIM+ consistently outperforms TIM on NetHEPT, while TIM is up to two orders of magnitude faster than CELF++ and RIS.When k = 50, CELF++ takes more than an hour, whereas TIM+ finishes within ten seconds.
  • Comparison with CELF++ and RIS: Reducing RIS’s running-time threshold τ can improve empirical efficiency, but its worst-case quality guarantee is then not necessarily retained.
  • Comparison with CELF++ and RIS: TIM and TIM+ can become faster as k increases because the lower bounds KPT ∗ and KPT + grow relative to the parameters determining RR-set counts.By contrast, RIS and CELF++ become slower as k increases.
  • Comparison with CELF++ and RIS: TIM+ reduces TIM’s running time to at most 1/3 through an intermediate step whose computation cost is negligible compared with total TIM+ cost.The intermediate step produces KPT +, which is at least three times KPT ∗ in all cases.
  • Comparison with IRIE and SIMPATH: On larger datasets, TIM+ outperforms IRIE when k > 20 and has less than 5% of IRIE’s computation time on LiveJournal when k = 50.
  • Comparison with IRIE and SIMPATH: TIM+ achieves higher expected spreads than IRIE on DBLP and LiveJournal, similar spreads on NetHEPT and Epinion, and higher or no worse spreads than SIMPATH across the evaluated datasets.Against SIMPATH, TIM+ is three orders of magnitude faster on LiveJournal when k = 50.

8. CONCLUSION

TIM combines provable approximation and expected-time guarantees with heuristic optimizations for practical influence maximization. Experiments report substantial efficiency gains and processing of billion-edge graphs within an hour under stated parameters.

  • Conclusion: TIM supports the triggering model and returns (1 −1/e −ε)-approximate solutions with at least 1 −n−ℓ probability.Its expected running time is O((k + ℓ)(n + m) log n/ε2).
  • Conclusion: 100-fold improvements in empirical efficiency result from TIM’s heuristic optimizations.The conclusion reports these gains without changing the stated asymptotic guarantees.
  • Conclusion: When k = 50, ε = 0.2, and ℓ = 1, TIM processes a billion-edge graph on a commodity machine within an hour.The paper describes this practical efficiency as unmatched by existing solutions with non-trivial approximation guarantees.

APPENDIX

The appendix establishes TIM’s guarantees through randomized-reachability sampling, concentration bounds, parameter estimation, and maximum-coverage analysis. These arguments yield high-probability approximation and expected-time bounds for the algorithm’s components.

  • Appendix: Random RR-set coverage has the same expectation as normalized influence spread.This identity connects RR-set sampling to influence maximization under the propagation model.
  • Appendix: Theorem 1 derives a (1 −1/e −ε)-approximation from RR-set maximum coverage and concentration guarantees.The returned seed set covers at least a (1−1/e) fraction of the best size-k RR-set coverage, leading to the influence bound.
  • Appendix: O(ℓ(m + n) log n) is the expected time complexity derived for Algorithm 2’s RR-set generation.The bound follows after accounting for later iterations reached with decreasing probability.
  • Appendix: Algorithm 3 produces KPT+ ∈ [KPT*, OPT] with high probability by combining the previous estimate with an additional RR-set estimate.The proof defines KPT′ from the covered fraction of sampled RR sets and shows KPT′ ≤ OPT with probability at least 1 −n−l.
Loading 1404.0900v2…