PaperlayerView exact revision on arXiv

Source-linked AI summary

Stop-and-Stare: Optimal Sampling Algorithms for Viral Marketing in Billion-scale Networks

Hung T. Nguyen, My T. Thai, Thang N. Dinh

arXiv:1605.07990v3cs.SIcs.DSphysics.soc-ph

TL;DR

Influence Maximization remains difficult to solve efficiently on billion-scale networks despite its importance in viral marketing and other applications. This paper proposes SSA and D-SSA, which use Stop-and-Stare sampling within a unified RIS framework. The algorithms retain the (1 −1/e −ϵ) guarantee, achieve near-minimum sample thresholds, and substantially reduce running time in experiments.

  • Problem

    Influence Maximization seeks influential users for widespread information diffusion, but billion-scale instances remain unsatisfactorily solved by existing methods.

  • Method

    SSA and D-SSA combine a unified RIS framework with Stop-and-Stare sampling that checks solution quality at exponential checkpoints.

  • Results

    1200 times faster than IMM on Friendster while returning comparable seed-set quality, with SSA and D-SSA achieving the same (1 −1/e −ϵ)-approximation guarantee.

  • Takeaways & Limitations

    The algorithms achieve, within constant factors, the type-1 and type-2 minimum RIS thresholds for sample-based approximation.

  • Takeaways & Limitations

    The paper does not focus on distributed or parallel computation, leaving distributed implementation as future work.

Abstract

from arXiv · show

Influence Maximization (IM), that seeks a small set of key users who spread the influence widely into the network, is a core problem in multiple domains. It finds applications in viral marketing, epidemic control, and assessing cascading failures within complex systems. Despite the huge amount of effort, IM in billion-scale networks such as Facebook, Twitter, and World Wide Web has not been satisfactorily solved. Even the state-of-the-art methods such as TIM+ and IMM may take days on those networks. In this paper, we propose SSA and D-SSA, two novel sampling frameworks for IM-based viral marketing problems. SSA and D-SSA are up to 1200 times faster than the SIGMOD'15 best method, IMM, while providing the same $(1-1/e-ε)$ approximation guarantee. Underlying our frameworks is an innovative Stop-and-Stare strategy in which they stop at exponential check points to verify (stare) if there is adequate statistical evidence on the solution quality. Theoretically, we prove that SSA and D-SSA are the first approximation algorithms that use (asymptotically) minimum numbers of samples, meeting strict theoretical thresholds characterized for IM. The absolute superiority of SSA and D-SSA are confirmed through extensive experiments on real network data for IM and another topic-aware viral marketing problem, named TVM. The source code is available at https://github.com/hungnt55/Stop-and-Stare

1. INTRODUCTION

Influence Maximization seeks influential seed users for viral marketing, but existing guaranteed methods remain challenging to scale to billion-edge networks. The paper introduces SSA and D-SSA, combining a unified RIS framework with Stop-and-Stare sampling to preserve approximation quality while reducing samples and running time.

  • Motivation: Influence Maximization selects k influential users whose information can spread widely through a network.The problem supports viral marketing and related applications involving influence propagation.
  • Motivation: Existing guaranteed methods are either too slow for billion-scale networks or rely on heuristics without performance guarantees.TIM, TIM+, and IMM use RIS sampling but may generate more samples than their theoretical thresholds, which are not established as minimal.
  • Contributions: The unified RIS framework characterizes necessary sample conditions for the (1 −1/e −ϵ)-approximation guarantee and defines type-1 and type-2 minimum thresholds.These thresholds generalize earlier RIS threshold approaches and distinguish minimum thresholds within and across threshold classes.
  • Contributions: Stop-and-Stare generates samples incrementally and checks solution quality at exponential checkpoints until statistical evidence supports termination.This avoids explicitly computing unreachable thresholds and addresses prior methods’ sample-generation shortcomings.
  • Empirical Evaluation: 1200 times faster than IMM on Friendster while returning comparable seed-set quality, with experiments conducted on networks containing up to several billion edges.The reported Friendster case uses roughly 65.6 million nodes, 1.8 billion edges, and k = 500.
  • Contributions: SSA and D-SSA provide (1 −1/e −ϵ)-approximate solutions while achieving, within constant factors, the type-1 and type-2 minimum thresholds, respectively.The methods are designed for IM and can generalize to sample-based optimization problems.
  • Scope: The paper does not focus on distributed or parallel computation, although the algorithms are described as amenable to distributed implementation.Distributed implementation is identified as future work.

