PaperlayerView exact revision on arXiv

Source-linked AI summary

SEISMIC: A Self-Exciting Point Process Model for Predicting Tweet Popularity

Qingyuan Zhao, Murat A. Erdogdu, Hera Y. He, Anand Rajaraman, Jure Leskovec

arXiv:1506.02594v1cs.SIphysics.soc-phstat.AP

TL;DR

Predicting the final size of information cascades matters for content ranking and understanding collective behavior. SEISMIC models cascades as self-exciting point processes and predicts most tweets’ final size, failing on 1.80% after 15 minutes.

  • Problem

    The paper asks how to predict an information cascade’s final reshare count, important for content ranking and understanding collective behavior.

  • Method

    SEISMIC models cascades as doubly stochastic self-exciting point processes with flexible, nonparametric post infectiousness.

  • Results

    1.80% of tweets remain unpredicted after 15 minutes, while SEISMIC predicts most tweets for most of the observation period.

  • Takeaways & Limitations

    SEISMIC offers a scalable, accurate approach for predicting information spread across millions of posts in real time without feature engineering.

  • Takeaways & Limitations

    SEISMIC cannot reliably predict final reshare counts when a cascade is in the supercritical, explosive regime.

Abstract

from arXiv · show

Social networking websites allow users to create and share content. Big information cascades of post resharing can form as users of these sites reshare others' posts with their friends and followers. One of the central challenges in understanding such cascading behaviors is in forecasting information outbreaks, where a single post becomes widely popular by being reshared by many users. In this paper, we focus on predicting the final number of reshares of a given post. We build on the theory of self-exciting point processes to develop a statistical model that allows us to make accurate predictions. Our model requires no training or expensive feature engineering. It results in a simple and efficiently computable formula that allows us to answer questions, in real-time, such as: Given a post's resharing history so far, what is our current estimate of its final number of reshares? Is the post resharing cascade past the initial stage of explosive growth? And, which posts will be the most reshared in the future? We validate our model using one month of complete Twitter data and demonstrate a strong improvement in predictive accuracy over existing approaches. Our model gives only 15% relative error in predicting final size of an average information cascade after observing it for just one hour.

1. INTRODUCTION

The introduction frames final cascade-size prediction as a fundamental problem for understanding and managing information cascades. It presents SEISMIC, a self-exciting point-process model designed for accurate, interpretable prediction without expensive feature engineering.

  • Predicting how many reshares a post will ultimately receive is a fundamental question in modeling information cascades.
  • Accurate popularity prediction could improve content ranking, faster trend discovery, and content-delivery networks while offering insights into cascade predictability.
  • SEISMIC models cascade growth with self-exciting point processes, characterizing each post by time-varying infectiousness that can decline as content becomes stale.
  • The model identifies whether a cascade is supercritical and explosive or subcritical and therefore tractable for accurate ultimate-popularity prediction.
  • SEISMIC requires only reshare times and resharing-node degrees, avoids expensive feature engineering, and computes predictions in time linear in observed reshares.

2. RELATED WORK

Prior cascade-size prediction methods primarily use feature-based or point-process approaches. SEISMIC differs by modeling time-varying post infectiousness, targeting ultimate cascade size rather than network inference, and achieving linear-time computation.

  • Approaches to cascade prediction: Existing cascade-size prediction methods generally fall into feature-based and point-process approaches.Information-cascade research is described as a rich and active field.
  • Feature-based methods: Feature-based methods extract content, poster, network, and temporal features before applying learning algorithms such as regression, collaborative filtering, trees, and passive-aggressive methods.The passage lists several representative learning techniques used after feature extraction.
  • Point-process methods: Point-process methods directly model cascade formation and have mainly been developed for network inference from observed cascades.These methods have also been applied to studying meme spread on the web.
  • SEISMIC’s distinction: SEISMIC predicts ultimate cascade size in an observed network rather than inferring the underlying network.This explicitly distinguishes the paper’s objective from the complementary network-inference problem.
  • SEISMIC’s distinction: SEISMIC models intensity λ_t through stochastic post infectiousness p_t, allowing infectiousness to change over time, and has linear time complexity instead of expensive Bayesian inference.The model is contrasted with existing Hawkes-process methods on both its time-varying intensity assumption and computational cost.

