Source-linked AI summary
Information diffusion epidemics in social networks
Jose Luis Iribarren, Esteban Moro
TL;DR
Information-diffusion models need to account for heterogeneous recommendation activity and non-instantaneous message passing. The paper combines empirical recommendation data with power-law and Bellman-Harris branching-process models, finding that extreme spreaders dominate transmission and that log-normal waiting times slow diffusion on a logarithmic time scale.
Problem
Existing Galton-Watson descriptions of viral marketing omit the waiting time between receiving and forwarding information, despite experiments showing non-instantaneous, log-normal transmission delays.
Method
The paper models heterogeneous recommendation counts with a power-law distribution and information diffusion with a stochastic Bellman-Harris branching process using log-normal waiting times.
Results
Extreme recommendation events must be included because participants make from one to more than one hundred recommendations, while log-normal waiting times shift diffusion from ordinary time to logarithmic time.
Takeaways & Limitations
Human heterogeneity changes information diffusion qualitatively: large response-time variability slows spreading, while fast responders can produce exponential growth on a shorter time scale.
Takeaways & Limitations
For subexponential waiting-time distributions, the resulting process is non-Markovian, so standard epidemic growth or differential-equation models fail.
Abstract
from arXiv · showhide
The dynamics of information dissemination in social networks is of paramount importance in processes such as rumors or fads propagation, spread of product innovations or "word-of-mouth" communications. Due to the difficulty in tracking a specific information when it is transmitted by people, most understanding of information spreading in social networks comes from models or indirect measurements. Here we present an integrated experimental and theoretical framework to understand and quantitatively predict how and when information spreads over social networks. Using data collected in Viral Marketing campaigns that reached over 31,000 individuals in eleven European markets, we show the large degree of variability of the participants' actions, despite them being confronted with the common task of receiving and forwarding the same piece of information. This have a profound effect on information diffusion: Firstly, most of the transmission takes place due to super-spreading events which would be considered extraordinary in population-average models. Secondly, due to the different way individuals schedule information transmission we observe a slowing down of the spreading of information in social networks that happens in logarithmic time. Quantitative description of the experiments is possible through an stochastic branching process which corroborates the importance of heterogeneity. Since high variability of both the intensity and frequency of human responses are found in many other activities, our findings are pertinent to many other human driven diffusion processes like rumors, fads, innovations or news which has important consequences for organizations management, communications, marketing or electronic social communities.
1. Candidate Models for the recommendation distribution
The paper compares Poisson and power-law models for recommendation counts, motivated by substantial heterogeneity and extreme recommendation events among participants.
- Observed heterogeneity: Recommendation counts range from one to more than one hundred, requiring models that incorporate extreme events.The observed distribution is highly heterogeneous across participants.
- Candidate models: Two candidate treatments represent recommendation counts using either a Poisson distribution or a power-law distribution.The Poisson model uses r ∼Poisson(⟨r⟩), while the proposed alternative uses r ∼PL(α, β).
- Power-law model: The power-law model asymptotically decreases like a power law and includes a small-count cutoff at r∗≃β1/α.Hα,β is a normalization constant for the distribution.
2. Parameter estimation
Model parameters are estimated so competing distributions share the observed mean recommendation count and R0, isolating differences in how they represent heterogeneity.
- Parameter estimation: Parameters are estimated by the method of moments so all models share the campaigns’ observed mean ⟨r⟩ and R0.This makes the distributions differ in their treatment of heterogeneity rather than their mean values.
- Parameter estimation: The Poisson model fits only ⟨r⟩, whereas PL(α, β) fits the first and second moments of r.The power-law model has two parameters, while the Poisson model has one.
- Observed parameters: Both seed-node and viral-node recommendation distributions appear to decay as power laws with the same exponent α ≃3.5.The two distributions are modeled independently to account for their different observed r values.
1. The Galton-Watson branching process
The Galton-Watson process models successive generations of reproducing individuals as a Markov chain, using probability-generating functions to characterize generation sizes.
- Branching-process structure: A branching process begins with a zeroth generation and produces successive generations of children of the same kind.Gn denotes the number of individuals in generation n, and Fn denotes the cumulative number through generation n.
- Branching-process structure: The generation variables form a Markov chain because each generation’s probability law does not depend on preceding generation sizes.The process is defined through the sequences {Gn} and {Fn}.
- Generating functions: The offspring distribution P(G1 = k) = pk is represented by the probability-generating function f(s).The derivative of f(s) at s = 1 gives the expected value of G1.
- Generating functions: The generating function of generation Gn is fn(s), the n-th iterate of the offspring generating function.This property supports analysis of successive generations and their average sizes.
2. Model for Viral Marketing propagation
The viral-marketing model applies a Galton-Watson branching process to propagation trees, distinguishing active spreaders from passive recipients and incorporating their referral behavior.
- Propagation-tree model: A propagation tree starts from one node with G0 = 1, and each generation contains nodes touched by the message.Fn is the total size through generation n.
- Propagation parameters: Viral transmissibility λ is the probability that a touched node is active, while the Fanout Coefficient is the average referrals sent by active nodes.Active nodes pass the viral message along; passive nodes do not.
- Propagation parameters: The average number of referrals across all nodes is treated as constant across generations in the mean-field approach.Referrals from inactive nodes contribute zero to this average.
- Offspring distribution: The Galton-Watson offspring law assigns p0 = 1 −λ and uses the power-law referral distribution for positive offspring counts.Its corresponding generating function describes viral propagation under the model.
- Network-size calculation: The mean-field branch calculation converges below the percolation threshold, where λrv < 1.The infinite-time network size is obtained by combining the trees generated by seed nodes.
- Network-size calculation: The far-from-threshold condition prevents outbreaks from different seed nodes from merging with one another.This condition is required for the network-size calculation’s validity.
3. Age-dependent dynamics: Bellman-Harris process
The Bellman-Harris process extends Galton-Watson modeling by representing both offspring counts and waiting times, capturing heterogeneous and delayed information transmission. Log-normal, subexponential waiting times change the dynamics qualitatively, producing logarithmic-time slowing below the tipping point and altered exponential growth above it.
- Model: The Bellman-Harris process models descendant counts and participant lifetimes as independent non-negative random variables.It generalizes the Galton-Watson process to continuous time, with a random lifetime governed by G(τ).
- Model: The process tracks active participants through Z(t), with generating function F(s,t) used to calculate their probability distribution.The expected active population i(t) is derived from this branching-process formulation.
- Below the tipping point: For R0 < 1, subexponential waiting-time distributions can eliminate the Malthusian parameter, so epidemic growth-equation descriptions fail and infected populations decay like the distribution tail.Pareto, log-normal, and Weibull distributions are cited as important subexponential examples.
- Below the tipping point: Log-normal waiting times make information spreading evolve on the logarithmic time scale ln t rather than the usual time scale t, slowing the dynamics qualitatively.Their influence appears at the population-average level, not only in fluctuations.
- Above the tipping point: For R0 > 1, the Malthusian parameter exists and active populations grow exponentially, but subexponential waiting times can make growth substantially faster than Poissonian estimates.The reported difference can reach one order of magnitude; fast responders contribute to the shorter growth time scale.
APPENDIX C: INFERENCES ON THE SUBSTRATE E-MAIL NETWORK
The appendix derives a mean-field relationship between clustering in the substrate e-mail network and its virally percolated subset. Simulations on a real e-mail network show that viral cascades remain far less clustered than the substrate, supporting the model’s focus on voluntary propagation rather than network topology.
- Network construction: The viral network is a subset of the e-mail network because messages can propagate only along listed e-mail connections.The substrate consists of individuals connected by address-book links.
- Clustering coefficient: The clustering coefficient is defined using triangles and triples, with a triple consisting of a node connected to an unordered pair of others.A connected pair at the open ends forms a triangle or transitive triad.
- Mean-field inference: The appendix derives a mean-field correlation between the clustering coefficients of the e-mail network and its virally percolated subset.The derivation accounts for the probability that edges and triangle-closing links are percolated.
- Simulation test: The derived relationship is tested by simulating viral propagation on a real e-mail network, where nodes spread with probability λ and send an average fanout r_v.The simulations compare viral-cascade clustering with the analytical linear relationship.
- Simulation test: C_email ≃ 0.22 while viral cascades have a very small clustering coefficient even for large λ, supporting the assumption that topology is largely irrelevant near the tipping point.The observed low C_viral is consistent with tree-like cascades despite dense local loops in the substrate network.
APPENDIX D: VIRAL CAMPAIGNS GENERAL DESCRIPTION
The viral marketing campaigns used a common electronic recommend-a-friend structure across 16 campaigns in 11 European countries. Subscribers promoted newsletter registrations through recommendation e-mails, supported by online acquisition tactics and a prize-draw incentive.
- Campaign design: The data came from 16 campaigns executed in 11 European countries with the same structure, strategy, interfaces, data flow, and participant conditions.This common setup supports comparison across campaigns and markets.
- Campaign design: The campaigns sought to increase online-newsletter subscriptions, with a free customizable subscription completed through a registration page.Visitors selected generic interest topics during registration.
- Participant acquisition: Drive-to-web tactics varied by country and included e-mail campaigns and banner advertising to attract visitors to the registration page.The registration page served as the entry point for campaign participation.
- Viral mechanism: A recommendation button invited participants to forward the page to friends and colleagues, offering laptop prize-draw tickets as an additional forwarding incentive.The button triggered electronic viral propagation of the campaign message.