2. MODELS AND PROBLEM DEFINITION

The paper models influence propagation with Linear Threshold and Independent Cascade processes over weighted directed graphs. It then defines Influence Maximization as selecting a size-k seed set that maximizes expected influence spread.

  • Propagation Models: The network is represented as a weighted directed graph G = (V, E, w) with n nodes and m edges.Each edge weight lies in [0, 1] and indicates the probability that one node influences another.
  • Propagation Models: Under both models, seed nodes start active, newly activated nodes attempt further activations in discrete rounds, and active nodes remain active.The propagation process stops when no additional nodes become active.
  • Linear Threshold (LT): In the Linear Threshold model, an inactive node activates when the total weight from active in-neighbors reaches its uniformly random threshold.The LT edge weights entering each node must sum to at most 1.
  • Influence Spread: Influence spread I(S) is the expected number of active nodes at the end of propagation for seed set S.The expectation is taken over the model’s random thresholds or edge states.
  • Independent Cascade (IC): In the Independent Cascade model, each newly activated node gets one chance to activate each inactive neighbor with success probability proportional to the edge weight.Influence spread is the expected number of active nodes over the random edge states.
  • Problem Definition: Influence Maximization asks for a seed set of k nodes that maximizes influence spread under the chosen propagation model.The optimization is defined over graph G, budget k, and a propagation model.

3. UNIFIED RIS FRAMEWORK

The unified RIS framework characterizes the sampling conditions and thresholds needed for (1−1/e−ϵ)-approximate influence maximization. It represents influence through random RR-set coverage, then defines type-1 and type-2 minimum thresholds to assess sample requirements.

  • Unified RIS framework: RIS generalizes prior RIS-sampling methods by specifying sufficient conditions for a (1−1/e−ϵ)-approximation and defining RIS thresholds for the required RR-set count.The framework uses two critical conditions and parameterized thresholds to guarantee solution quality.
  • RIS sampling: Random RR sets are generated by selecting a random node, sampling a graph, and returning nodes that can reach the selected node.Each RR set contains nodes capable of influencing its source.
  • RIS sampling: A seed set covers an RR set when their intersection is nonempty; maximizing covered RR sets approximates maximizing expected influence.The framework therefore solves a Max-Coverage problem over generated RR sets using a greedy algorithm.
  • Two types of minimum thresholds: Previous methods approximate explicit thresholds but provide no guarantee that their sample counts are close to the minimum, whereas SSA achieves a type-1 minimum threshold within a constant factor.The framework identifies this gap as the problem of determining the minimum sufficient number of RR sets.
  • RIS thresholds: The RIS framework guarantees that, with sufficiently many RR sets meeting its threshold, the returned seed set is (1−1/e−ϵ)-approximate with high probability.The guarantee is expressed through the number of RR sets and the framework’s approximation conditions.
  • Two types of minimum thresholds: Type-1 and type-2 minimum thresholds formalize increasingly strong lower limits on the number of RR sets required within the RIS framework.Type-1 is the smallest threshold over admissible parameter settings, while type-2 is the tightest threshold achievable in the framework.

4. STOP-AND-STARE ALGORITHM (SSA)