3. MODELING INFORMATION CASCADES

SEISMIC models information cascades by combining time-varying post infectiousness with a memory kernel for human reaction times. This framework estimates spreading rate, classifies cascades as explosive or dying out, and predicts final reshare counts.

  • Model objectives: SEISMIC estimates cascade infectiousness, determines whether spreading is supercritical or subcritical, and predicts the ultimate number of reshares.The model uses R_t, the total reshares by time t, to characterize cascade progression.
  • Model components: The memory kernel φ(s) models delays between feed arrival and resharing, while infectiousness models the probability that a user reshares a post.Together, these quantities determine the speed at which a post spreads through the network.
  • Model components: Post infectiousness p_t(w) is time-dependent and may reflect content quality, network structure, local time, and geographical location.Unlike fixed-infectiousness approaches, SEISMIC does not assume a parametric form for p_t(w).
  • Point-process formulation: SEISMIC represents R_t as a doubly stochastic self-exciting point process combining human reaction times and post infectiousness.Its intensity is shaped by infectiousness, prior reshare times, node degrees, and the reaction-time distribution φ(s).
  • Criticality: The critical infectiousness threshold is p∗ = 1/n∗ when node degrees are independently and identically distributed with mean n∗.This threshold separates the supercritical and subcritical regimes under the model’s criticality framework.

4. PREDICTING INFORMATION CASCADES

SEISMIC infers time-varying post infectiousness from resharing histories and predicts final cascade size using network-informed branching-process reasoning. Its prediction is adjusted for future infectiousness changes, but becomes unreliable in the supercritical regime where expected future reshares are infinite.

  • Inferring infectiousness: SEISMIC estimates infectiousness p̂_t from the sample-function density of observed reshare times and user degrees, using a maximum-likelihood estimator.The estimator can also provide a confidence interval for p_t.
  • Inferring infectiousness: A triangular kernel with growing window size t/2 smooths infectiousness estimates by discarding older observations, stabilizing estimates, and emphasizing recent reshares.The kernel removes posts older than t/2, expands its window as t increases, and up-weights more recent posts.
  • Predicting final cascade size: SEISMIC predicts final reshare count by modeling cascade growth as a branching process over the network, while its final estimator does not require explicit network structure information.The branching-process formulation uses expected offspring generated by reshares to derive the expected final cascade size.
  • Predicting final cascade size: When p̂_t ≥ 1/n∗, the point process is supercritical, expected future reshares are infinite, and the final reshare count cannot be reliably predicted.In this regime, the offspring expectation µ = n∗p̂_t is at least 1 and the expected generation sizes do not decrease.
  • Predicting final cascade size: To account for changing future infectiousness, SEISMIC adjusts its prediction with time-varying scaling constants α_t and γ_t selected to minimize median Absolute Percentage Error.The same α_t and γ_t values are used for all posts at a given time, and α_t is more important than γ_t in practice.
  • Computational complexity: O(R_t) is the computational cost of both calculating p̂_t and predicting R̂∞(t), for any choices of φ(s) and K_t(s).Actual computing time depends heavily on the integration.

5. EXPERIMENTS

The experiments describe the Twitter dataset and parameter estimation procedure, then compare SEISMIC with state-of-the-art approaches.

  • The experiments cover the Twitter dataset, parameter estimation, and performance comparisons between SEISMIC and state-of-the-art approaches.

5.1 Data description and data processing

