PaperlayerView exact revision on arXiv

Source-linked AI summary

Scalable Influence Estimation in Continuous-Time Diffusion Networks

Nan Du, Le Song, Manuel Gomez Rodriguez, Hongyuan Zha

arXiv:1311.3669v1cs.SIcs.LG

TL;DR

Finite-time influence estimation must capture continuous cascade timing while scaling to networks with millions of nodes. The paper introduces CONTINEST, a randomized estimator that uses independent transmission-time samples and shortest-path structure. It reports scalable estimation and improved influence-estimation accuracy and influence-maximization quality over prior state-of-the-art methods, with a greedy guarantee of (1 −1/e)OPT −2Cϵ.

  • Problem

    Finite-time influence estimation requires accurate timing models and scalable computation, whereas prior work largely considered infinite time windows.

  • Method

    CONTINEST is a scalable randomized algorithm for continuous-time diffusion networks with heterogeneous transmission functions, using graphical-model and neighborhood-estimation perspectives.

  • Results

    The method scales to networks of millions of nodes while improving estimated-influence accuracy and selected-node influence over previous state-of-the-art methods.

  • Takeaways & Limitations

    Used within greedy influence maximization, the estimator guarantees influence at least (1 −1/e)OPT −2Cϵ under uniform estimation error ϵ and confidence 1 −δ.

  • Takeaways & Limitations

    The continuous-time diffusion model assumes shift-invariant, nonnegative transmission functions, and the randomized greedy procedure introduces sampling error.

Abstract

from arXiv · show

If a piece of information is released from a media site, can it spread, in 1 month, to a million web pages? This influence estimation problem is very challenging since both the time-sensitive nature of the problem and the issue of scalability need to be addressed simultaneously. In this paper, we propose a randomized algorithm for influence estimation in continuous-time diffusion networks. Our algorithm can estimate the influence of every node in a network with |V| nodes and |E| edges to an accuracy of $\varepsilon$ using $n=O(1/\varepsilon^2)$ randomizations and up to logarithmic factors O(n|E|+n|V|) computations. When used as a subroutine in a greedy influence maximization algorithm, our proposed method is guaranteed to find a set of nodes with an influence of at least (1-1/e)OPT-2$\varepsilon$, where OPT is the optimal value. Experiments on both synthetic and real-world data show that the proposed method can easily scale up to networks of millions of nodes while significantly improves over previous state-of-the-arts in terms of the accuracy of the estimated influence and the quality of the selected nodes in maximizing the influence.

1 Introduction

Influence estimation seeks to predict how many follow-ups a source set generates within a finite time window, while accounting for cascade timing and network scale. The paper proposes a scalable randomized approach for continuous-time diffusion networks.

  • Influence maximization selects source nodes expected to trigger the largest number of follow-ups within a specified time window.Finite windows matter in applications such as reaching a target audience within one month rather than over an unlimited horizon.
  • Finite-time influence estimation must model cascade timing accurately and scale to large real-world networks.
  • Continuous-time diffusion models can represent asynchronous follow-ups and richer temporal dynamics than discretized models.Discrete-time models introduce bin-size choices and restrict transmission times to exponential densities.
  • Continuous-time influence estimation and maximization remain difficult because exact inference is generally computationally expensive and scaling to millions of nodes is unclear.Exact methods can scale exponentially with network size and density, while naive sampling is not scalable for maximization.
  • CONTINEST is a scalable randomized algorithm for continuous-time influence estimation with heterogeneous edge transmission functions.It estimates every node using n = O(1/ϵ^2) randomizations and O(n|E| + n|V|) computations up to logarithmic factors.

2 Continuous-Time Diffusion Networks

The paper models diffusion as a continuous-time independent cascade process in which transmissions have edge-specific waiting-time distributions. Infection times are determined by shortest paths under sampled transmission times.

  • Continuous-time cascade models assign each directed edge a transmission-time density rather than a fixed infection probability.Events are sampled directly from transmission functions instead of being generated in discrete rounds.
  • The process starts with infected source nodes at time zero and transmits contagion along outgoing edges using independent random spreading times.
  • Transmission functions may be heterogeneous across edges and can be parametric or nonparametric.They are shift invariant, nonnegative, and support models such as exponential and Rayleigh functions.
  • Each node’s infection time equals the length of the shortest path from the sources when sampled transmission times serve as edge weights.

3 Graphical Model Perspectives for Continuous-Time Diffusion Networks

The graphical-model perspective replaces dependent infection-time variables with independent edge transmission times. A shortest-path transformation then connects the two representations and supports finite-window infection probabilities.

  • The continuous-time independent cascade model is a directed graphical model whose dependencies follow the contact network.Parents in a cascade-induced DAG determine each node’s conditional infection-time density.
  • Switching from node infection times to edge transmission times yields a fully factorized representation over mutually independent variables.
  • Each infection time is obtained by transforming sampled edge transmission times through a shortest-path minimization.Paths are taken from the source nodes, which are infected at time zero.
  • The node-centric and edge-centric formulations are connected by shortest-path computation in a weighted directed graph.

