Source-linked AI summary
Uncovering the Temporal Dynamics of Diffusion Networks
Manuel Gomez Rodriguez, David Balduzzi, Bernhard Schölkopf
TL;DR
Diffusion studies often observe when nodes become infected or adopt information without revealing the network connections or transmission rates involved. NETRATE infers both from cascade timestamps through a convex, scalable model, recovering network structure and estimating transmission rates on synthetic and real data.
Problem
Cascade observations reveal when nodes adopt information or become infected but not who transmitted it, the transmission rate, or the time required.
Method
NETRATE models diffusion as continuous-time pairwise processes and uses convex maximum-likelihood inference to recover network edges and transmission rates from cascades.
Results
NETRATE reconstructs synthetic and real diffusion networks with high recall, precision, and accuracy, while accurately estimating transmission rates that competing methods cannot estimate.
Takeaways & Limitations
The model provides a scalable, parameter-tuning-free approach for analyzing diffusion dynamics and may support influence maximization, epidemic control, and causal inference.
Takeaways & Limitations
NETRATE’s edge values are not comparable with CONNIE’s because the methods use different priors, preventing mean absolute error evaluation for CONNIE.
Abstract
from arXiv · showhide
Time plays an essential role in the diffusion of information, influence and disease over networks. In many cases we only observe when a node copies information, makes a decision or becomes infected -- but the connectivity, transmission rates between nodes and transmission sources are unknown. Inferring the underlying dynamics is of outstanding interest since it enables forecasting, influencing and retarding infections, broadly construed. To this end, we model diffusion processes as discrete networks of continuous temporal processes occurring at different rates. Given cascade data -- observed infection times of nodes -- we infer the edges of the global diffusion network and estimate the transmission rates of each edge that best explain the observed data. The optimization problem is convex. The model naturally (without heuristics) imposes sparse solutions and requires no parameter tuning. The problem decouples into a collection of independent smaller problems, thus scaling easily to networks on the order of hundreds of thousands of nodes. Experiments on real and synthetic data show that our algorithm both recovers the edges of diffusion networks and accurately estimates their transmission rates from cascade data.
1. Introduction
The paper addresses the challenge of inferring hidden diffusion mechanisms from observed infection times, when transmission sources, connectivity, and exposure requirements are unknown. It introduces a probabilistic model whose convex, decoupled optimization enables inference of networks and transmission rates at large scale.
- Motivation: Observed diffusion data reveal when nodes reproduce information, become infected, or buy products, but not who caused each event or what exposure was required.This limits direct understanding of the mechanisms underlying information propagation and infection.
- Model: The method models diffusion over static, fixed but unknown directed networks with binary infection states.The stated assumptions treat each node as either infected or not infected.
- Method: The authors formulate a generative probabilistic model in which maximizing cascade likelihood jointly identifies the optimal network and transmission rates.The model is designed to describe how infections occur over time in a static network.
- Method: The resulting optimization is convex and decouples into many smaller problems, enabling natural parallelization and scaling to networks with hundreds of thousands of nodes.These properties make the algorithm computationally scalable.
- Novelty: The paper’s main innovation is representing diffusion as a spatially discrete network of continuous, conditionally independent temporal processes operating at different rates.Rather than modeling every individual infection mechanism, the approach captures their effects through transmission processes with varying rates.
2. Problem formulation
The model represents cascades as infection-time observations on a fixed population, using cascade-induced DAGs and pairwise transmission likelihoods to formulate network inference. It maximizes the likelihood of observed cascades over nonnegative transmission rates, with positive rates defining network edges.
- Data: Each cascade records infection times for N nodes over an observation window, with ∞ denoting nodes not infected during that window.The clock resets at the start of each cascade, and the formulation assumes a common window length T across cascades.
- Cascade structure: Within each cascade, earlier infected nodes are parents of later infected nodes, inducing a directed acyclic graph that simplifies inference.The underlying network itself need not be acyclic; each cascade imposes its own DAG structure.
- Pairwise transmission: Pairwise transmission likelihoods depend on infection times and edge-specific rates, with transmission allowed only from an earlier-infected node to a later-infected node.The framework considers different transmission rates over different network edges and uses parametric likelihood models for diffusion dynamics.
- Cascade likelihood: Cascade likelihoods combine first-parent infection events with survival probabilities for nodes remaining uninfected during the observation window.Conditional independence given infected-node parents allows the likelihood to factorize over nodes, while independent cascades yield a product likelihood across cascades.
- Network inference problem: Network inference maximizes the likelihood of the observed cascades over nonnegative transmission rates αj,i, and pairs with αj,i > 0 are network edges.The optimization variables are the transmission rates for every ordered pair of distinct nodes.
3. Proposed algorithm: NETRATE
NETRATE formulates diffusion-network inference as a convex, uniquely solvable, and consistent maximum-likelihood problem under broad transmission models. Its probabilistic objective naturally promotes sparsity and decomposes into independent node-level subproblems that can be solved in parallel.
- Statistical properties: The solution is unique, computable, and consistent, with the maximum-likelihood estimator α̂ consistent.Consistency follows from identification, continuity, and compactness conditions.
- Convex formulation: Under log-concave survival and concave hazard functions, NETRATE’s network inference problem is convex in A.This includes exponential, power-law, and Rayleigh transmission models.
- Model properties: NETRATE’s objective depends on transmission rates and infection-time differences, not absolute infection times or cascade-root times.This makes the formulation invariant to the absolute time origin of each cascade.
- Natural sparsity: The Ψ1 and Ψ2 terms induce a positively weighted l1-norm that encourages sparse solutions without heuristic sparsity penalties.Weights are linear, logarithmic, or quadratic in infection times for exponential, power-law, or Rayleigh models, respectively.
- Optimization: The optimization splits into N independent node-specific subproblems, enabling parallel computation of globally optimal local solutions.Each subproblem estimates N −1 incoming rates using infection times from cascades containing that node.
4. Experimental evaluation
NETRATE recovers diffusion-network structure and transmission rates accurately on synthetic and MemeTracker cascades, generally outperforming NETINF and CONNIE. Its accuracy improves with cascade coverage and observation horizon, while node-wise decomposition enables scalable inference.
- Synthetic-network accuracy: NETRATE outperforms NETINF and CONNIE in precision-recall for all tested synthetic networks under Pareto comparisons.The comparison used hierarchical and random Kronecker networks and a Forest Fire network with observation window T = 10.
- Synthetic-network accuracy: Under 25% normalized MAE, NETRATE estimates transmission rates accurately for almost all tested networks and transmission models.The estimates were computed from 5,000 cascades despite involving more than 2,000 non-zero real numbers.
- Cascade coverage and time horizon: More observed cascades improve precision-recall and transmission-rate estimates, with as many as 5,000 cascades needed for accurate rate estimation.Estimating transmission rates is considerably harder than discovering edges.
- Cascade coverage and time horizon: Longer observation windows improve transmission-rate inference accuracy for exponential, power-law, and Rayleigh transmission models.This result was shown for a hierarchical Kronecker network using 5,000 cascades.
- Running time: A cluster with 25 CPUs can infer a 16,000-node network with 32,000 edges in less than 4 hours.NETRATE achieves this scalability because it naturally splits into one subproblem per node.
- Real-data accuracy: On MemeTracker cascades, NETRATE outperforms CONNIE on precision and recall and outperforms both alternatives on accuracy for most output solutions.NETRATE performs comparably to NETINF on precision and recall and almost matches the alternatives’ best accuracy performances; its solution is unique, unlike their solution curves.
5. Conclusions
NETRATE infers diffusion-network transmission rates by maximizing the likelihood of cascade infection traces in a flexible spatiotemporal model. It yields a unique, efficiently solvable convex problem without hand-tuned sparsity parameters and performs strongly on synthetic data, though real-data performance is modest under its simple pairwise assumption.
- Model: NETRATE infers transmission rates between network nodes by maximizing the likelihood of temporal traces left by infection cascades.The model makes minimal assumptions about the physical, biological, or cognitive mechanisms underlying diffusion.
- Model: Continuous temporal dynamics and heterogeneous edge rates produce a well-defined convex maximum-likelihood problem with naturally interpretable parameters.The optimization can be solved efficiently and does not require hand-tuned parameters to control inferred-network sparsity.
- Evaluation: On synthetic diffusion networks designed to mimic real-world social and information networks, NETRATE achieves high recall, precision, and accuracy with a unique solution.It is typically more accurate than previous methods across the full range of their tunable parameters.
- Evaluation: On real data, NETRATE again provides a unique solution but achieves modest recall, precision, and accuracy because its simple parametric pairwise transmission model is simplistic.It outperforms previous methods in accuracy across a significant part of their tunable-parameter ranges.
- Implications: NETRATE offers a novel view of diffusion processes with potential applications in influence maximization, epidemic control, and causal inference.These applications are proposed as research directions rather than evaluated uses in the conclusions.