The study uses complete Twitter data from one month in 2011, focusing on tweets with at least 50 retweets. The dataset contains 166,076 qualifying tweets in the first 15 days, while available network information is limited to users’ follower counts.

  • Data description: The dataset contains over 3.2 billion tweets and retweets collected from October 7 to November 7, 2011.Each retweet records tweet ID, posting time, retweet time, and poster/retweeter follower counts; network connections are unavailable.
  • Data processing: The analysis selects tweets with at least 50 retweets, yielding 166,076 qualifying tweets in the first 15 days.Independently posted copies of the same tweet are treated as separate cascades.
  • Data processing: For training tweets, R14 days has mean 209.8 and median 110.The temporal evolution of mean and median Rt is also shown in Figure 3.

5.2 SEISMIC parameter estimation

SEISMIC estimates a network-wide memory kernel from retweet-time distributions and sets correction factors shared across tweets. The fitted parameters then support five-minute predictions of each tweet’s final retweet count.

  • Memory-kernel estimation: SEISMIC estimates its memory kernel φ(s) from the retweet-time distribution of 15 carefully selected training tweets.Their retweet-time histograms show subcritical decay, and the original posters’ many followers suggest most retweets come from immediate followers.
  • Memory-kernel estimation: 5 minutes is the constant initial period for φ(s), followed by power-law decay with θ = 0.242 and c = 6.27 × 10−4.The parameters are estimated from the observed reaction-time distribution, with c chosen so the kernel integrates to one.
  • Memory-kernel estimation: The memory kernel is network-wide and needs to be estimated only once, although network structure could further improve its estimation.The fitted kernel is plotted in Figure 4.
  • Correction factors: 20 is the shared setting for γ_tn* because this product has little effect on algorithm performance, while α_t minimizes training median Absolute Percentage Error.Values of α_t are reported in Table 2.
  • Application: Every 5 minutes, SEISMIC outputs an estimate of tweet w’s final retweet count R∞(w).The estimate is denoted R̂∞(t, w) and is produced after applying the estimated parameters to the Twitter dataset.

5.3 Baselines for comparison

The comparison includes four prediction methods: two regression baselines and two point-process models. These span linear and feature-augmented regression, a Dynamic Poisson Model, and a reinforced Poisson approach.

  • 5.3 Baselines for comparison: Four prediction methods are considered: Linear Regression, Linear Regression with degree, Dynamic Poisson Model, and Reinforced Poisson Model.The first two methods are regression based, while the latter two are point-process based.
  • 5.3 Baselines for comparison: Linear Regression gives all tweets the same multiplicative constant for a given time.It is also the second baseline estimator used in [34].
  • 5.3 Baselines for comparison: Linear Regression with degree is more flexible than Linear Regression because log Rt may have a slope other than 1 and additional features are included.Its specification uses log Rt, log Nt, and log n0 alongside time-varying coefficients.
  • 5.3 Baselines for comparison: Dynamic Poisson Model represents retweet times as a point process, estimating the power-law parameter γ separately for each tweet.Retweet times are discretized into b = 5 minute intervals, and tpeak is shifted forward when the relevant integral is infinite.
  • 5.3 Baselines for comparison: Reinforced Poisson Model represents reshare rates using message attractiveness, aging, and reinforcement functions.For each tweet, c, γ, and α are fitted by likelihood maximization and projected to feasible sets when necessary.

5.4 Evaluation metrics

The evaluation uses Absolute Percentage Error, Kendall-τ Rank Correlation, and Breakout Tweet Coverage to assess prediction accuracy, ranking quality, and identification of highly reshared tweets. APE is summarized across test-tweet quantiles at each prediction time, while the other metrics compare predicted with final retweet counts or top-k lists.

  • Evaluation metrics: Absolute Percentage Error evaluates predictions for each tweet at a given prediction time, with quantiles reported across test tweets.The metric is defined for tweet w and prediction time t, and its quantiles are reported at each time t.
  • Evaluation metrics: Kendall-τ Rank Correlation measures the correlation between predicted and final retweet-count ranks across test tweets.It is generally more robust than Pearson’s correlation of values, and higher rank correlation indicates stronger correspondence.
  • Evaluation metrics: Breakout Tweet Coverage measures how well a predicted top-k list covers the ground-truth top-k tweets with the highest final retweet counts.The ground-truth list defines breakout tweets, while the model produces its list using predicted final retweet counts.