4 Influence Estimation Problem in Continuous-Time Diffusion Networks

Influence within a finite time window is the expected number of nodes infected by that time. Computing it requires graphical-model inference over dependent infection times, which is generally difficult and expensive.

  • Influence is defined as the expected number of infected nodes from a source set A by time T.A node counts when its infection time satisfies ti ≤ T.
  • The influence objective can be expressed using indicator variables over dependent infection times.The expectation is taken over the joint infection-time variables.
  • Estimating influence is a graphical-model inference problem requiring marginalization over other nodes’ infection times.
  • High-degree graphical models require integration over many continuous variables, making exact influence computation challenging.Large tree-width and heterogeneous transmission functions complicate analytic evaluation.
  • 37?
  • Exact closed forms exist only in special cases, while general methods can have exponential complexity in network size and density.This motivates efficient approximation algorithms.

5 Efficient Influence Estimation in Continuous-Time Diffusion Networks

CONTINEST transforms continuous-time influence estimation into randomized neighborhood-size estimation, reusing computations across source nodes and achieving near-linear scalability up to logarithmic factors.

  • Naive sampling estimates influence by drawing transmission-time samples, running shortest-path algorithms, and averaging the resulting neighborhood sizes.Its repeated shortest-path computations create substantially higher complexity than CONTINEST.
  • Cohen’s least-label method estimates every node’s neighborhood size from minimum exponential random labels over sampled transmission times.The minimum label has a distribution parameterized by the neighborhood size, enabling an unbiased estimator.
  • Binary search on each node’s least-label list retrieves the smallest reachable label within a specified time window.The lists store distance–label pairs ordered to support efficient time-window queries.
  • O(|E| log |V| + |V| log^2 |V|) is the per-sample complexity of the least-label algorithm for all single-source neighborhood sizes.The overall complexity scales with the number of random-label collections and includes an additional query term.
  • For multiple sources, CONTINEST unions individual neighborhoods and reuses their least-label lists, avoiding fresh sampling when the source set grows.This reuse is the key computational difference from naive sampling.
  • CONTINEST averages neighborhood estimates across n transmission-time samples, while a small inner-loop label count m can reduce variance efficiently.The paper states that m can be small in practice and gives a uniform accuracy guarantee for bounded source sets.

6 Influence Maximization

Influence maximization is NP-hard but admits greedy approximation because influence is monotonic and submodular; CONTINEST supports this process with reusable estimates and a sampling-error guarantee.

  • Influence maximization seeks up to C source nodes whose expected infected-node count within time T is largest.The optimization is NP-hard in general.
  • Monotonicity and submodularity allow greedy selection to achieve at least (1 − 1/e) of the optimal influence.Lazy evaluation can reduce the number of marginal-gain computations.
  • Greedy iterations reuse least-label lists computed for individual nodes instead of rerunning the full influence-estimation algorithm.The expected aggregate storage for these lists is O(|V| log |V|).
  • CONTINEST’s nested sampling loops and distributed least-label storage support straightforward parallelization.In practice, the outer transmission-time sampling loop is the main loop requiring parallelization because m ≪ n.
  • Uniform influence-estimation error ϵ yields a greedy solution of at least (1 − 1/e)OPT − 2Cϵ with probability at least 1 − δ.The guarantee assumes all source sets of size at most C are estimated uniformly with error ϵ and confidence 1 − δ.

7 Experiments

Experiments evaluate CONTINEST on heterogeneous synthetic diffusion networks and MemeTracker, measuring estimation accuracy, runtime, scalability, and influence-maximization quality.

  • Experimental setup: Synthetic experiments use core-periphery, random, and hierarchical Kronecker networks with heterogeneous edge transmission functions.Each network type includes 10 samples with independently chosen transmission parameters.
  • Synthetic networks: Relative error falls below 0.01 with 10,000 random samples and 5 random labels in the core-periphery accuracy experiment.CONTINEST closely fits the near-ground-truth Naive Sampling estimates as the time window, samples, and labels vary.
  • Scalability: CONTINEST outperforms INFLUMAX and Naive Sampling in runtime for influence estimation and maximization experiments.The source-count experiment uses 128-node, 320-edge core-periphery networks with T = 10.
  • Scalability: Network-size experiments scale from 100 to 1,000,000 nodes at density 1.5, with CONTINEST’s runtime increasing linearly with network size.The comparison reports parallel runtime for CONTINEST and Naive Sampling; INFLUMAX is described as not scalable.
  • Real-world data: MemeTracker evaluation uses 10,967 hyperlink cascades among 600 media sites and repeated 80%/20% train-test splits.Continuous-time models are learned with NETRATE using exponential transmission functions.

8 Conclusions