SSA is an approximation algorithm that repeatedly expands its RR-set sample pool, checks candidate quality at exponential checkpoints, and stops when statistical evidence supports termination. Its design combines greedy maximum coverage with independent influence estimation, while parameter choices affect runtime.

  • SSA is the first approximation algorithm presented here to meet, asymptotically, a type-1 minimum threshold.
  • SSA doubles its RR-set pool across iterations, using Max-Coverage to produce a candidate seed set at each checkpoint.At iteration t, the sample count is |R| = Λ2t−1.
  • The algorithm independently estimates candidate influence and stops only when coverage and estimation checks provide sufficient accuracy evidence.The coverage check controls relative error ϵ3, while Estimate-Inf provides an estimate with relative error ϵ2.
  • The two stopping conditions are sufficient to guarantee an (1−1/e−ϵ)-approximation for the returned seed set.
  • Greedy Max-Coverage returns an (1 −1/e)-optimal solution on sampled RR sets and can be implemented in time linear in their total size.
  • Empirically, ϵ1 ≪ϵ2 ≈ϵ3 yields good performance on large networks, while D-SSA is introduced to select near-optimal parameter settings automatically.

5. SSA THEORETICAL ANALYSIS

The theoretical analysis establishes SSA’s high-probability approximation guarantee and shows that its sample usage is within a constant factor of the type-1 minimum threshold under explicit range conditions. The section also identifies parameter sensitivity and discarded verification samples as limitations.

  • SSA’s error analysis separately bounds inaccuracies in candidate influence, estimated candidate influence, and estimated optimum influence.
  • SSA returns a seed set satisfying I( ˆSk) ≥(1 −1/e −ϵ)OPTk when the analyzed bad events do not occur.
  • The range conditions include OPTk ≤1/2|V |, ϵ ≤1/4, and 1/δ = Ω(n).
  • Under the stated range conditions, SSA stops with high probability once the RR-set count reaches O(N1_min(ϵa, ϵb, δa, δb)).
  • SSA performance depends on selecting ϵ1, ϵ2, and ϵ3, and its verification samples are discarded after one use.Reusing those samples may reduce sample generation and improve performance.

6. DYNAMIC STOP-AND-STARE ALGO.

D-SSA dynamically selects precision parameters while operating on a single RR-set stream divided between candidate construction and verification. It retains the approximation guarantee and achieves the strongest type-2 sample-efficiency bound under the stated range conditions.

  • D-SSA automatically selects near-optimal ϵ1, ϵ2, and ϵ3 settings to meet the type-2 minimum threshold asymptotically.
  • At each iteration, D-SSA divides the RR sets into a candidate-construction half and a verification half.Verification samples are reused to construct the candidate in the next iteration.
  • D-SSA stops when its combined precision expression ϵt satisfies ϵt ≤ϵ, then returns the candidate as an (1 −1/e −ϵ)-approximation solution with high probability.
  • The algorithm uses at most tmax = O(log n) iterations.
  • D-SSA returns an (1−1/e−ϵ)-approximate solution with probability at least (1 −δ).
  • Under the range conditions, D-SSA stops with high probability within O(N2_min(ϵ, δ)) samples, the strongest RIS-framework efficiency guarantee.

7. EXPERIMENTS

Experiments compare SSA and D-SSA with established IM and TVM methods across real networks and diffusion models. The proposed algorithms achieve comparable solution quality with substantially lower running time and memory usage.

  • Experimental setup: SSA and D-SSA are compared with CELF++, IMM, TIM/TIM+, and KB-TIM on IM and TVM experiments.The experiments use real networks, including datasets with up to several billion edges, under LT and IC models.
  • Solution quality: All tested methods return comparable seed set quality under both LT and IC models.The quality comparisons are reported in Figures 2 and 3, while CELF++ runs only on NetHEPT because of the time limit.
  • Running time: 1200x is the maximum speedup of D-SSA over IMM on NetHEPT under the LT model.On most other cases, the speedup remains at several hundred times.
  • Algorithm comparison: D-SSA performs at least as well as SSA and outperforms it in cases where SSA’s fixed setting is ineffective.D-SSA addresses this through dynamic error computation at every iteration.
  • Memory usage: 69 and 72 GB are the memory requirements of D-SSA and SSA, compared with 172 GB for IMM on Friendster.Across the experiments, SSA and D-SSA require much less memory, by up to orders of magnitude.
  • Targeted Viral Marketing: 2 orders of magnitude is the minimum TVM running-time improvement of SSA and D-SSA over KB-TIM, reaching 500x.D-SSA is consistently faster than SSA because it uses the more optimal type-2 threshold.

8. CONCLUSION