5.5 Experimental results

SEISMIC provides an empirically unbiased estimate of final retweet counts and, using a calibrated prediction, outperforms competing methods in cascade-size accuracy and ranking. It also detects breakout tweets early, covering substantial portions of the eventual top-100 list after limited observation.

  • Estimator validation: SEISMIC’s predicted final retweet counts almost perfectly track empirical averages, supporting the estimator’s unbiasedness.The experiments subsequently use the calibrated prediction formula to stabilize estimates and improve overall performance.
  • Cascade-size prediction: After 10 minutes, the 95th, 75th, and 50th APE percentiles are below 71%, 44%, and 25%, respectively.Thus, average error is below 25% for 50% of tweets and below 71% for 95% of tweets.
  • Cascade-size prediction: 30% more accurate than all competitors across the entire tweet lifetime, SEISMIC consistently outperforms the baselines and state-of-the-art methods.The comparisons use median APE over time as increasingly more of each retweet cascade is observed.
  • Ranking prediction: SEISMIC produces more accurate rankings of the most-retweeted tweets than the other methods using Kendall-τ rank correlation.The ranking comparison evaluates predicted top-tweet order against the ground-truth ranking.
  • Breakout detection: After seeing 20% of retweets, SEISMIC covers 65% of the shortlist, compared with 50% for both LR-D and LR.The dynamic Poisson model generally fails to provide accurate predictions and breakout identifications.
  • Breakout detection: After observing around 5 minutes, SEISMIC identifies 60% of the top-100 tweets by final retweet count.It covers 82 tweets within 1 hour and 93 within 6 hours, while LR, LR-D, and DPM detect the illustrated breakout more slowly or fail during the first 6 hours.

5.6 Discussion of model robustness

SEISMIC is more robust than DPM and RPM because it can predict for most tweets most of the time, while the alternatives fail for larger fractions under their respective constraints. Its coverage of the top 500 tweets also improves clearly once roughly 10% of retweets are observed.

  • Discussion of model robustness: SEISMIC is more robust than DPM and RPM, which fail when their decay parameters leave feasible sets, whereas SEISMIC cannot predict supercritical tweets.DPM fails for γ < −1; RPM fails for γ < 0 or α < 0.
  • Discussion of model robustness: 1.80% of tweets remain unpredicted by SEISMIC after 15 minutes, falling to 1.29% after 1 hour and 0.67% after 6 hours.These figures cover tweets with at least 50 retweets; the remaining tweets are still in the supercritical regime after 15 minutes.
  • Discussion of model robustness: SEISMIC improves coverage of the top 500 tweets after about 10% of retweets are observed, while all methods except DPM achieve perfect coverage after 65%.The comparison concerns coverage of the top 500 tweets, L∗ 500.
  • Discussion of model robustness: 6.77%, 5.79%, and 1.45% of tweets are unpredicted by DPM after 15 minutes, 1 hour, and 6 hours, respectively.RPM fails for 3.45%, 5.69%, and 15.43% at the same observation times.

6. CONCLUSION AND FUTURE WORK

SEISMIC is a flexible, statistically sound framework for modeling information cascades and predicting final cascade size as they unfold. It models cascades as self-exciting point processes on Galton-Watson trees and supports scalable, real-time prediction without feature engineering.

  • Contributions: SEISMIC models information cascades as self-exciting point processes on Galton-Watson trees, providing a theoretical framework for temporal cascade patterns.The model is designed to explain temporal patterns in information cascades.
  • Contributions: SEISMIC requires no feature engineering and scales linearly with the number of observed reshares for a post.This enables prediction for millions of posts in an online real-time setting.
  • Conclusion and future work: SEISMIC is a statistically sound and scalable bottom-up model for predicting final cascade size as the cascade unfolds over the network.The framework is intended to support richer understanding and better management of shared content.
Loading 1506.02594v1…