The paper presents randomized continuous-time influence estimation for heterogeneous networks, with scalability to millions of nodes and improved estimation and source-selection quality over prior methods.

  • CONTINEST is proposed as a randomized influence-estimation algorithm for continuous-time diffusion networks that scales to millions of nodes.The conclusion also reports improvements over previous state-of-the-art methods in estimated influence accuracy and selected-node quality.
  • Modeling assumptions: Continuous-time transmission functions model edge-specific waiting times through conditional densities that are shift invariant and nonzero only for nonnegative delays.This formulation permits heterogeneous transmission behavior across directed edges.
  • Modeling assumptions: Exponential and Rayleigh transmission functions are common prior choices, while heterogeneous real-world waiting times motivate more flexible models.The paper notes that nonparametric transmission functions can improve real-world diffusion modeling.
  • Modeling assumptions: Hazard-based modeling expresses the transmission density as fji(τji) = hji(τji)Sji(τji), requiring nonnegative hazard functions rather than explicit density normalization.This facilitates nonparametric transmission-function modeling.

B A Graphical Model Perspective

The paper reframes continuous-time diffusion inference through graphical models and then transforms dependent infection times into independent edge transmission times. This connects influence estimation to shortest-path computation.

  • Each cascade induces a directed acyclic graph, enabling infection times to be modeled with a directed graphical model despite loops in the contact network.
  • Conditional infection-time densities factor over each node’s parents, although the independent cascade model initially specifies only pairwise transmission functions.
  • Independent-Infection derives each conditional density from pairwise transmission functions by summing parent-specific infection likelihoods.
  • The same factorization applies to any induced DAG consistent with the contact network because infection-time ordering zeroes out incompatible transmission terms.
  • The alternative edge-centric view treats transmission times as mutually independent and expresses infection times through shortest paths in a weighted directed graph.

C Naive Sampling Algorithm

Naive sampling estimates influence by repeatedly sampling edge transmission times, solving shortest-path problems, and averaging reachability counts. Although it supports arbitrary transmission functions, repeated shortest-path computation makes it unsuitable for very large networks.

  • Naive sampling draws n transmission-time samples, computes shortest paths from the source nodes for each sample, and averages the resulting counts.
  • For a single source, the procedure requires O(n|E| + n|V| log |V|) computation because shortest paths are computed for every sample.
  • With C selected nodes, repeated influence estimation adds a multiplicative C|V| factor and makes the computation quadratic in network size.
  • Least Label List: Algorithm 1 uses exponentially distributed node labels and ordered processing to construct least-label lists that support distance queries.
  • Least Label List: In the example, binary search on node c’s least-label list identifies node a within distance 0.8 as having the smallest label, r(a) = 1.5.

E Theorem 1

Theorem 1 provides concentration guarantees for CONTINEST’s randomized influence estimator, including accuracy for fixed source sets and simultaneous accuracy over bounded-size source sets.

  • Estimator construction: The randomized algorithm constructs an unbiased estimator for influence by combining random transmission times with random labels.For fixed transmission times, the estimator is unbiased for infected-neighborhood size; averaging over transmission times makes it unbiased for influence.
  • Variance analysis: The estimator’s variance combines random-label variance, represented by σ(A,T)/(m−2), with transmission-time variance Var(Sτ).The variance decomposition follows from the conditional estimator variance and the variance of infected-neighborhood size across transmission-time samples.
  • Fixed-set guarantee: With probability at least 1−δ, sampling sufficiently many random transmission times guarantees |bσ(A,T)−σ(A,T)|≤ϵ.The sample requirement is obtained by applying Bernstein’s inequality to the final estimator.
  • Simultaneous guarantee: For all source sets A with |A|≤C, a union-bound argument yields the same error guarantee with probability at least 1−δ.The bound uses the constant Λ, defined as the maximum variance-related quantity over source sets of size at most C.
  • Experimental evaluation: Figures 5 and 6 evaluate estimated influence and relative error as the time window, sample count, and random-label count vary on random and hierarchical Kronecker networks.Both figures use networks with 1,024 nodes and 2,048 edges; the relative-error panels set T=10.

F Additional Experimental Results

Additional experiments assess estimation accuracy, continuous-time influence maximization, and scalability. CONTINEST closely matches exact influence on small networks and performs best in the reported influence-maximization comparisons.

  • F.1 Accuracy of Influence Estimation: Errors decrease dramatically as the number of random samples and labels increases on both random and hierarchical Kronecker networks.Figures 5 and 6 report these trends for networks with 1,024 nodes and 2,048 edges.
  • F.1 Accuracy of Influence Estimation: Relative error remains less than 0.01 across all three tested network types when CONTINEST is compared with exact INFLUMAX values.The comparison uses 10,000 samples and 5 random labels per node, with the highest-degree node selected as the source.
  • F.2 Continuous-time Influence Maximization: CONTINEST performs best for all three network types when estimating expected infected nodes over the time window with 50 selected sources.This experiment uses heterogeneous Weibull transmission functions.
  • F.3 Scalability: Figure 10 compares CONTINEST, INFLUMAX, and Naive Simulation by running time across network densities, sizes, and numbers of selected sources.The comparisons use random and hierarchical Kronecker networks on a single 2.4GHz CPU core.
Loading 1311.3669v1…