The conclusion presents SSA and D-SSA as RIS-based solutions to influence maximization that retain the approximation guarantee while meeting minimum sampling thresholds. It connects these developments to applications such as viral marketing and disease control in billion-scale domains.

  • Framework: The unified RIS framework generalizes methods for finding (1 −1/e −ϵ)-approximate solutions in billion-scale networks.It introduces RIS thresholds and two minimum thresholds, called type-1 and type-2.
  • Algorithms: SSA and D-SSA are the first methods reported to meet the type-1 and type-2 minimum thresholds.The conclusion identifies these thresholds as central theoretical contributions.
  • Applications: The proposed developments are presented as enabling applications of influence maximization in billion-scale domains.The cited applications include viral marketing, disease control, virus or worm control, and contamination detection.

Tightness of Chernoff’s bounds

This section establishes tightness results for Chernoff-like bounds used in the analysis. It extends the lower-bound argument to the weakly dependent variables arising in the paper’s lemmas.

  • Bound conditions: The tightness result concerns i.i.d. Bernoulli variables with mean μ ≤ 1/2 and sample average μ̂.For ϵ ∈ (0, 1/2], the stated bounds require a sufficiently large ϵ^2μT term.
  • Parameter range: The restriction ϵ ∈ (0, 1/2] can be relaxed to ϵ ∈ (0, c] for any c < 1 when δ is sufficiently small.This is stated as an assumption-dependent relaxation of the parameter range.
  • Lower bounds: The corollary gives lower-bound conditions for both lower-tail and upper-tail deviations of μ̂.The stated setting has μ ∈ (0, 1/2], ϵ ∈ (0, 1/2], and δ < 1/e.
  • Extension: The lower bounds also apply when the random variables are weakly dependent martingales.This connects the i.i.d. tightness result to the dependent variables used in the paper’s analysis.

Proof of Theorem 1

The proof combines two concentration inequalities with a union bound and the greedy maximum-coverage guarantee. It then derives the claimed (1 −1/e −ϵ)-approximation probability.

  • Probability bound: The two inequalities from Eqs. 9 and 10 hold together with probability at least 1−(δa+δb).The proof obtains this joint probability by applying the union bound.
  • Approximation derivation: The proof combines the sampling inequalities and greedy guarantee to show I(Ŝk) ≥ (1 −1/e −ϵ)OPTk.The contradiction argument uses the relationship among ϵ, ϵa, and ϵb.
  • Greedy guarantee: The greedy solution satisfies CovR(Ŝk) ≥ (1 −1/e)CovR(S∗k) through the maximum-coverage guarantee.This deterministic greedy bound is used as the approximation component of the proof.
  • Conclusion: The final probability guarantee is Pr[I(Ŝk) ≥ (1 −1/e −ϵ)OPTk] ≥ 1 −(δa + δb).This is the theorem’s resulting high-probability approximation statement.

Proof of Lemma 3

The proof establishes that SSA and D-SSA stop under their sampling and accuracy conditions while returning a (1−1/e−ε)-approximation with high probability. It combines concentration bounds, stopping conditions, and union bounds to obtain the stated guarantee.

  • The analysis uses exponentially increasing RR-set sample sizes and concentration bounds to control estimation errors across iterations.Chernoff-type inequalities and union bounds limit the probabilities of the relevant bad events.
  • The returned solution achieves a (1−1/e−ε)-approximation with probability at least 1−δ.The proof combines the approximation bound with a union-bound argument over bad events.
  • SSA stops when either the maximum sample count is reached or all prescribed stopping conditions hold simultaneously.The stopping conditions include a coverage threshold and an influence-estimation consistency condition.
  • With at least TSSA = O(N1(εa, εb, δa, δb)) samples, SSA stops with probability at least 1−2δ.The proof separately establishes termination of influence estimation and satisfaction of the stopping conditions.
  • D-SSA preserves the same (1−1/e−ε)-approximation guarantee whether it stops at the maximum sample count or at an accuracy-controlled iteration.The proof treats the two stopping cases separately and uses concentration events for the iterative estimates.
Loading 1605.07990v3…