\Title
% \alignauthor Qingyuan Zhao
Murat A. Erdogdu
Hera Yu He
Anand % Rajaraman
Jure Leskovec
% \affaddr{Stanford University
\input{abstract
abstract.tex
% !TEX root = ./paper-twitter.tex

Social networking websites % , like Twitter and Facebook,
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. % Josh thinks "can form" is strange.
%
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.

\hide{
We consider the problem of forecasting information outbreaks on social
networks. Many social networks allow their users to share others' post
with their own friends or followers, which may form many large
information cascades over the network. In this paper, we propose a
self-exciting statistical model to analyze the behavior of such information
cascades. Our model can be used in real time
to: 1. answer when the cascade is large enough to be predictable;
2. classify the cascade into breakout or non-breakout; 3. predict its
final influence. We use a large Twitter data set to validate the
effectiveness of our model, which indeed shows a clear improvement over
several benchmarks.
} % end-hide
Discussion.tex
% !TEX root = ./paper-twitter.tex



% \cite{gao2015modeling} : Re-tweet dynamics are
% modeled using a \cite{shen2014modeling},
% which uses temporal relaxation and reinforcement functions to model the rate of the re-tweet process.
% This method only uses re-tweet times for the prediction and does not require node degrees. The parameter estimation is based on the maximum likelihood estimation, in which three parameters, namely, the attractiveness, and two decay parameters are estimated.

% Finding the optimal values of these parameters relies on gradient ascent algorithm. There are several issues with this approach:
% i-Convergence and the performance of the ascent algorithm strongly depends on the step-size choice.
% Larger step-size may result in divergence, whereas a smaller step-size will result in slow convergence.
% ii-The gradient ascent algorithm will likely converge to a local maximum. Since the likelihood function is not concave in the parameters, iterate produced by the gradient ascent may get stuck in local maxima, which might result in poor prediction performance.
% iii-The unconstrained maximizer of the likelihood function may not be in the feasible set. The decay parameters are constrained to be positive, which may not be satisfied by the optimal values outputted by gradient ascent. In such a case, projection onto feasible set will result in poor performance.

%\subsection{Concluding remarks}
\label{sec:concluding-remarks}

%\qz{make this shorter as well}

In this paper we propose \sem, a flexible framework for modeling information cascades and predicting the final size of an information cascade. Our contributions are as follows:
\begin{itemize}[nolistsep]
        \item We model the information cascades as self-exciting point
        processes on Galton-Watson trees. Our approach provides a theoretical framework for
        explaining temporal patterns of information cascades.
        \item \sem is both scalable and accurate. The model requires no feature engineering and scales linearly with the number of observed reshares of a given post. This provides a way to predict information spread for millions of posts in an online real-time setting.
        \item \sem brings extra flexibility to estimation and prediction tasks as it requires minimal knowledge about the information cascade as well as the underlying network structure.
\end{itemize}

% To make a high-level comparison of our method with the baselines, we
% reexamine the retweet process $R_t$ and its rate $\lambda_t$ which is
% essentially the derivative of $R_t$ and is determined by
% the infectiousness parameter $p_t$ in our model. The first two baselines, MULTI and
% LINREG, only use the ``0th-order'' information of $R_t$. That is, they use only
% $R_t$ to predict for the future. The third baseline, DPM, makes use of
% the ``1st-order'' information by fitting a function form to discretized
% $\lambda_t$, which suffers from the noisy nature of the data and works poorly in practice. Our
% model can be viewed as a systematical way to make use of both ``0th-order''
% and ``1st-order'' information of $R_t$. Further, the infectiousness parameter
% $p_t$ is also much more stable and intrinsic than the
% rate parameter $\lambda_t$.

% It is also interesting to observe that in our experiments we used a relatively small
% value of $\gamma_t$. We explain this by the assumption
%  in Proposition \ref{prop:expectation} that the infectiousness stays
%  the same. However, in reality, $p_t$
% drops down quickly for most of the tweets. A small value of $\gamma_t$
% helps to stabilize our estimator and improve the prediction for most of
% the tweets, but may greatly underestimate the final influence of
% tweets that continue to breakout for a long time, such as the one shown in Figure
% \ref{fig:breakout}. Extra parameters can be added to our framework to
% predict the future behavior of $p_t$. One possibility is to
% incorporate ``2nd-order'' information of $R_t$,  for instance, the
% derivative of $p_t$. We leave this for future research.

There are many interesting venues for
future work and our proposed model can be extended in many different
directions. For example, if the network structure is available, one could replace the node degree $n_i$ by the number of newly exposed followers. If content-based features or features of the original post are available, one could develop a content-based prior of $p_t$ for each post. If temporal features such as the users' time zone are available, one could directly use them to modify the estimator $\hat{p}_t$. In this sense, the proposed model provides an extensible framework for predicting information cascades.

\sem is a statistically sound and scalable bottom-up model of information cascades that allows for predicting final cascade size as the cascade unfolds over the network. We hope that our framework will prove useful for developing richer understanding of cascading behaviors in online networks, paving ways towards better management of shared content. % and applications that identify trending content early.

Experiments.tex
% !TEX root = ./paper-twitter.tex
In this section, we describe the Twitter data set, our parameter estimation procedure, and compare the performance of \sem to state-of-the-art approaches.

\subsection{Data description and data processing}
Our data is the complete set of over 3.2 billion tweets and retweets on Twitter from October 7
to November 7, 2011. For each retweet, the dataset includes tweet id,
posting time, retweet time, and the number of followers of the poster/retweeter.
Note, the data set lacks Twitter network information. The only piece of network information available to us is the number of followers of a node.

We focus on a subset of reasonably popular tweets with at least 50 retweets, so that our model enables the prediction as soon as sufficient number of retweets occur. Note, that if multiple Twitter users independently post the same tweet, which then gets retweeted, each original posting creates its own independent cascade. All in all there are 166,076 tweets
satisfying this criterion in the first 15 days. We form the training set
using the tweets from the first 7 days and the test set using the tweets from the next 8 days. We use the remaining 14 days for the retweet cascades to unfold and evolve.
For a particular retweet cascade, we obtain all the retweets posted within 14 days of the original post time, \ie, we approximate $R_{\infty}$ by $R_{\text{14 days}}$.
We estimate parameters $\phi(s), \alpha_t, \gamma_t
\text{ and } n_{*}$ with the training set, and evaluate the performance of
the estimator $\hat{R}_{\infty}$ on the test set. For the tweets in
our training set, $R_{\text{14 days}}$ has mean 209.8 and median
110. The temporal evolution of mean and median of $R_t$ are also shown in Figure \ref{fig:rtcum}.


% We notice that both mean and median of $R_t$
% approach those of $R_{\infty}$ quite quickly. In fact, on
% average $20\%$ of the retweets occur in the first $5$ minutes, $50\%$
% in the first hour and $80\%$ in the first day.\hera{check numbers!}

\begin{figure}[t]
  \centering
  \includegraphics[width = \columnwidth]{rtcum.pdf}
  \caption{Convergence of the mean and media cumulative retweet count $R_{t}$
  as a function of time.The horizontal lines correspond to mean and median final
  retweet count $R_{14\,\text{days}}$. On average, a tweet receives 75\% of its retweets in the first 6 hours.}
  \label{fig:rtcum}
\end{figure}

\subsection{SEISMIC parameter estimation}
\label{sec:parameter-estimation}
%Next, we describe the fitting of $\phi(s), \alpha_t, \gamma_t \text{ and } n_{*}$.
First we describe how to fit the memory kernel $\phi(s)$
(Section~\ref{sec:human-reaction-time}). We
carefully choose 15 tweets in the training set and use the
distribution of all their retweet times as our $\phi(s)$ (Figure
\ref{fig:pdf}). The histograms of the 15 sequences of retweet times all
display a clear shape of subcritical decay. Moreover, all the original
posters have an overwhelming number of followers. Therefore, most of the
retweets, if not all, should come from the immediate followers of the
original poster. Consequently, the distribution of human reaction time
can be well approximated by that of the retweet times of these 15
tweets. The estimation of $\phi(s)$ can be further improved if the
network structure is available.

The observed reaction time distribution (Figure \ref{fig:pdf}) suggests a form of
Eq.~\eqref{eq:memory-kernel} for the memory kernel: constant in the
first 5 minutes, followed by a power-law decay. After setting the constant
period $s_0$ to 5 minutes, we estimate power law decay parameter
$\theta =$ 0.242 with the complimentary cumulative distribution function
(ccdf), and chose $c = 6.27 \times 10^{-4}$ to make
$\int_{0}^{\infty} \phi(s) ds = 1$. The memory kernel is a network wide
parameter and only needs to be estimated once. The fitted memory kernel is
plotted in Figure \ref{fig:pdf}.
\begin{figure}[t]
  \centering
  \includegraphics[width = \columnwidth]{pdf.pdf}
  \caption{Reaction time distribution and the estimated memory kernel $\phi(s)$.
  The reaction time is plotted on logarithmic axes, hence the linear trend suggests
    a power law decay.}
  \label{fig:pdf}
\end{figure}

\hide{ % jure hide
With the simplified
assumptions on the contagiousness of the 15 selected
tweets, we run the risk of overestimating the tail of $\phi(s)$, which
results in an underestimation of the ``effective'' degree
$N^e_t$. We compensate for the overestimation of $\phi(t)$
by adding parameters $\alpha_t$ and $\gamma_t$ in the final
prediction (See Eq.~\eqref{eq:predict}). As discussed earlier in
Section~\ref{sec:predict-influence}, the $\alpha_t$ and $\gamma_t$
also help correct the bias from assuming constant infectiousness parameter.
} %end-hide

% The reader may question the assumption that the $15$ retweets spreaded
% only among immediate followers, which could lead to an overestimate of the tail of $\phi(s)$
% because the selected $15$ tweets could receive many retweets from
% non-immediate followers. This is one of the reasons we add the
% parameter $\alpha_t$ in the prediction formula
% Eq.~\eqref{eq:new-predict} to correct the possible underestimation of the
% ``effective''degree $N^e_t$. In other data sets with structural
% information, $\phi(s)$ can be estimated more accurately and the
% prediction accuracy may further improve.

% To discretize our method, Algorithm \ref{alg:1} and \ref{alg:2} are
% applied every $5$ minutes. Other parameters need to be estimated before using our algorithm
% are $\alpha_t$, $\gamma_t$ and $n_*$. Notice that $\gamma_t$ and
% $n_{*}$ only affect the predictions through their product $\gamma_t
% n_*$. We find the value of $\gamma_t n_*$ has very little change to the
% performance of our algorithm when it remains relatively small. We
% choose to use $\gamma_t n_* = 20$ for all $t$. Some of the resulting
% $\alpha_t$ that minimizes the training median APE are listed in Table
% \ref{tab:alpha}. The small value of $\alpha$ at $5$ minute is most
% likely due to the overestimation of $p_t$ in the beginning period,
% which is not solved completely by using the triangular kernel $K_t(s)$.

Last, we briefly comment on the correction factors $\alpha_t$ and $\gamma_t$ introduced in Eq.~\eqref{eq:predict}.
We use the same values of $\alpha_t$ and $\gamma_t$ for all tweets. Notice that $\gamma_t$ and $n_{*}$ only affect the predictions through their product $\gamma_t
n_*$. Overall, we find the value of $\gamma_t n_*$ has little effect on the
performance of our algorithm. In our experiments we simply set $\gamma_t n_* =$ 20 for all $t$.
We choose the value of
$\alpha_t$ such that it minimizes the training median Absolute Percentage Error (Section \ref{sec:error-metrics}). We report values of $\alpha_t$ in Table \ref{tab:alpha}. $\alpha_t$ has a particularly
small value at $t =$ 5 minutes, which may be a result of the overestimation
of $p_t$, when the triangular kernel has not moved away from the unstable beginning period.
After that $\alpha_t$ begins a slow and consistent decay to account for the fact that information is getting increasingly stale and outdated over time.

With all the estimated parameters in \sem, we are ready to apply
it (Algorithms \ref{alg:2} and
\ref{alg:1}) to the Twitter dataset. For a given tweet $w$ and every 5 minute interval $t$, we output our estimate $\hat{R}_\infty(t,w)$ of the tweet's final retweet count $R_\infty(w)$.



% To discretize our method, Algorithm \ref{alg:1} and \ref{alg:2} are
% applied every $5$ minutes. Other parameters need to be estimated before using our algorithm
% are $\alpha_t$, $\gamma_t$ and $n_*$. Notice that $\gamma_t$ and
% $n_{*}$ only affect the predictions through their product $\gamma_t
% n_*$. We find the value of $\gamma_t n_*$ has very little change to the
% performance of our algorithm when it remains relatively small. We
% choose to use $\gamma_t n_* = 20$ for all $t$. Some of the resulting
% $\alpha_t$ that minimizes the training median APE are listed in Table
% \ref{tab:alpha}. The small value of $\alpha$ at $5$ minute is most
% likely due to the overestimation of $p_t$ in the beginning period,
% which is not solved completely by using the triangular kernel $K_t(s)$.



% latex table generated in R 3.1.1 by xtable 1.7-4 package
% Sun Nov  9 14:41:37 2014
\begin{table}[t]
\centering
\begin{tabular}{c|rrrrr}
%  \hline
time (minute) & 5 & 10 & 15 & 20 & 30 \\
  \hline
  $\alpha$ & 0.389 & 0.803 & 0.772 & 0.709 & 0.680  \\
   \hline\hline
time (minute) & 60 & 120 & 180 & 240 & 360 \\
\hline
$\alpha$ & 0.562 & 0.454 &
  0.378 & 0.352 & 0.326 \\
  %\hline
\end{tabular}
\caption{Values $\alpha_t$ used in Algorithm \ref{alg:2}.}
\label{tab:alpha}
\end{table}

\subsection{Baselines for comparison}
\label{sec:baseline-estimators}

We consider four different prediction methods for comparison. The
first two are regression based and the next two are point process based.

\begin{itemize}[nolistsep]
\item{\bf Linear regression (LR) \cite{Szabo2010}:} The model can be defined as
$$\log R_{\infty} = \alpha_t + \log R_t +
  \epsilon,$$ where $\epsilon$ denotes the Gaussian noise. This is
  also the second baseline estimator used in \cite{Zaman2014}. % We call this model mult% iplicative because the prediction
  % % for $R_{\infty}$ is just $\alpha(t) \times R_t$.
  Notice that all the
  tweets receive the same multiplicative constant for a given time.
\item{\bf Linear regression with degree (LR-D) \cite{Szabo2010}:} This model can be written as
$$\log R_{\infty} = \alpha_t + \beta_{1,t} \log R_t +
  \beta_{2,t} \log N_t + \beta_{3,t} \log n_0 + \epsilon$$ where
  $\epsilon$ denotes, as before, the Gaussian noise. LR-D is
  more flexible than LR, since it allows $\log R_t$ to have a slope
  not equal to $1$ and uses additional features.
\item{\bf Dynamic Poisson Model (DPM) \cite{Agarwal2009, Crane2008}:}
It models the retweet times $\{t_k \}$
as a point process with rate
\[
\lambda_t = \lambda_{t_{\textrm{peak}}} (t -
  t_{\textrm{peak}})^{\gamma}
\]
where $t_{\textrm{peak}} = \arg\max_{s
  < t} \lambda_s$. The power-law parameter $\gamma$ is estimated
separately for each tweet. To discretize the model, we bin the retweet
times into $b=$ 5 minute intervals. Note that when $\gamma > -1$, the integral
$\int_{t_{\mathrm{peak}} + b}^{\infty} \lambda_t dt$ is
infinite. In such cases, we move $t_{\mathrm{peak}}$ forward to
the second maximum bin.
\item{\bf Reinforced Poisson Model (RPM) \cite{gao2015modeling}:} This
  recently published state-of-the-art approach models the reshare rate as
\[
\lambda_t = c f_{\gamma}(t)r_{\alpha}(R_t)
\]
where parameter $c$ measures the attractiveness of the message, $f_{\gamma}(t)
\propto t^{-\gamma} (\gamma>0)$ models the
aging effect, and $r_{\alpha}(R_t) (\alpha > 0)$ is the reinforcement
function which depicts the ``rich get richer'' phenomenon.
Given a particular tweet, the parameters $c, \gamma, \alpha$ are found by
maximizing the likelihood function, where the optimal values are projected to
their feasible sets whenever they are out of range.
%  respectively that are
% learned by gradient ascent method. Prediction formula is obtained by
% solving a differential equation~\cite{shen2014modeling}.
% chosen so that they address the retweeting dynamics, using an exponential decay in their arguments with the parameters $\gamma$ and $\alpha$,
% respectively. Given a particular tweet, the corresponding parameters are found using the
% maximum likelihood estimation. The prediction is performed, by solving the
% differential equation
% \eqn{
% \frac{dN_t}{dt} = \lambda^*(t,k),
% }
% where $\lambda^*$ is the optimal rate obtained by using optimal parameters.
\end{itemize}

\subsection{Evaluation metrics}
\label{sec:error-metrics}

For a particular tweet, suppose that the prediction for $R_{\infty}$ at
time $t$ is denoted by $\hat{R}_{\infty}(t)$. We use the following evaluation metrics in our experiment:
%
\begin{itemize}[nolistsep]
\item{\bf Absolute Percentage Error (APE):} For a given tweet $w$ and a prediction time $t$, the APE metric is defined as,
\eqn{
\text{APE}(w,t)=\frac{|\hat{R}_{\infty}(w,t) -
    R_{\infty}(w)|}{R_{\infty}(w)}.
}
     When the APE metric is used for evaluation purposes, various
     quantiles of APE over the tweets (all possible $w$) in the test
     dataset will be reported at each time $t$.
\item{\bf Kendall-$\tau$ Rank Correlation:} This is a measure of rank correlation
  \cite{kendall1938new}, which computes the
  correlation between the ranks of $\hat{R}_{\infty}(t)$ and
  $R_{\infty}$ for all test tweets. This metric is generally more robust than Pearson's
  correlation of values of $\hat{R}_{\infty}(t)$ and
  $R_{\infty}$.
  %   That is for our nearly 80,000 tweets we sort
  % them by their true final retweet count $R_{\infty}$. We then compute
  % the rank correlation of this list with the list of predicted retweet
  % counts $\hat{R}_{\infty}(t)$.
  A high value of rank correlation means the predicted and the final retweet counts are strongly correlated.
  %The Pearson  correlation may also be used, but in practice we find it to be less
  %robust than the rank correlation. The Pearson correlation is also
  %less informative, since it is always very high as we observe more retweets.
\item{\bf Breakout Tweet Coverage:} We create a ground-truth list of top-$k$ tweets with the highest final retweet count. We refer to these tweets as ``breakout'' tweets.
  Using our model we can also produce a top-$k$ list based on the predicted final retweet count. We evaluate the methods by quantifying how well the predicted top-$k$ list covers the ground-truth top-$k$ list. We give additional details in Section~\ref{sec:identify-breakout-tweets}.
% Suppose we create
%   a shortlist of $M$ tweets at time $t$ based on
%   $\hat{R}_{\infty}(t)$. This metric measures how well the shortlist
%   covers the top $m$ tweets in the end (based on $R_{\infty}$). We give
%   more motivation for this metric in Section~\ref{Identifying breakout
%     tweets}.
\end{itemize}

% \subsection{Implementation Details}
% \label{sec:impl-deta}

% \jure{This section should be move to section 4. Unless you want to talk about the experimental setup here. If there are any implementation details we need to discuss them at the end of Section 4.}

\subsection{Experimental results}
\label{sec:results}

In this section we evaluate the performance of \sem and the four competitors described in Section
\ref{sec:baseline-estimators}. All the methods start making predictions as
soon as a given tweet gets retweeted 50 times.

\subsubsection{SEISMIC model validation}
\label{sec:model-validation}

First, we empirically validate \sem. In Proposition
\ref{prop:expectation}, we obtain a formula for the expected number of final
retweets in terms of the infectiousness parameter $p_t$. Our goal here is to show that Proposition
\ref{prop:expectation} provides an unbiased estimate of the true final retweet count. We proceed as follows.
%
We use \sem to make a prediction after observing each tweet for 1 hour and then plot the prediction against the true final number of retweets. If \sem gives an unbiased estimate, then we expect a diagonal curve $y=x$, that is, the expected predicted $\hat{R}_{\infty}$ matches the true expected $R_\infty$.

Figure~\ref{fig:valid} shows that the empirical average almost perfectly coincides with \sem's
prediction. This suggests that the \sem estimator in Eq.~\eqref{eq:predict} is unbiased and
we can safely use it to predict the expected final number of retweets.
%
However, as mentioned earlier, in practice one often wants to shrink the
prediction in order to stabilize the estimator and achieve better
overall performance.
%This is particularly important if the error metric is
%Absolute Percentage Error (APE), since an underestimation can at most
%result in 100\% error but an overestimation could incur a much worse
%error.
Therefore, we use the calibrated prediction formula
Eq.~\eqref{eq:new-predict} for the rest of the experiments.
% Note that we also apply similar calibration procedure to all other
% compeitors as we found that it significantly improves their performance as well.

\begin{figure}[t]
  \centering
  \includegraphics[width = \columnwidth]{p5.pdf}
  \caption{Predicted final retweet counts nicely follow the ground-truth retweet counts,
  which suggests \sem provides an unbiased estimate of the final
  retweet count. The dashed red curve is obtained by binning the
  tweets according to the prediction and then computing the average
  number of retweets in each bin.}
  \label{fig:valid}
\end{figure}


\subsubsection{Predicting final retweet count}

We run our \sem method for each tweet and compute the Absolute
Percentage Error (APE) as a function of time. We plot the quantiles of the distribution of APE of \sem in Figure~\ref{fig:ape-ours}.
After observing the cascade for 10 minutes ($t=$10 min), the 95th,
75th, and 50th percentiles of APE are less than 71\% , 44\%, and 25\%, respectively. This means that after 10 minutes, average error is less than 25\% for 50\% of the tweets and less than 71\% for 95\% of the tweets. After 1 hour the error gets even lower---APE for 95\%, 75\% and 50\% of the tweets drops to 62\%, 30\% and 15\%, respectively.

\begin{figure}[t]
  \centering
  \includegraphics[width = \columnwidth]{ape_fill_ours.pdf}
  \caption{Absolute Percentage Error (APE) of \sem on
    the test set. We plot the median and the middle 50th, 80th, 90th
    percentiles of the distribution of APE across the tweets.}
  \label{fig:ape-ours}
\end{figure}

The proposed method, \sem, demonstrates a clear improvement over the
baselines and the state-of-the-art as
shown in Figures \ref{fig:med-cor} and \ref{fig:zoom-in}. The left panels of Figures
\ref{fig:med-cor} and \ref{fig:zoom-in} show the median APE of different methods over time as more and more of the retweet cascade gets revealed. The LR and LR-D baselines
have very similar performances, indicating the additional features used
by LR-D are not very informative. DPM performs poorly across the
entire tweet lifetime, while the other point process approach RPM is worse than LR
and LR-D in the early period but becomes better after about 2 hours.
% are not particularly accurate. Especially early in the lifetime of a tweet (Figure~\ref{fig:zoom-in}) the DPM and RPM then to have larger error than the regression baselines. However, in all cases \sem heavily outperforms all the other methods.
All in all, in terms of median APE score \sem is about $30\%$ more accurate than all the competitors
across the entire twee lifetime.

Similarly, the right panels of Figures \ref{fig:med-cor} and \ref{fig:zoom-in}
show the Kendall-$\tau$ rank correlation between the predicted ranking
of top most retweeted tweets and the ground-truth ranking of
tweets. Again \sem is giving much more accurate rankings than other methods.

% \begin{figure}[t]
%   \centering
%   \includegraphics[width = 3.5in]{med}
%    \caption{Median Absolute Percentage Error (APE) of our model SEISMIC and the baselines.}
%   \label{fig:med}
% \end{figure}
% \begin{figure}[t]
%   \centering
%   \includegraphics[width = 3.5in]{cor}
%   \caption{Rank correlation of our model SEISMIC and the baselines.}
%   \label{fig:cor}
% \end{figure}

\begin{figure}[t]
  \centering
  \includegraphics[width = \columnwidth]{med-cor.pdf}
  \caption{Median Absolute Percentage Error (APE) and Kendall's Rank Correlation
    of \sem and the baselines as a function of time. \sem consistently gives best performance.}
  \label{fig:med-cor}
\end{figure}


\begin{figure}[t]
  \centering
  \includegraphics[width = \columnwidth]{zoomin.pdf}
  \caption{Zoom-in of Figure \ref{fig:med-cor}: Median APE and Rank
    Correlation for the first 60 minutes after the tweet was
    posted. \sem performs especially well compared to the baselines
    early in the tweet's lifetime.}
  \label{fig:zoom-in}
\end{figure}


%\jure{One idea for an experiment: we could simply plot prediction
%error vs. final retweet count. Basically, the idea is, imagine that I
%allow you to see X retweets (or observe the tweet for say 1h), can we
%say anything about how our error correlates with the final retweet
%count. Basically, the idea would be that our error on big-breakouts
%is in fact smaller than the error we get on tweets with small number
%of retweets. Basically, we care more about our model being able to
%predict accurately things that will go big, than to have good
%performance on things that stay small.}
%\qz{I tried a little (not very hard), the results aren't so
%great after 1hr. The big-breakouts have much larger percentage
%errors, which I don't find too surprising.}

\subsubsection{Identifying breakout tweets}
\label{sec:identify-breakout-tweets}

%\jure{Here goes the identification of top information breakouts}

Can we identify a breakout tweet before it receives most of its
retweets? This question arises from various applications like trend
forecasting or rumor detection. The goal of this prediction task is to as early as possible identify ``breakout'' tweets, which have the highest final retweet count.
We quantify the performances of different models in detecting breakout tweets by using models' predictions of tweets' final retweet counts.

First, we form a ground-truth set $L_{M}^{*}$  of size $M$. The set
$L_{M}^{*}$ contains top-$M$ tweets with the highest final retweet
counts. Then with each of the prediction methods, we produce a
sequence of size $m$ lists, $\hat{L}_{m}(t)$. At each time $t$ the list $\hat{L}_{m}(t)$ contains the top-$m$ tweets with the highest predicted retweet counts at time $t$.

As described in Section~\ref{sec:error-metrics}, we then compare each $\hat{L}_m(t)$ with $L_M^{*}$, and calculate the {\em Breakout Tweet Coverage}, which is defined as the proportion of tweets in $L_M^{*}$ covered by $\hat{L}_m(t)$. %In this experiment we use $m = 500$ for predicted lists, and $M = \{ 100, 500\}$ for the ground-truth list.

Fig.~\ref{fig:rank} shows the performance of \sem in detecting top 100 most retweeted tweets ($L_{100}^{*}$) as a function of time.  \sem is able to cover 82 tweets in the
first 1 hour and 93 tweets in the first $6$ hours.

The fifth most retweeted tweet in this plot is actually the tweet we
showed earlier in Figure~\ref{fig:breakout}. We observe that \sem
detects this tweet 30 minutes after it has been posted, while LR and
LR-D both take more than an hour. DPM fails to detect this breakout for the first 6 hours (plots not show for brevity).

% As for the ability of identifying breakout tweets, we look at the
% coverage of the top $100$ tweets in the test set by SEISMIC. For a grid of
% time, we maintain a shortlist of $500$ tweets with the most
% predicted retweet counts and plot the results in Figure
% \ref{fig:rank}. SEISMIC is able to cover $82$ tweets in the
% first $1$ hour and $93$ tweets in the first $6$ hours. As an anecdote,
% the $5$th most retweeted tweet in this plot is actually the breakout
% tweet \cite{gaddafi-bieber} we showed earlier in Section
% \ref{sec:related-work}. SEISMIC detects this tweet $30$
% minutes after it is posted, while LR and LR-D take more than
% an hour. DPM fails to detect this breakout for the first $6$ hours because the
% power constant $\gamma$ is never less than $-1$.

\begin{figure}[t]
  \centering
  \includegraphics[width = \columnwidth]{rank.pdf}
  \caption{Coverage of top 100 most retweeted tweets.
  %Coverage of the top 100 tweets by shortlist of 500 tweets generated from our \sem model.
    Each row represents a tweet.
    White blocks indicate that a given tweet was not covered by \sem's
    predicted list of top-500 tweets at time $t$, and blue indicates successful coverage.
    }
  \label{fig:rank}
\end{figure}

To compare \sem with other methods, we keep the size of the
predicted lists to be $m =$ 500, and use a larger target list
$L_{500}^{*}$, which is a more difficult task than finding $L_{100}^{*}$.
Figure \ref{fig:coverage} compares the coverage of
different methods against the proportion of retweets seen. After
seeing 20\% of the retweets, \sem covers 65\%
of the shortlist, while LR-D and LR both
cover only 50\%. In general, the dynamic Poisson model fails to
provide accurate predictions and breakout identifications.

Overall, \sem allows for effective detection of breakout tweets. For instance, after seeing around 25\% of the total number of retweets of a given tweet (in other words, after observing a tweet for around 5 minutes), \sem can identify 60\% of the top-100 tweets according to the final retweet counts.


\begin{figure}[t]
  \centering
  \includegraphics[width = \columnwidth]{coverage.pdf}
  \caption{Coverage of top 500 tweets ($L_{500}^{*}$) by various methods.
  \sem exhibits clear improvement over all
  methods after about 10\% of retweets are observed.
  All methods except DPM achieve perfect coverage after 65\% of retweets
  are observed.}
  \label{fig:coverage}
\end{figure}


\subsection{Discussion of model robustness}
\label{sec:comp-with-state}

\sem demonstrates better robustness than the other two point process
based methods --- DPM and RPM. While \sem is not able to make a prediction
for tweets that are in the supercritical state, DPM and RPM are unable
to make predictions when the decay parameter is outside the feasible set ($\gamma < - 1$ for DPM and $\gamma < 0$ or
$\alpha < 0$ for RPM). For example, in
Figure~\ref{fig:breakout}, \sem characterizes the tweet as
supercritical for the first 70min, DPM fails to make a prediction for the first
6 hours and RPM is only able to make a prediction from 30 to 80 minute.

All in all, we find that tweets are in the supercritical regime for
only a very short time and \sem is able to make predictions for most
of the tweets in most of the time. We find that on average, \sem is not able to make a prediction for 1.80\% of the tweets after observing them for 15 minutes. In other words, after 15 minutes, 1.80\% of the tweets are still in the supercritical regime (over all the tweets with at least 50 retweets). This number drops to 1.29\% (0.67\%) after 1 hour (6 hours). As a point of comparison we also note that other methods are not able to make predictions for a much larger fraction of tweets: DPM fails to make a prediction for 6.77\%, 5.79\% and 1.45\%, and RPM fails for 3.45\%, 5.69\% and 15.43\% of the tweets after 15min, 1h, and 6h.


% Compared to regression estimators (LR, LR-D), the point process based
% methods (DPM, RPM, \sem) are usually more sensitive to volatile
% retweet dynamics. An example is the tweet \cite{gaddafi-bieber} in
% Figure \ref{fig:breakout}, for which both DPM and RPM fail to fit a reasonable
% model after the retweet out break starts (around 20
% minutes). For DPM, the estimated power constant $\gamma$ is always greater than $-1$ in the
% first $6$ hours. For RPM, the reinforcement function $r(R_t)$ is not
% enough to explain the information outbreak, so the estimated $\gamma$
% is indeed less than $0$. In contrast, \sem uses an non-parametric
% estimator of $p_t$ and is more robust to information outbreaks. \sem
% fails to make a prediction only if $p_t < 1/(\gamma_t n^{*})$ (see
% Eq. \eqref{eq:new-predict}). This usually means the tweet is in a
% supercritical state and no prediction method could perform well
% at this time.

% Here we compare how often \sem, DPM and RPM fail to make a
% prediction. When making prediction at $15$ minutes, $1$ hour and $6$
% hours for all tweet with at least $50$ retweets, \sem considers
% $1.80\%$, $1.29\%$ and $0.67\%$ of the tweets are supercritical. In
% comparison, DPM fails to make a prediction for $6.77\%$, $5.79\%$ and
% $1.45\%$, and RPM fails for $3.45\%$, $5.69\%$ and $15.43\%$ of the tweets.

Our \sem method is also significantly faster than the RPM model
\cite{shen2014modeling}, which requires to solve a nonlinear
optimization problem every time it predicts. In our implementation, the average running
time per tweet for predicting at every 5 minutes for 6 hours is 0.02s
for \sem and 3.6s for RPM. The reported running time includes both parameter learning and prediction.


%\jure{These plots are great but I assume we will  also put back that ``matrix'' plot where we test the breakout detection}

% \begin{figure*}
% \includegraphics[width=3.4in]{quantile}
% \includegraphics[width=3.4in]{quantileHalfHour}
% \end{figure*}

GenFramework.tex
% !TEX root = ./paper-twitter.tex

In this section, % we describe \sem, a statistical model of information cascades.
%WhileThe social network of concern in this paper is Twitter, but the model here is not limited to this particular network.
we describe \sem and discuss how it can be used for:

\begin{enumerate}[nolistsep]
  \item Estimating the spreading rate of a given information cascade, which we quantify by the post's infectiousness.
  \item Determining whether the cascade is in supercritical (explosive) or subcritical (dying out) state.
  \item Predicting the final size of an information cascade, which is measured by the ultimate number of reshares received by the post that started the cascade.
\end{enumerate}

%We quantify post's velocity of spreading with the rate $\lambda_t$.
% and its influence with the count of retweets $R_t$.
Important quantities in our model are the total number of
reshares $R_t$ of a given post up to time $t$ and the
cascade speed of spreading $\lambda_t$. In our model, $\lambda_t$ is determined by the post
infectiousness $p_t$ and human reaction time. Our goal is to predict $R_\infty$, the final number of reshares.

Another important quantity in our model is the {\em memory kernel}
$\phi(s)$, which quantifies the delay between a post arriving to a user's feed and the user resharing it. Intuitively, infectiousness defines the probability that a given user will reshare a given post, and the memory kernel models user's reaction time. By combining the two we can then accurately model the speed at which the post will spread through the network.
% We proceed by fist defining memory kernel $\phi(s)$, which models human reaction times. Next we define the model of infectiousness $p_t$. And last, we connect the two by describing our self-exciting model. The model enables us to predict the final post popularity $R_{\infty}$ at any point in time.
Table~\ref{tab:notations} summarizes the notation.

\begin{table}[!t]
  \centering
  \begin{tabular}{l | l}
    Symbol & Description \\
    \hline
    $w$ & Post/information cascade \\
    $p_t$ & Infectiousness of $w$ at time $t$ (Section \ref{sec:spread-speed}) \\
    $\phi(s)$ & Memory kernel (Section \ref{sec:human-reaction-time}) \\
    $i$ & Node that contributed $i^\textit{th}$ reshare. \\
         &$i=0$ corresponds to the originator of the post. \\
    % $t_i$ & Time of the $i$th retweet.\\
    $t_i$ & Time of the $i^\textit{th}$ reshare relative to the original
    post.\\
    $n_i$ & Out-Degree of the $i^\textit{th}$ node \\
    $R_t$ & Cumulative popularity by time $t$: $|\{i > 0; t_i \le t\}| $ \\
    $R_{\infty}$ & Final popularity (final number of reshares): $|\{i
    > 0\}|$ \\
    $N_t$ & Cumulative degree of resharers by time $t$: $\sum_{i: t_i\le t} n_i$ \\
    $N_t^e$ & Effective cumulative degree of resharers by time $t$:\\
            & $N_t^e = \sum_{i=0}^{R_t}  n_i \int_{t_{i}}^{t} \phi(s-t_i)ds $\\
    $\lambda_t$ & Intensity of cumulative popularity $R_t$ \\
    $\hat{p}_t$ & Model's estimate of infectiousness $p_t$ at time $t$ \\
    $\hat{R}_{\infty}(t)$ & Model's estimate at time $t$ of final popularity $R_{\infty}$ \\
  \end{tabular}
  \caption{Table of symbols.}
  \label{tab:notations}
\end{table}

%The main subjects we want to study are the stochastic processes $R_t$ and $N_t$, both indexed by time $t$, denoting the total number of re-tweets (re-tweet count) and the cumulative number of followers up to time $t$, respectively. Here we will first explain two important components before presenting our self-exiciting model of $R_t$.


\subsection{Human reaction time}
\label{sec:human-reaction-time}
In order to predict the cascade size, we need to know how long it takes for a person to reshare a post. Knowing the delay allows us to accurately model the speed of a cascade spreading through the network. We consider that the time $s$ between the arrival of a post in a users'
timeline and a reshare of the post by the user is distributed with
density $\phi(s)$. The probability density $\phi(s)$ is also called a memory kernel because it measures a physical/social system's memory of stimuli~\cite{Crane2008}.
%In general, reaction time
%of different individuals do not necessarily have the same
%distribution. For example, some users check the website more
%frequently than others. However, the information cascade is usually
%consists of many users, which allows us to use a single memory kernel
%to model the aggregated behavior.

%Research indicates the response time to letters of Darwin and Einstein can be well approximated by a power law with exponent $\approx 1.5$ \cite{oliveira2005human}.
The distribution of human response time $\phi(s)$ has been shown to be heavy-tailed in social networks~\cite{Barabasi2005}. Usually
the tail of $\phi(s)$ is assumed to follow a power-law with exponent
between $1$ and $2$ or a log-normal distribution~\cite{Crane2008,Zaman2014}.
However, due to the rapid nature of information sharing on Twitter, it
is also natural to expect many instant reaction times. In fact, our exploratory data analysis in Section
\ref{sec:parameter-estimation} confirms that in Twitter, $\phi(s)$ is
approximately constant for the first 5 minutes and then followed by a
power-law decay. Different social networks may have different
distributions of human reaction times. However, $\phi(s)$ only needs
to be estimated once per network and thus we can safely
assume it is given. We describe a detailed estimation procedure of $\phi(s)$ in Section~\ref{sec:parameter-estimation}.

\subsection{Post infectiousness}
\label{sec:spread-speed}

The second component of our model is the post infectiousness. We assume each
post $w$ is associated with a time dependent, intrinsic
infectiousness parameter $p_t(w)$. In other words, $p_t(w)$ models how
likely the post $w$ is to be reshared at time $t$.
%If the context is clear that only one specific tweet is concerned, we
%simply write $p_t(w)$ as $p_t$.
Infectiousness of a post may depend on a combination of factors,
including but not limited to the quality of the post's content, the social network
structure, the current local time, and the geographical location. Instead of assuming a parametric form of $p_t$, we model it
flexibly in a nonparametric way which implicitly accounts for all
these factors. % Our model is able to infer the right value of $p_t$, which accounts for all the factors, as well as how it evolves over time.

Most existing methods studying self-exciting point processes assume
$p_t$ to be fixed over time. Consequently, an important concept is the
{\em criticality} of the process $R_t$. In a self-exciting point process
with constant infectiousness $p_t \equiv p$, there exists a phase transition
phenomenon at certain critical threshold $p^{*}$ such that~\cite{durrett2010probability}:
\begin{enumerate} [nolistsep]
  \item If $p > p^{*}$, then $R_t \to \infty$ as $t \to \infty$ almost surely
  and exponentially fast. This is called the \emph{supercritical} regime.
  \item If $p < p^{*}$, then $\sup_t R_t < \infty$ almost surely. This is
  called the \emph{subcritical} regime.
\end{enumerate}

In reality, $R_t$ is always bounded due to the finite size of the network.
Thus, no supercritical
cascades can exist if $p_t$ is assumed to be a constant. This is
inadequate to model highly contagious tweets and our assumption of
non-constant infectiousness solve this problem as well. Furthermore, as the post gets older the
information becomes outdated and its spreading power (infectiousness) may decrease.
This effect may also be observed as the post spreads
further away from the original poster~\cite{Zaman2014}. Alternatively,
resharing by a highly influential user may increase the
post's infectiousness. Thus, rather than assuming a common evolutionary pattern of $p_t$ for all the tweets, we only assume it
varies smoothly over time and use non-parametric methods to estimate
$p_t$ for each tweet.

\subsection{The SEISMIC model}
\label{sec:self-exiciting-model}

We combine human reaction times and post
infectiousness to derive \sem. In order to link $p_t$ to the post resharing
process $R_t$, we model $R_t$ as a \emph{doubly stochastic
  self-exciting point process}. This is an extension to the standard self-exciting
point process (also called the Hawkes process~\cite{hawkes1971}) which
was initially used to model earthquakes~\cite{ogata1988}.

We first define the intensity $\la_t$ of $R_t$, which simply measures the rate of obtaining an additional reshare at time $t$. More formally:
\begin{equation*}
  \label{eq:1}
\la_t =\lim_{\Delta \downarrow 0} \frac{\P\left ( R_{t+\Delta } - R_t
    = 1 \right )}{\Delta }.
\end{equation*}

In \sem, the intensity $\la_t$ at time $t$ is determined by
infectiousness $p_t$, reshare times $t_i$, node degrees  $n_i$, and
human reaction time distribution $\phi(s)$. The exact relationship
described in Eq.~\eqref{eq:model} is inspired by the theory of Hawkes processes~\cite{hawkes1971}:
% The equation combines infectiousness with the number of exposed users and the time kernel, which quantifies human reaction times:
\begin{equation}
  \label{eq:model}
  \begin{aligned}
  \lambda_t &= p_t \cdot \sum_{t_i \le t,~i \ge 0} n_i \phi(t-t_i), \quad t \ge t_0.
  \end{aligned}
\end{equation}

Intuitively, $\sum_{t_i \le t,~i \ge 0} n_i \phi(t-t_i)$ is the
intensity of the arrival of newly exposed users at time $t$ and its
product with the resharing probability $p_t$ gives the
intensity of reshares at time $t$.

Note that the above point process is called \emph{self-exciting}
because each previous observation $i$ such that $t_i \le t$
contributes to the intensity $\lambda_t$, or equivalently, each
observation increases the intensity in the future. It is further
\emph{doubly stochastic} (or a \emph{Cox process}) because the infectiousness $p_t$ is itself a stochastic process.

Additionally, we assume node degrees $\{n_i\}$ are independent and
identically distributed with mean $n^{*}$. Mean degree $n^{*}$ is
related to the critical threshold $p^{*}$ which is already discussed in Section \ref{sec:spread-speed}. The critical infectiousness threshold takes value $p^{*} = 1 / n^{*}$. We give the proof of this fact in Proposition~\ref{prop:expectation}.

% \subsection{Dynamic classes for tweets}
% Collective human behavior on social networks has gained significant
% attention of scientists. Many studies explain the
% waiting times of human activity on social networks with power law decay
%  \cite{barabasi2005,oliveira2005human}. Each tweet is affected by many
%  factors throughout its life span. Some of those include the tweet quality,
%  popularity of the person who tweets it, tweet time, content etc. Depending on
%  these factors, the propagation behavior of a tweet will determine the number of
%  retweets it gets, which ranges from zero to millions. Therefore, to predict the
%  final re-tweet counts, it is essential to understand this behavior.

% A tweet can be interpreted as a shock to a network where the propagation starts
% from the original node (person who tweeted) and its spreading behavior
% relies on the factors mentioned above. Authors of
%  \cite{Crane2008} characterize such behaviors into four classes.
%  We will be interested in only two of those classes: \emph{Critical} and \emph{Sub-critical} tweets.
% We say that a tweet is in the sub-critical region if its spreading potential is small. On the other hand, we say that a tweet is in the critical region if the spreading potential is quite high. Note that a tweet might

Intro.tex
% !TEX root = ./paper-twitter.tex

% What is our problem: identify breakouts, predict influence
% Why is it intersting or important: interesting because social
% behavior is known to be hard to predict, can be used to detect trending
% topics, useful for medias

% Humanity is embedded in social networks and the information we experience comes to us continuously over time, assembled from many small pieces, and conveyed through social networks.

% Online social networking services, have become an important mechanism by which people discover and consume information online. Often, people discover new information by following each other and then sharing pieces of information with each other.

% Online social networking services give raise to a complex web of human collective behaviors.

% \jure{reorder citations inside ``cite'' command so that references are sorted in increasing order}

% OLD:
%Social networks give rise to complex collective behaviors that emerge spontaneously by uncoordinated actions of many individuals. One particularly interesting example of collective behavior is the process by which information, fads, and rumors spread among people~\cite{rogers95diffusion}. Generally, such phenomena are modeled as information cascades, where people observe actions of others and as a result change their own behavior.

% OLD:
%Information cascades are especially prevalent in today's online social networking services, like Facebook, Youtube and Twitter, which allow their users to post and share content in the form of posts, images, or videos~\cite{dow2013anatomy,hong2011predicting,nowell08letter,suh2010want}. As a user is exposed to posts of others she follows, the user may in turn reshare a post with her own followers. This way large information cascades of post resharing behavior occur in the network.

% NEW
Online social networking services, such as Facebook, Youtube, and Twitter, allow their users to post and share content in the form of posts, images, and videos~\cite{dow2013anatomy,hong2011predicting,nowell08letter,suh2010want}. As a user is exposed to posts of others she follows, the user may in turn reshare a post with her own followers, who may further reshare it with their respective sets of followers. This way large information cascades of post resharing spread through the network.
%As posts are reshared by many users in the network, large information cascades of post resharing behavior can occur.

A fundamental question in modeling information cascades is to predict their future evolution.
Arguably the most direct way to formulate this question is to consider predicting the final size of an information cascade. That is, to predict how many reshares a given post will ultimately receive.

Predicting \hide{the attention or} the ultimate popularity of a post is
important for content ranking and aggregation. For instance, Twitter
is overflowing with posts and users have a hard time keeping up with
all of them. Thus, much of the content gets missed and eventually
lost. Accurate prediction would allow Twitter to rank content better,
discover trending posts faster, and improve % the content placement in
its content-delivery networks.
Moreover, predicting information cascades allows us to gain fundamental insights into predictability of collective behaviors where uncoordinated actions of many individuals lead to spontaneous outcomes, for example, large information outbreaks.
%How can we in real-time estimate content's instant infectiousness?  How do we early identify tweets that will create large information outbreaks? And last, how can we in real-time predict the ultimate popularity of online content?

Most research on predicting information cascades involves extracting
an exhaustive set of features describing the past evolution of a
cascade and then using these features in a simple machine learning
classifier to make a prediction about future growth~\cite{bandari2012pulse,cheng2014can,hong2011predicting,kupavski2012cikm,petrovic2011rt,suh2010want}. However,
feature extraction can be expensive and cumbersome, and one is never
sure if more effective features could be extracted. The question
remains how to design a simple and principled
bottom-up model of cascading behavior. The challenge lies in defining
a model for an individual's behavior and then aggregating the effects
of the individuals in order to make an accurate global prediction.

%%%% OLD INTRO
\hide{
Emerging online social networks, like Facebook, Youtube and Twitter, have greatly facilitated the spread of user-generated content, thanks to their functionality of ``retweet'' or
``share''~\cite{dow2013anatomy,hong2011predicting,nowell08letter,suh2010want}. On
these networks, big or even explosive information cascades can
occur, e.g.\ the tweet described in Figure~\ref{fig:breakout}.
% For example, in March
% 2014, a ``selfie'' photograph of actors at the Oscars awards ceremony
% was posted to Twitter and gained more than 3 million retweets~\cite{selfie}.
%  plots the
% time evolution of a breakout tweet~\cite{gaddafi-bieber}.
Accurate prediction of the ultimate popularity of such contagious user-generated
content is key to applications such as content ranking, trend
forecasting, and understanding the collective human behavior~\cite{bandari2012pulse,cheng2014can,Kwak2010,petrovic2011rt,suh2010want,Szabo2010}.
In particular, our motivating application is to identify breakout
tweets long before they go viral, which can be reformulated into a more general problem: How to accurately
predict the final popularity of an individual tweet, preferably in
an online fashion?

On Twitter, a tweet spreads mainly through the Twitter followers
network, i.e.\ a user is susceptible to the tweet only if someone he/she
follows has posted or retweeted this tweet before. Since tweets with hashtags
may have different diffusion mechanisms, % e.g.\ through recommendations
% as trending topics,
in this paper we only focus on tweets
without hashtags. In its nature, the problem of predicting single tweet is
different from another widely
studied class of problems where information flows freely on the
network, thus all nodes are susceptible to the information of interest
regardless of the network structure. Examples of the latter problems are
hashtag popularity on Twitter~\cite{Matsubara2012rise}, clicks on Youtube videos~\cite{Crane2008}, evolvement of
citation networks~\cite{hunter2011dynamic}, frequencies of memes mentioned on
websites~\cite{rodriguez2013modeling, yang2013mixture,
  zhou2013learning} etc. A more thorough discussion of these work can
be found in Section \ref{sec:related-work}.
% , volumes of queries on search engines~\cite{Matsubara2012rise} etc.

In contrast to the problems mentioned above, the information diffusion
mechanism of an individual tweet has the following distinctive characteristics:
\begin{enumerate}[nolistsep]
\item Tweets have the ``rich-get-richer'' property. The more retweets a
  tweet gets, the more attention it will draw and thus will be more
  likely to be retweeted again.
\item The dynamics of a breakout
  information cascade (\eg, Figure~\ref{fig:breakout}) are extremely
  bursting and unstable, hence imposing parametric assumptions on the
  time series can limit the applicability.
\item Twitter's network is extremely inhomogeneous and thus
  network information, in particular the node degrees (number of
  followers), can play in an important role in a successful model.
\item The sheer volume of tweets being generated every second calls
  for an algorithm efficient in both computing time and storage.
% Predicting for the vast amount of tweets in real time requires an extremely efficient algorithm.
\end{enumerate}

} %end-hide NEW INTRO

% We make the following observations of the information diffusion
% mechanism of an individual tweet on Twitter. Firstly, Twitter's network is
% extremely inhomogeneous and thus the network information, in
% particular the node degrees(number of followers) should play in an
% important role in a successful model. Secondly, tweets have a
% ``rich get richer'' property - the more retweets there are, the more
% attention it will draw. Thirdly, the extremely bursty and unstable
% dynamics of a breakout information cascade as seen in
% Figure~\ref{fig:breakout} suggests we should model the
% infectiousness of a tweet as a time varying process. We develop a
% model that are in line with these observations.



% Humanity is embedded in social networks, which give rise to complex collective behaviors that emerge spontaneously by uncoordinated actions of many individuals. Understanding and predicting collective behaviors has been a central topic in many different fields and has recently raised considerable research interest in many communities including computer science~\cite{bandari2012pulse,Cheng2014,Kwak2010,petrovic2011rt,suh2010want,Szabo2010}, statistics~\cite{Zaman2014}, and applied physics~\cite{oliveira2005human,Pastor-Satorras2014,Lilian2013srep}.

% One particularly interesting example of collective behavior is the process by which information, fads, rumors, and behaviors spread among people~\cite{rogers95diffusion}. Generally, such phenomena are modeled as information cascades, where people observe actions of others and as a result change their own behavior.
% %
% Information cascades are especially prevalent in today's online social networking services, like Facebook and Twitter, which allow
% % enable for the information to spread among their users.
% users to post and share content in the form of textual posts, images, and videos~\cite{dow2013anatomy,hong2011predicting,nowell08letter,suh2010want}. As a user is being exposed to various posts produced by others she follows, the user may in turn reshare the post with her own followers. This way big information cascades of post resharing behavior occur in the network. As a rather extreme example, a ``selfie'' photograph taken by famous actors at the Oscars awards ceremony in March 2014 has been reshared more than 3 million times on Twitter~\cite{selfie}.

% The sheer volume of content in online social networks then brings up
% the question of predicting how much attention a given content will
% ultimately receive. Predicting the attention or the ultimate
% popularity of content is important for content ranking and
% aggregation. For instance, Twitter and Facebook are overflowing with
% posts and users have a hard time keeping up with all of them. Thus, much of the content gets missed and eventually lost. The ability to predict the ultimate popularity of content would allow online social networks to rank content based on its ultimate interestingness, improve the content placement in content-delivery networks, and optimize revenue.  Moreover, predicting popularity of online content is interesting as it allows us to gain fundamental insights into predictability of collective human behaviors where uncoordinated actions of many individuals lead to big spontaneous outcomes, for example, large information outbreaks. How can we in real-time estimate content's instant infectiousness?  How do we early identify tweets that will create large information outbreaks? And last, how can we in real-time predict the ultimate popularity of online content?

% % : How can we quantify its influence and infectiousness? Why do we see different dynamics patterns? Can we, or when can we predict its final influence?

% Most research predicting information cascades involves empirical modeling by extracting a large set of features describing the past evolution of a cascade and then using these features in a machine learning classifier in order to make a prediction~\cite{bandari2012pulse,Cheng2014,hong2011predicting,kupavski2012cikm,petrovic2011rt,suh2010want}. While these works have been able to demonstrate that cascades can in fact be predicted, the question remains how can we build principled bottom-up models of cascading behavior. The challenge here is to define a model of individual's behavior and then aggregate the effects of individuals in order to make a global prediction.
% %
% The difficulty of bottom-up modeling of human collective behavior lies in the unpredictability of individual's behavior~\cite{song2010limits}. There are countless factors that influence individual's actions and building models of individual's behavior with the goal of predicting macroscopic population-level outcomes becomes extremely challenging. However, if there is sufficient population of people participating in a given information cascade, it may indeed be possible to study their aggregated behavior, and as more people are involved, the information cascade becomes more stable and predictable~\cite{Cheng2014,Crane2008}.


% % , which first assumes some models on individual social behavior and then aggregate their effects.
% % Further review of the related work and comparison with our method can be found in Section \ref{sec:related-work}. Here we want to point out that most of these models require a known network and many user features or the information content.

% % One particular interest is the temporal patterns of information cascades and their relationship with human dynamics \cite{Crane2008,Yang2011,Lehmann2012,Cheng2014}.

% % Unlike traditional ways such as word of mouth and newpapers, information can spread much faster nowadays and is not limited by geographical distance or centralized media, thanks to the rapid growth of online social networks.

% % One particular interest is the temporal patterns of information cascades and their relationship with human dynamics \cite{Crane2008,Yang2011,Lehmann2012,Cheng2014}. To state the problem more clearly, we follow the depiction of social network as a graph. Each node in the graph represents a human user and each edge represents a kind of social connection between the users. The edge can be undirected, like friendship in Facebook, or directed, like following relationship in Twitter. Such connection may result from offline relationship (family, friend, acquaintance, etc.) or not (celebrity, network's recommendation, etc.). Social event in such networks is always triggered by an user posting some information (status, photos, tweet, blog article) and then followed by a sequence of sharing actions. Large and even phenomenal information cascades can be formed. As a rather extreme example, a photo taken at Oscars 2014 has received more than 3 million retweets in a few days in Twitter.

% % \begin{table}[htbp]
% %   \centering
% %   \begin{tabular}{c|c|c}
% %     Scale & Behavior & Example: Twitter \\
% %     \hline
% %     micro & individual human & tweet, retweet, favorite \\
% %     \multirow{2}{*}{$\downarrow$} & single cascade & a single tweet \\
% %     & multiple cascades & trending topics, hashtags \\
% %     macro & entire systm & the whole Twitter website \\
% %   \end{tabular}
% %   \caption{Information spread over a social network in different scale.}
% %   \label{tab:micro-macro}
% % \end{table}

% % Most of the related works study single or multiple information cascades can be classified into the next three kinds: 1. descriptive and explatory approach such as \cite{Kwak2010,Yang2011,bakshy2011everyone}; 2. empirical modeling approach such as \cite{petrovic2011rt,bandari2012pulse,Cheng2014}, which usually doesn't involve explicit model of human dynamics; 3. bottom-up modeling approach such as \cite{Crane2008,Zaman2014}, which first assumes some models on individual social behavior and then aggregate their effects. Further review of the related work and comparison with our method can be found in Section \ref{sec:related-work}. Here we want to point out that most of these models require a known network and many user features or the information content.

% \xhdr{Present work}
% In this paper, we focus on predicting the behavior of individual information cascades. Our main goal is to provide a flexible and statistically-sound model to predict the ultimate size of an information cascade spreading in an online social network. We consider the setting where we observe the cascade growing in real-time and at any point of time our model estimates the expected cascade's final size. Our model allows for answering questions like: What will be the final size/popularity of a given information cascade? What is the infectiousness rate of given content at a given time? What content will create big information outbreaks?

% Our paper primarily studies information cascades of tweets being retweeted and spreading in Twitter. However, our model is more general and is not limited to any particular social network. In fact, one of our motivations for this work is to develop a general model that can be used for any type of information outbreak analysis.

\begin{figure}[!t]
  \centering
  \includegraphics[width = \columnwidth]{anec-full-pred.pdf}
%  \vspace{-2mm}
  \caption{First 6 hours of retweeting activity of a popular
    tweet~\cite{gaddafi-bieber} (top). The controversial tweet is
    about the fresh death of dictator Muammar Gaddafi and mentions singer Justin Bieber.
  Interestingly, the car manufacturer Chevrolet Twitter account
  inappropriately retweeted the tweet about 30 minutes after the original
  tweet, which possibly lead to tweet's   sustained popularity.
  %
  Tweet infectiousness against time as estimated by \sem (middle).
  %
  Predictions of the tweet's final retweet count (denoted as ``Truth'') as a function of time
  (bottom). We compare \sem with time series linear regression (LR), ``Observed'' plots the cumulative number of observed retweets by a given time. Notice \sem quickly finds an
  accurate estimate of the tweet's final retweet count.
%   Later in Figure~\ref{fig:breakout-predict} we show how our model
%   can accurately predict tweet's final retweet count after observing it
%   for only about 1 hour. \qz{Let's show it here!}
  %but then quickly removed the retweet due to its controversial nature.
% The vertical red dashed line marks the time that the breakout
%     starts. The horizontal green dotted line in the second plot is
%     the critical threshold, estimated by the reciprocal of average
%     node degree of all the retweeters.
  }
%  \vspace{-2mm}
  \label{fig:breakout}
\end{figure}


\xhdr{Present work}
Here we focus on predicting the final size of an information cascade
spreading through a network. We develop a statistical model based on the theory of {\em self-exciting point
  processes}. A point process indexed by time is called a {\em counting process}
when it counts the number of instances (reshares, in our case) over time. In contrast to homogeneous
Poisson processes which assume constant intensity over time, self-exciting processes assume that all the previous
instances (\ie, reshares) influence the future evolution of the
process. Self-exciting point processes are frequently used to model ``rich get richer'' phenomena~\cite{Matsubara2012rise,mohler2011,yang2013mixture,zhou2013learning}. They are ideal for modeling information cascades in networks because every new reshare of a post not only increases its cumulative reshare count by one, but also exposes new followers who may further reshare the post.


% Our model is based on the theory of {\em self-exciting point
%   processes}. A point process is also called a {\em counting process} when it is indexed by time. A counting process can be thought of as accumulative count of observations (retweets, in our case) over time, so it only takes nonnegative values and is always nondecreasing. And, self-exciting simply means that all the previous observations (\ie, retweets) have influence on the future evolution of the process. This is in contrast to a homogeneous Poisson process, which assumes the intensity of the process is always a fixed constant. Self-exciting point processes are ideal for modeling collective behaviors in networks and especially for modeling information cascades, because every new retweet not only adds $1$ to the cumulative retweet count, but it also exposes new users to the tweet (followers of the retweeter), who can in the future retweet it and further spread the cascade.

We develop \sem (\emph{Self-Exciting Model of Information Cascades})
for predicting the total number of reshares of a given post. In our
model, each post is fully characterized by its {\em infectiousness} which measures the reshare probability. We allow the infectiousness
to vary freely over time in agreement with the observation that the
infectiousness can drop as the content gets stale (see~Figure~\ref{fig:breakout}). Moreover, our model is able to identify at
each time point whether the cascade is in the \emph{supercritical} or
\emph{subcritical} state, based on whether its infectiousness is above
or below a critical threshold. A cascade in the supercritical state is
going through an ``explosion'' period and its final size cannot be
predicted accurately at the current time. On the contrary, a cascade
is tractable if it is in subcritical state. In this case, we are able to predict its
ultimate popularity accurately by modeling the future cascading behavior by a
Galton-Watson tree.

% The main innovation of our approach over the existing literature about self-exciting models~\cite{which models} is that we allow for the infectiousness can change over time. This way a supercritical tweet can transit into subcritical, and vice versa. Furthermore, we can also predict the final retweet count based on the estimated infectiousness.

Our \sem approach makes several contributions:
%brings several advantages over existing approaches:
\begin{itemize}[nolistsep]
% \item {\bf Undemanding assumption:} Our model assumes minimal knowledge of the network. It requires only the degrees of nodes in the graph. Edge information is not needed.
% \item {\bf Generative model:} The model requires practically no training. It
%   uses very few parameters to model the generation of real information cascades.
% \item {\bf No feature extraction:} Our model requires no expensive
%   feature extraction/generation process. The required input data are
%   the times of the retweets. The degrees of the retweeting nodes are
%   optional but may further.
\item {\bf Generative model:} \sem imposes no parametric
  assumptions and requires no expensive feature engineering.
  Moreover, as complete social network structure may be hard to obtain,
  \sem assumes minimal knowledge of the network:
  The only required input is the time history of reshares and the degrees of the
  resharing nodes.
  % are optional but can greatly improve the prediction performance.
\item {\bf Scalable computation:} % The model reduces down
  % to some simple formulae that are easy to compute.
  % , and is thus
  % extremely scalable:
  Making a prediction using \sem only requires computational time linear in the
  number of observed reshares. Since predictions for individual posts
  can be made independently, our algorithm can also be easily
  parallelized. % , and can be updated in real-time
% \item {\bf Real-time update ability:} The model allows for tracing the evolution of a tweet and
%   updating predictions in real-time.
\item {\bf Ease of interpretation:} For an individual cascade, the model synthesizes all its past
  history into a single infectiousness parameter. This infectiousness
  parameter holds a clear meaning, and can serve as input to other applications.
\end{itemize}

% Our model brings several advantages and innovations over existing
% approaches:
% \begin{itemize}[noitemsep]
% \item The model assumes only minimal knowledge of the network as it only requires the information about the degrees of nodes.
% \item The model requires no expensive feature extraction/generation and it only requires input data about the times of the retweets and the degrees of the retweeting nodes.
% \item The model allows for tracing the evolution of a tweet and making predictions in real-time.
% \item The model requires practically no training and includes very few parameters.
% \item The model reduces down to a simple formula that is easy
%   to compute and is thus extremely scalable: To make a
%   prediction the model requires time linear in the number of
%   observed retweets so far.
% \item \jure{Anything else?}
%         % \item The self-exciting point process model is simple compared to many existing methods. No prior information is needed and the computation is very straightforward. In fact, the computation time is linear in the number of retweets.
%         % \item Our model require very minimal features about the process. Only the relative retweet time and number of followers of each retweeter are needed.
%         % \item The training phase of the model is very simple and very few parameters need to be tuned.
% \end{itemize}
% Our closed-form formula is based on the expected retweet count assuming the infectiousness will not change afterwards. A slightly modified version of this formula can be tuned and achieves impressive performance on real data. The model demonstrates a clear improvement over several benchmarks and gives 15\% error in predicting final reshare count after observing the post for one hour.

We evaluate \sem on one month of complete Twitter data, where users post tweets which others can then reshare by retweeting them. % Such retweeting behavior can cause large information cascades to occur.
We demonstrate that \sem is able to predict the final retweet count of
a given tweet with 30\% better accuracy than the state-of-the-art
approaches (\eg, \cite{gao2015modeling}). For reasonably popular tweets, our model achieves 15\%
relative error in predicting the final retweet count after observing
the tweet for 1 hour, and 25\% error after observing the tweet for just 10
minutes. Moreover, we also demonstrate how \sem is able to
identify tweets that will go ``viral'' and be among the most popular
tweets in the future.
% Among the top $500$ most reshared tweets over a week, after
% seeing 20\% of their retweets, we are
% able to cover 65\% of them by maintaining a shortlist of size $500$ over
% time. The best baseline can only cover 50\% of them after seeing the
% same portion of the retweets. \qz{change some numbers} \jure{change
% this to $100$ breakout tweet example. Our numbers are much more
% impressive there.}
By maintaining a dynamic list of 500 tweets over time, we are able to
identify 78 of the 100 most reshared tweets and 281 of the 500
most reshared tweets in just 10 minutes after they are posted.
% \jure{change this to $100$ breakout tweet example. Our numbers are
%   much more impressive there.} \qz{It's true, but so do the
%   baselines... This task is much easier than predicting the actual
%   number or actual rank}

The rest of the paper is organized as follows: Section \ref{sec:related-work} surveys the related work. Section~\ref{sec::genFrame} describes \sem, and Section~\ref{sec::theory} shows how the model can be used to predict the final size of an information cascade. We evaluate our method and compare its performance with a number of baselines as well as state-of-the-art approaches in Section~\ref{sec:experiments}. Last, in Section \ref{sec:discuss}, we conclude and discuss future research directions.

%We then start by describing our model of individual human behavior (Section \ref{sec:human-reaction-time}) and then proceed to model the infectiousness of a tweet (Section \ref{sec:spread-speed}). Next we develop a self-exciting model for retweets (Section \ref{sec:self-exiciting-model}) and describe how to estimate infectiousness, use it to characterize super-/sub-criticality of a tweet, and ultimately predict the final retweet count (Section \ref{sec::theory}); We compare our method with a number of baselines on complete Twitter data (Section \ref{sec:experiments}); Finally, in Section \ref{sec:discuss}, we briefly discuss the proposed method along with some future research directions.






% We are only interested in sharing actions inside the network. For
% example in Twitter, the primary social network considered in this
% paper, we are only interested in retweets of the original tweet or an earlier retweet.

macros.tex

\newtheorem{theorem}{Theorem}[section]
\newtheorem{claim}[theorem]{Claim}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{assumption}{Assumption}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}{Definition}
\newtheorem{remark}{Remark}
\newtheorem{note}{Note}



\long\def\mquestion#1{{\red #1}}
\long\def\tocheck#1{{\blue #1}}  % To print colors

\newcommand{\todo}[1]{\textcolor{red}{[TODO] #1}}
\newcommand{\commentout}[1]{}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%***********************  COMMANDS
%
\def\l{\ell}
\def\ind{\mathbbm{1}}
\def\X{\mathcal{X}}
\def\HX{\widehat{\mathcal{X}}}
\def\S{\mathcal{S}}
\def\hX{\hat{X}}
\def\hx{\hat{x}}
\def\Q{\bold{Q}}
\def\I{\mathcal{I}}
\def\t{\tau}
\def\p{\hat{p}}
\def\D{D_{\text{KL}}}
\def\e{\epsilon}
\def\la{\lambda}
\def\d{\delta}
\def\dh{\dot{h}}
\def\J{\mathcal{J}}
\def\th{{\theta}}
\def\reals{{\mathbb R}}
\def\naturals{{\mathbb N}}
\def\<{\langle}
\def\>{\rangle}
\def\E{{\mathbb E}}
\def\P{{\mathbb P}}
\def\identity{{\mathbf I}}
\def\normal{{\sf N}}
\def\Sig{{\boldsymbol \Sigma}}
\def\O{{\mathcal O}}
\def\F{{\mathcal F}}
\def\D{{\mathcal D}}
\def\MSE{{\rm MSE}}
\def\argmin{{\rm argmin}}

\newcommand{\defeq}{\vcentcolon=}
\newcommand{\eq}[1]{\begin{align}#1\end{align}}
\newcommand{\eqn}[1]{\begin{align*}#1\end{align*}}

paper-twitter.tex
\documentclass{sig-alternate-2013}
\usepackage{color}
\usepackage{graphicx}
\usepackage{multirow}
\usepackage{times}
\usepackage{url}
\usepackage{enumitem}
\usepackage{algpseudocode, algorithm}
\usepackage{xspace}
\usepackage[normalem]{ulem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%The following lines are added as required by %%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%http://www.sheridanprinting.com/typedept/kdd.htm#L%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newfont{\mycrnotice}{ptmr8t at 7pt}
\newfont{\myconfname}{ptmri8t at 7pt}
\let\crnotice\mycrnotice%
\let\confname\myconfname%

\permission{Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from Permissions@acm.org.}
\conferenceinfo{KDD'15,}{August 10-13, 2015, Sydney, NSW, Australia.}
\copyrightetc{\copyright~2015 ACM. ISBN \the\acmcopyr}
\crdata{978-1-4503-3664-2/15/08\ ...\$15.00.\\
DOI: http://dx.doi.org/10.1145/2783258.2783401}

\clubpenalty=10000
\widowpenalty = 10000
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\def\Title {SEISMIC: A Self-Exciting Point Process Model \\ for Predicting Tweet Popularity}

\input{macros}

%\newcommand{\note}[1]{{{\textcolor{red}{#1}}}}
\newcommand{\hide}[1]{}
\newcommand{\xhdr}[1]{\vspace{1.7mm}\noindent{{\bf #1.}}}
\newcommand{\eg}{\emph{e.g.}}
\newcommand{\ie}{\emph{i.e.}}
\newcommand{\jure}[1]{{\color{magenta}\bf[J: #1]}}
\newcommand{\qz}[1]{{\color{blue}\bf[QZ: #1]}}
\newcommand{\murat}[1]{{\color{green}\bf[Murat: #1]}}
\newcommand{\hera}[1]{{\color{cyan}\bf[Hera: #1]}}
\newcommand{\sem}{{\sc{Seismic}}\xspace} % model name
%SESMIC (Self-Exciting Model of Information Cascades)

%\graphicspath{{../plot/}}
\graphicspath{{./}}

\begin{document}

\title{\Title}

\numberofauthors{5} %  in this sample file, there are a *total*
% of EIGHT authors. SIX appear on the 'first-page' (for formatting
% reasons) and the remaining two appear in the \additionalauthors section.
%
%\numberofauthors{1}
\author{
% \alignauthor Qingyuan Zhao, Murat A. Erdogdu, Hera Yu He, Anand
% Rajaraman, Jure Leskovec \\
%         \affaddr{Stanford University} \\
%         \email{\{qyzhao, erdogdu, yhe1\}@stanford.edu, \{anand, jure\}@cs.stanford.edu} \\
\alignauthor
Qingyuan Zhao\\
      \affaddr{Stanford University}\\
      \email{qyzhao@stanford.edu}
%2nd. author
\alignauthor
Murat A. Erdogdu\\
      \affaddr{Stanford University}\\
      \email{erdogdu@stanford.edu}
%3rd. author
\alignauthor
Hera Y. He\\
      \affaddr{Stanford University}\\
      \email{yhe1@stanford.edu}
\and  % use '\and' if you need 'another row' of author names
%4th. author
\alignauthor
Anand Rajaraman\\
      \affaddr{Stanford University}\\
      \email{anand@cs.stanford.edu}
%5th. author
\alignauthor
Jure Leskovec\\
      \affaddr{Stanford University}\\
      \email{jure@cs.stanford.edu}
%% 6th. author
%\alignauthor Charles Palmer\\
%       \affaddr{Palmer Research Laboratories}\\
%       \affaddr{8600 Datapoint Drive}\\
%       \affaddr{San Antonio, Texas 78229}\\
%       \email{cpalmer@prl.com}
}
%\date{30 July 1999}

\maketitle
\begin{abstract}
\input{abstract}
\end{abstract}

\vspace{2mm}
\noindent {\bf Categories and Subject Descriptors:} H.2.8 {\bf
[Database Management]}: Database applications---{\it Data mining}

\noindent {\bf General Terms:} Algorithms; Experimentation.

\noindent {\bf Keywords:} information diffusion; cascade prediction;
self-exciting point process; contagion; social media.

\section{Introduction}
\label{sec:introduction}
\input{Intro}

\section{Related Work}
\label{sec:related-work}
\input{relatedWork}

\section{\!\!\! Modeling Information Cascades}
\label{sec::genFrame}
\input{GenFramework}

\section{\!\!\!\!\! Predicting Information Cascades}
\label{sec::theory}
\input{Theory}

\section{Experiments}
\label{sec:experiments}
\input{Experiments}
% \jure{For experiments: Please expand section 5.5.2 (breakout tweets). Motivate the task, explain the setting and the evaluation, then explain the results. Feel free to use xhdr command to separate the section into smaller subsection.

% For section 5.5.1. we could also comment on the scalability of our method and how it compares to the baselines.
% }

\section{Conclusion and Future Work}
\label{sec:discuss}
\input{Discussion}

\section*{Data and Software}
The \sem software and the dataset we use in Section
\ref{sec:experiments} can be found in
\url{http://snap.stanford.edu/seismic/}. The R package of our
algorithm is also available on \url{http://cran.r-project.org/web/packages/seismic}.

\section*{Acknowledgements}
The authors would like to thank David O. Siegmund for his constructive
suggestions and Austin Benson, Bhaswar B. Bhattacharya, Joshua Loftus
for their helpful comments. This research has been supported in part by NSF
IIS-1016909,              % NSF with Jon (Sep 2013)
CNS-1010921,              % NSF with Madhav (Sept 2015)
IIS-1149837,              % NSF CAREER (Dec 2015)
IIS-1159679,              % NSF Sentiment (Sep 2015)
ARO MURI,                 % (Sep 2015)
DARPA SMISC, DARPA SIMPLEX,
Stanford Data Science Initiative,
Boeing,
Facebook,
Volkswagen,
and Yahoo.

\bibliographystyle{abbrv} %% Jure: Please don't change this. ACM says we should use ABBRV style
\bibliography{ref}

\end{document}
relatedWork.tex
% !TEX root = ./paper-twitter.tex

The study of information cascades is a rich and active
field~\cite{rogers95diffusion}. Recent models for predicting size
of information cascades are generally characterized by two types of approaches, feature based methods and point process based methods.

Feature based methods first extract an exhaustive list of potentially relevant features, including content features, original poster features, network structural features, and temporal features \cite{cheng2014can}.
Then different learning algorithms are applied, such as simple
regression models~\cite{Agarwal2009,cheng2014can}, probabilistic
collaborative filtering~\cite{zaman2010predicting}, regression
trees~\cite{bakshy2011everyone}, content-based models~\cite{naveed2011bad}, and passive-aggressive algorithms~\cite{petrovic2011rt}.
There are several issues with such approaches: laborious feature engineering and extensive
training are crucial for their success, and the performance is highly
sensitive to the quality of the
features~\cite{bandari2012pulse,suh2010want}. Such approaches also
have limited applicability because they cannot be used in real-time
online settings---given the massive amount of posts being produced every second, it is practically impossible to extract all the necessary features for every post and then apply complicated prediction rules.
%
In contrast, \sem requires no feature engineering and results in an
efficiently computable formula that allows it to predict the final
popularity of millions of posts as they are spreading through the
network.

The second type of approach is based on point processes, which directly models the formation of an information cascade in a network.
% Poisson process, characterized by a constant
% intensity $\lambda$, is the simplest form of point process.
Such models were mostly developed for the complementary problem of
network inference, where one observes a number of information cascades
and tries to infer the structure of the underlying network over which
the cascades propagated~\cite{daneshmand14netrate, du2012learning, manuel13pathways,rodriguez2013modeling, manuel13dynamic, hunter2011dynamic, yang2013mixture,zhou2013learning}.
%shaping14nips,
These methods have been successfully applied to study the spread of memes on
the web~\cite{du2012learning,rodriguez2013modeling,yang2011,yang2013mixture} as well as hashtags on Twitter~\cite{zhou2013learning}. In contrast, our goal is not to infer the network but to predict the ultimate size of a cascade in an observed network.
% Also, our modeling of a self-exciting individual tweet with one-dimensional Hawkes process is different from modeling mutually-exciting node activities with multi-dimensional Hawkes process \cite{shaping14nips, yang2013mixture,zhou2013learning}.


% Many successful point process based algorithm have been proposed for
% network inference using survival theory \cite{rodriguez2013modeling,
%   du2012learning, hunter2011dynamic} and muldimensional Hawkes process
% \cite{zhou2013learning, yang2013mixture}. However, the focus of
% network inference problems is to learn the unobserved network from
% observed information diffusion, and to make predictions based on the inferred network.
% Although closely related, these network inference methods are not
% directly applicable for our problem. Models proposed in
% \cite{rodriguez2013modeling, du2012learning, hunter2011dynamic,
%   zhou2013learning, yang2013mixture} view the spread of a
% meme or hashtag $m$ on a network with $I$ nodes as a multidimensional point process with intensity
% $\lambda_{m, i}, i = 1, \cdots, I$, usually parametrized with some network
% parameters, the maximum likelihood
% estimation of which are obtained with various optimization techniques. However,
% network inference is feasible only for highly interactive
% networks, like citation network \cite{hunter2011dynamic} or
% hot websites \cite{rodriguez2013modeling} with frequent
% information like memes \cite{rodriguez2013modeling, du2012learning},
% or aggregated information like hashtags(or topics)
% \cite{zhou2013learning}, and not feasible for predicting the more noisy individual
% tweets that scatters over the whole network.

A major distinction between our model and existing methods based on
Hawkes processes ({\it e.g.}, \cite{Matsubara2012rise,mohler2011,yang2013mixture,Zaman2014,zhou2013learning}) is that we assume the process intensity $\lambda_t$ depends on another
stochastic process $p_t$, the post infectiousness. In other words, we
allow the infectiousness to change over time. Moreover, some of these
methods \cite{Zaman2014} rely on computationally expensive Bayesian inference, while our method has linear time complexity.
%One of our contributions is to develop a nonparametric estimator of $p_t$ (see Section \ref{sec:estimation-infectiousness}), which can be useful in other applications as well.
% Probably the most related to our work here is the recently published
% work by Gao {\em et al.}~\cite{gao2015modeling}, which tackles
% exactly the same problem as we do, but their method makes
% restrictive parametric assumptions and does not consider the network
% structure, which limits its predictive ability. We experimentally
% compare \sem with \cite{gao2015modeling} in
% Section~\ref{sec:experiments}.
Another recently proposed related work is \cite{gao2015modeling},
which also takes the point process approach and directly aims to
predict tweet popularity. However, their method makes restrictive
parametric assumptions and does not consider the network structure,
which limits its predictive ability. We compare \sem with
\cite{gao2015modeling} in Section~\ref{sec:experiments} and demonstrate a 30\% improvement.



%Just recently published work by Gao et al.~\cite{gao2015modeling} tackles exactly the same problem as we do here, but the method makes restrictive parametric assumptions and does not consider the network structure, which limit its predictive ability. We experimentally compare \sem with \cite{gao2015modeling} in Section~\ref{sec:experiments}.


%Most related to our work here are work of Matsubara et al.~\cite{Matsubara2012rise} and Zaman et al.~\cite{Zaman2014} in this category proposed SpikeM to unify the temporal variation patterns found in \cite{Yang2011}. However, they model the driving force of spikes with exogeous factors that are nonexistent in individual tweets. Another predictive approach \cite{Zaman2014} proposes a Bayesian model of the point process, however its inference relies on Markov Chain Monte Carlo which is computationally infeasible for real applications. %  assumes the % network allow free information flow and all nodes are susceptible to
% external shock, which is not true for single tweets driven by
% retweets originated from users' timeline.
% \qz{criticize the bayesian paper as well.}

% Empirical study by
% Yang et. al. \cite{Yang2011} found six patterns of temporal variation
% in online media, which provides good insights but are too crude for
% single tweet prediction. Recently Matsubara et.
% al. \cite{Matsubara2012rise} proposed SpikeM to model rise and fall
% patterns of information diffusion. Their model assumes a network where
% information flows freely and all nodes are susceptible. The assumption is true for
% hashtags in Twitter or memes on websites,
% but not true for single tweets that can only be seen on users' timeline.

% Recently \cite{gao2015modeling} proposed an interesting reinforced Poisson
% process model for predicting individual tweet popularities. At time $t$ the
% intensity of tweet $m$ at the $k$th retweet is modeled as
% $\lambda_m(t, k) = c_mf_m(t)r_m(k)$, where $c_m$ is the intrinsic
% infectiousness parameter for tweet $m$, $f_{m}(t)$ is a power law
% decay function and $r_m(k)$ is the reinforcement function that captures
% the ``rich get richer phenomenon''. We compare its performance with
% our model in Section \ref{sec:experiments}.



%  which is in line with real work observation (people's
% interests die out). And in constrast with somewhat arbitrary choice of
% time decaying kernel functions in \cite{zhou2013learning, yang2013mixture},
% we provide a systematic way for estimating the kernel function. Rather
% than imposing specific parametric forms \cite{gao2015modeling} or
% undue assumptions like homogeneous network \cite{Matsubara2012rise}, our
% model is designed to capture the mechanism of the spreading of a
% tweet.








% \murat{The breakout tweet about Justin Bieber simply suggests to kill
%   him. We might want to find some other example.}

% \qz{I don't agree. I think this is actually a good example that
%   Twitter can use our algorithm to detect this controversial tweet
%   sooner. They may take furthr actions if they find it necessary, like
% the white house is bombed tweet. I will add this into the text.}


% Many empirical methods have been proposed to predict the popularity of
% information cascades and the aggregate volume of online actions.
% These methods are characterized as
%  empirical since they do not contain any modeling of human
% dynamics. For instance, \cite{Agarwal2009} studies spatio-temporal
% models for estimating click-through rate using dynamic linear
% regression. As for predicting the probability of a retweet between two
% users, many sophisticated algorithms have been proposed including probabilistic
% collaborative filtering model \cite{zaman2010predicting}, regression
% trees \cite{bakshy2011everyone}, content-based analysis
% \cite{naveed2011bad}, and a machine learning approach based on the
% passive-aggressive algorithm \cite{petrovic2011rt}. Recent
% attempts of cascade prediction \cite{cheng2014can,hong2011predicting} use a variety of
% learning methods including linear regression, naive Bayes, SVM,
% decision trees and random forest with different many kinds of features,
% including content features, original poster/resharer features,
% structural features of the cascade and temporal features. Some earlier
% articles \cite{bandari2012pulse,suh2010want} point out the
% importance of feature extraction in these empirical methods.


% Another related approach focuses on the structural and temporal
% features \cite{Zaman2014}. Their hierarchical Bayesian model of the
% stochastic cascade process bears some similarity to our
% model. However, the problem they consider is the prediction of the
% whole retweet path of a small number of manually selected tweets. (The training and test sets total 52 tweets.) In order to find the posterior distribution of the
% final retweet count, they use a computationally intensive Markov Chain
% Monte Carlo (MCMC) based training which cannot scale to large and real-time applications.

\hide{
, due to the following reasons:
%\qz{is this making the related work section too long?}
\begin{itemize}[noitemsep]
\item Theoretically, \cite{Sornette2003} derive all possible
shapes of the burst if the memory kernel is power-law. Empirical
studies such as \cite{Yang2011} find many clusters of information
cascades that cannot be well explained by this model.
% hardly true in real examples. For example, for multiple
% information cascades (such as a trending topic in Twitter), \cite{Yang2011}
% find $6$ clusters of information cascades in Memetracker according to
% their temporal patterns. Only the second cluster is symmetric and the
% third cluster may be explained by a large exogeneous shock, but all
% the other clusters cannot be well explained by the model in \cite{Sornette2003}.
\item The stochastic process is assumed to be stationary in their
  model, which is very unlikely for breakout tweets. For example, Figure
  \ref{fig:breakout} shows the time evolution of a breakout
  tweet \cite{gaddafi-bieber}\footnote{\footnotesize The
  tweet is related to the death of Muammar Gaddafi and teenage
  singer Justin Bieber. It became very controversial after the official
  Twitter account of the car manufacturer company Chevrolet retweeted but
  quickly deleted the retweet later, which happens about an hour after
  the original tweet had been posted.}. This
  demonstrates that the dynamics of a breakout information cascade can
  be extremely bursting and unstable.

  % \begin{figure*}[htbp]
  %   \centering
  %   \begin{subfigure}[h]{.9\textwidth}
  %   \includegraphics[width = \textwidth]{../plot/anec}
  %   \caption{The histogram of retweet times of the tweet.}
  %   \end{subfigure}
  %   \\
  %   \begin{subfigure}[h]{.9\textwidth}
  %   \includegraphics[width = \textwidth]{../plot/anec-p}
  %   \caption{The infectiousness of the tweet over time estimated by our
  %     model.}
  %   \end{subfigure}
  %   \caption{Demonstration of the time evolution of a breakout tweet.}
  %   \label{fig:breakout}
  % \end{figure*}


\item \cite{Crane2008} assumes the burst is the result of either an
  endogenous or an exogenous shock. For a sharing process such as
  the retweet process considered in this paper, the external sources
  outside Twitter contribute very little to the cascade most of the time.
\end{itemize}

} %end-hide

% to predict the path of retweet counts. Their data-set
% consists of 52 different tweets which are manually collected from Twitter.
% The authors assume that the data-set includes information about
% the reaction times, namely, the time elapsed between a retweet
% and its parent (re-)tweet. Note that this information may not be
% available, as in the case of Twitter's own database CITE.
% Also, training their model requires computationally inefficient techniques such as
% Markov Chain Monte Carlo (MCMC).

% The factors (features) that affect the re-tweetability of a tweet
%  is studied by the authors of .
%   Here, re-tweetability refers to the popularity in our terminology.
%  A generalized linear model (GLM) based approach is
%  used for the feature analysis.
% In the paper \cite{}, authors suggest to extract
% features per online content and use those to predict the range of
% popularity. Similarly,
% %
% the paper \cite{hong2011predicting} constructs the classification
% problems: 1- A binary classification to predict whether a tweet
% will be re-tweeted or not, 2- A multi-class classification to predict
% the volume of the re-tweets that a tweet will receive. This method
% is similar to one of the benchmarks we compare our estimator to.
% We will discuss this method in detail in Section \ref{sec:baseline-estimators}.

% The authors of \cite{Yang2011} study the temporal patterns in
% online media and how the popularity of a content grows and
% decays over time.
% The paper focuses on a time series clustering method in order to
% classify the different behavior of contents over time.
% They investigate the proposed ideas on Twitter data set where
% they find that there
% are a few classes of apparent decays in popularity of a content. \\

Theory.tex
% !TEX root = ./paper-twitter.tex

%\section{Details of the Model}\label{sec::theory}

In this section we describe how to perform statistical inference for the self-exciting
model of information cascades introduced in the previous section.
Specifically, we discuss how \sem estimates the
infectiousness parameter $p_t$ and then predicts the ultimate size of
the cascade $R_{\infty}$.

Throughout this section, we make a technical assumption that
the followers of all the resharers are disjoint, so we can use a tree
structure to describe the information diffusion (Figure
\ref{fig:descendants}).
%, which can be viewed as an approximation to the real network.
%may not be true in general,
%but is
%roughly correct for highly influential
%tweets because the overlap of followers is low. Indeed, the
The conclusions made in this section remain valid even if resharers are not disjoint.
In this case, we can replace the node degree $n_i$ with the total
number of newly exposed neighbors of node $i$ (the followers of
$i$-th resharer who do not follow the first $i-1$ resharers).

\subsection{Estimating post infectiousness}
\label{sec:estimation-infectiousness}

We first define the {\em sample-function density}, which plays a central
role in estimating self-exciting point processes~\cite{snyder2011}.
Let's denote $\mathcal{F}_t = \sigma \left( \{ (n_i, t_i)
  \}_{i=0}^{R_t} \right)$ as the $\sigma$-algebra generated by all the
information available by time $t$: the times $t_i$ of all the reshares up to time $t$
and the number of followers (\ie, node degree) $n_i$ of the $i$-th
user to reshare.
Sample-function density is defined
as the joint probability of the number of reshares in the time interval
$[t_0, t)$ and the density of their occurrence times.

To motivate our estimator of $p_t$, we first consider the case where the
infectiousness parameter remains constant over time, \ie, $p_t \equiv p$.
Later we will relax this assumption and allow $p_t$ to vary over time.

In \sem, % the probability that the number of
% reshares in $[t_0, t)$ takes value $r$, given the previous reshare times, is $\P(R_t = r
% | \mathcal{F}_t)$, and the density of the occurrence times is
% $\P(t_1, \ldots t_r|\mathcal{F}_{t_0})$.
% By using the intensity function
% $\lambda_t$, the sample-function density can be expressed as
% \cite[Thm. 6.2.2]{snyder2011}:
the sample-function density can be expressed using the intensity
$\lambda_t$ as \cite[Thm. 6.2.2]{snyder2011}
\begin{equation}
  \label{eq:likelihood}
  \begin{aligned}
  \P(R_t = r, t_1, \ldots, t_r) =% & \exp \left\{ -
%     \int_{t_0}^t \lambda_s ds + \int_{t_0}^t \ln \lambda_s d R_s
%   \right\} \\
% =&
\prod_{i=1}^{R_t} \lambda_{t_i} \cdot \exp \left \{
  - \int_{t_0}^{t} \lambda_s ds \right \}. \\
    \end{aligned}
\end{equation}
% So
% \begin{equation}
%   \label{eq:log-sample-func}
%   \log p(\{ R_s:t_0 \le s < t \}) = R_t \log p - \left( \int_{t_0}^t
%   N^{e}_s ds
%   \right) \cdot p + \mathrm{const}
% \end{equation}
By taking derivative of the log of Eq.~\eqref{eq:likelihood} and combining it with Eq.~\eqref{eq:model}, we obtain the maximum likelihood estimate (MLE) of $p_t$:
\begin{equation}
  \label{eq:mle}
  \p_t \ =\ \frac{R_t}{\sum_{i=0}^{R_t} n_i \int_{t_{i}}^{t} \phi(s-t_i)
     ds }
\end{equation}

The above equation forms the basis of \sem as it allows us to
estimate the infectiousness $\p_t$ at any given time $t$. Moreover, a
confidence interval of $p_t$ can also be obtained~\cite{snyder2011}.

% Notice that in the calculations above, we implicitly assume node
% degrees $n_0, n_1, \ldots$ are given and related to the process
% through Eq.~\eqref{eq:model}.

The denominator in Eq. \eqref{eq:mle}, denoted as $N_t^e$ hereafter,
can be interpreted as the accumulative
``effective'' number of exposed users to the post. The numerator $R_t$ is the current number
of reshares of the post. To shed more light on our
estimator, we take $t \rightarrow \infty$, which leads to:
\begin{equation}
\label{eq:p-infty}
\p(\infty) = \frac{1}{\frac{1}{R_{\infty}}\sum_{j=0}^{R_{\infty}}
  n_j } \approx \frac{1}{n_{*}}
\end{equation}
Thus, by assuming the infectiousness $p_t$ to be a constant over
time, one would essentially assume that most posts have the same
infectiousness $1/n_{*}$. However, such assumption is unrealistic as it
cannot explain the bursty and volatile dynamics information cascades (\eg, Figure \ref{fig:breakout}). % Thus we next show, how to allow infectiousness $p_t$ to vary over time.
%Note that the above approximation is true for most of the realizations
%such that $R_{\infty}$ is large.
%If a post was created by a
%high-degree node, then $n_0$ is very large, and hence $\p(\infty)$
%could in fact be smaller than $1/n_{*}$.

This undesirable consequence of assuming constant $p_t$ is another
motivation for allowing $p_t$ to vary over time. To estimate $p_t$ in this case, we smooth the MLE in Eq. \eqref{eq:mle} by only
using observations close to time $t$ to estimate $p_t$. In particular,
we rely on a sequence of one-sided kernels $K_t(s)$, $s >
0$, indexed by time $t$. We use these kernels to weight the reshares
and the weighted estimate of $p_t$ is given by
\begin{equation}
  \label{eq:mle-kernel}
\begin{aligned}
  \p_t &= \frac{\int_{t_0}^t K_t(t - s) d R_s}{\int_{t_0}^t K_t(t - s)
    d N^e_s } \\
&= \frac{\sum_{i=1}^{R_t} K_t(t - t_i)}{\sum_{i=0}^{R_t}
    n_i\int_{t_i}^t K_t(t - s) \phi(s - t_i) ds}\, .
%\overset{\Delta}{=} \frac{RW_t}{NW^e_t}
\end{aligned}
\end{equation}

Notice that when $K_t(s) \equiv 1$ the estimator reduces to the MLE we derived in Eq.~\eqref{eq:mle}. In \sem we use a triangular kernel with growing window size $t/2$ as weighting kernel $K_t(s)$:
\begin{equation}
  \label{eq:weighting-kernel}
  K_t(s) = \max \left\{1 - \frac{2s}{t}, 0\right\}, \ \ \ \ s >0.
\end{equation}

We chose the triangular kernel because it has properties important for our application.
First, the kernel discards all posts
that are older than $t/2$. In particular, it quickly discards the
unstable and potentially explosive period at the beginning, which if included, would
introduce an upward bias to $p_t$.
Second, the kernel takes into account posts in
a larger window size as time $t$ increases. According to
our experiments, the growing window size helps to stabilize $\hat{p}(t)$
%the estimate of the infectiousness parameter
compared to a fixed window size.
Third, for reshares
within the window, the kernel up-weights the most recent posts and
gradually down-weights older posts. This keeps our estimator
$\hat{p}(t)$ closer to the ever-changing true $p_t$.
%, in order to  more reflective of most recent activities.
And last, as $K_t(s)$ is piece-wise linear, the integral $\int K_t(t
  - s)\phi(s - t_i) ds$ has a closed form for
many different functions $\phi(s)$ including the one we use for
Twitter in our experiments, see Section \ref{sec:experiments}.


%%%%%%
%%%%%%
\subsection{Predicting final popularity}
\label{sec:predict-influence}

Having described the procedure for inferring the post infectiousness,
we now need to account for the network structure in order to predict
how far the post is going to spread across the network.
%Following, we can
%predict the post's {\em final} reshare count at any point in its lifetime.

For simplicity, let us assume the post is first posted at time $0$,
\ie, $t_0 = 0$. Consider we have observed the post for $t$ time units
and our goal now is to predict the post's final reshare count, $R_\infty$, based on the information we have observed so far, $\mathcal{F}_t$.
% Note that the stochastic process $R_s$ is a right-continuous counting process and
% the retweet times can be obtained by
% $t_i = \inf \{ s\geq 0\ |\  R_s = i \}$, for $i = 0,1,...,R_t$.

The following proposition shows how to compute the expected final
reshare count of a post. The main idea is to model an information
cascade spreading over the network with a branching process that
counts the reshare number of a post, as illustrated in Figure \ref{fig:descendants}.
Predictor for $R_\infty$ used by \sem can be stated as follows:

\begin{proposition}\label{prop:expectation}
% Assume that the data $\mathcal{F}_t$ is known at time $t$.
% Further, assume that the degrees in the random directed graph are i.i.d. random variables with
% expectation $n_*$ and
% the probability that a certain piece of information is shared to a
% neighbor is
Assume the (out-)degrees in the network are i.i.d. with expectation
$n_*$ and the infectiousness parameter $p_s$ is a constant $p$ for $s
\ge t$. Then, we have
\begin{equation}
\E[R_{\infty}|
\ \mathcal{F}_t]
=\left\{
  \begin{aligned}
&R_t + \frac{p (N_t - N^e_t)}{1 - p n_{*}},\!\!&\mathrm{if~} p <
\frac{1}{n_{*}}, \\
&\infty, ~&\mathrm{if~} p \geq \frac{1}{n_{*}}.
  \end{aligned} \right.
\label{eq:predict}
\end{equation}
\end{proposition}
%\begin{remark}
%\label{rmk:1}
%Proposition \ref{prop:expectation} assumes that the probability that a post spreads to a follower is constant $p$. In general, the assumption may not hold, however, when $p$ varies over time, the analysis of the resulting diffusion tree and the computation of the corresponding expectation becomes extremely involved. This case is indeed an interesting line of research which we leave to future work.
%\end{remark}

\begin{proof}
% We derive Eq.~\eqref{eq:predict}, which allows us to predict the expected final reshare count, as follows.
First, we consider the case where $p < 1/n_*$.
We define a sequence of random variables
$\{Z_{1},Z_{2},Z_{3},\ldots\}$ that models the future information
diffusion tree, as illustrated in Figure \ref{fig:descendants}. In
this tree, $Z_k$ denotes the number of reshares made by the $k^\textit{th}$ generation descendants (counting from generation $R_t$ onward). % Our intuition is as follows: We have just observed the cascade up to time $t$ and now aim to model how the cascade will spread in the future. We model this as a branching process, where
Thus, the 1$^\textrm{st}$ generation descendants $Z_1$ refers to the
number of new reshares generated by the posts created before time $t$,
the 2$^\textrm{nd}$ generation descendants $Z_2$ refers to the reshares of the posts of the 1$^\textrm{st}$ descendants, and so on.
Notice that the summation over the $Z_k$'s gives the post's final
reshare count $R_{\infty} = R_t + \sum_{k=1}^{\infty} Z_k$. In the
following we use descendants $Z_k$ only for deriving
Eq. \eqref{eq:predict} and emphasize that our final estimator does not
require explicit network structure information.

\begin{figure}[t]
\centering
\includegraphics[width=0.9\columnwidth]{graph.pdf}
\caption{\label{fig:descendants} An illustration of the information
  diffusion tree. We observe the cascade up to time $t$ (denoted by a dashed line)
  and the question is how the cascade tree is going to grow in the future.
  We define variables $Z_k$ which denote the number of reshares
  caused by the $k^\textit{th}$ generation descendants. Using variables $Z_k$
  the final reshare count $R_{\infty}$ can then be simply computer as $R_t + \sum\limits_{k = 1}^{\infty} Z_k$.}
\end{figure}

Given $Z_{1}$, the sequence of random variables $Z_{k}$ defines a
Galton-Watson tree with the \emph{offspring expectation} $\mu =
n_{*}p$ \cite{durrett2010probability}. Here, $\mu$ denotes the
expected number of reshares that the post gets.
Using a standard branching process result, we have $Z_{i}/\mu^i$ is a
martingale. Therefore, $\forall k>1$, $\E \left [Z_{k+1} | Z_k \right ]  = \mu \ Z_k$,
and,
\[
\E\left[\sum_{k=1}^\infty Z_k \middle| Z_1\right] = \frac{Z_1}{(1 - \mu)}= \frac{Z_1}{(1 - n_* p)}\, .
\]
Hence, we obtain
$$\E[R_\infty | \F_t] = R_t
+ \E\left[\sum_{k=1}^{\infty} Z_{k}\right] = R_t +
\frac{\E[Z_1]}{(1 - n_{*} p)},$$ which ends up being the right hand
side in Eq.~\eqref{eq:predict} because $\E[Z_1] = p(N_t - N^e_t)$ by
the definition of $Z_1$ and $N^e_t$.

Next, consider the case where $p = \p_t \geq 1/n_*$. In this regime,
the point process is supercritical and stays explosive. In terms of the
Galton-Watson tree discussed above, the offspring expectation $\mu =
n* p \ge 1$, so $\E[Z_{k+1}] \ge \E[Z_k] \ge \dotsb \ge
\E[Z_1]$. Therefore the total future reshares
$\sum_{k=1}^{\infty}Z_k$ has infinite expectation and the final
reshare count cannot be reliably predicted.
\end{proof}

%We will validate the conclusions in Proposition \ref{prop:expectation} using real data in Section \ref{sec:model-validation}.

%As noted in Remark \ref{rmk:1},
%Note that the Proposition \ref{prop:expectation} assumes that the probability that a post spreads to a follower is constant $p$. In general, the assumption may not hold, however, when $p$ varies over time, the analysis of the resulting diffusion tree and the computation of the corresponding expectation becomes extremely involved. This case is indeed an interesting line of research which we leave to future work.

Note that Prop.\ \ref{prop:expectation} assumes that the post
infectiousness remains constant in the future ($p_s = p_t$ for $s \ge
t$), which could be unrealistic for some information cascades. We correct this by changing the prediction formula in Eq.~\eqref{eq:predict} by adding two
scaling constants $\alpha_t, \gamma_t$ that adjust the final prediction:
\begin{equation}
  \label{eq:new-predict}
\hat{R}_{\infty}(t) = R_t + \alpha_t \frac{\hat{p}_t (N_t - N^e_t)}{1
  - \gamma_t \hat{p}_t n_{*}},~0<\alpha_t,\gamma_t<1 \, .
\end{equation}
We introduce these correction factors based on the
following intuition. We expect $\alpha_t$ to decrease over time $t$ so it scales
down the estimated infectiousness in the future, which accounts for
the post getting stale and outdated. Similarly, $\gamma_t$ accounts
for the overlap in the neighborhoods of reposters' followers. Over
time as the post spreads farther in the network, we expect $\gamma_t$
to increase as more nodes get exposed multiple times, which means the
arrival rate of new nodes (previously unexposed nodes) decreases over time.

We use the same values of $\alpha_t$ and $\gamma_t$ for all posts but allow them to vary over time.
The values of $\alpha_t$ and $\gamma_t$ are selected to minimized
median Absolute Percentage Error (refer to Section
\ref{sec:error-metrics} for definition) on a training data set. As
described in Section~\ref{sec:parameter-estimation}, we find
$\alpha_t$ is more important than $\gamma_t$ in
practice. %\qz{everybody have another look at this part, thanks!}

\hide{
There are several reasons for using such model calibration procedure:
%\begin{enumerate}[noitemsep]
First, in decision theory and statistics, Stein's paradox shows that
  shrinking the estimated means $\hat{R}_{\infty}(t)$ is more accurate
  than using them directly, especially if we need to make a large number
  of predictions.
Second, we expect $p_t$ might decrease as time $t$ goes by (\eg, Figure
  \ref{fig:breakout}), so we may
  overestimate the size of first generation $\mathrm{E}[Z_{1}]$ and
  the offspring expectation $\mu$. To compensate for this, we discount them by
multiplying $\alpha_t$ and $\gamma_t$.
And third, the estimated memory kernel $\phi(s)$ and thus $N^e_t$
can be inaccurate. This error can also be corrected by introducing
tuning parameters.
}
%\end{enumerate}
%We will discuss another motivation from $\phi(s)$
%of adding these two parameters in Section~\ref{sec:parameter-estimation}.
%Note that $\gamma_t$ affects
% the prediction only through $\gamma_tn_{*}$, so alternatively one
% could make parametrize $\gamma_tn_{*}$ with $n_{*}(t)$. We decided on the
% form of $\gamma_tn_{*}$ to keep the physical meaning of $n_{*}$ untouched.



\subsection{The SEISMIC algorithm}
\label{sec:algorithm}

Last, we put together all the components described so far and synthesize them in the \sem algorithm.
The \sem algorithm for predicting $\hat{R}_{\infty}(t)$ is described in Algorithm \ref{alg:2}, which uses the algorithm for computing $\hat{p}_t$ (Algorithm~\ref{alg:1}) as a subroutine.
These algorithms are based on Eqs. \eqref{eq:mle-kernel} and
\eqref{eq:new-predict}. We assume parameters
$K_t(s)$, $\alpha_t$, $\gamma_t$, $n_{*}$ are given \emph{a priori} or estimated from the data.

\begin{algorithm}[t]
  \caption{\sem: Predict final cascade size}
  \label{alg:2}
  \begin{algorithmic}
    \State  \textbf{Purpose:} {For a given post  at time $t$, predict its final reshare count}
    \State \textbf{Input:} {Post resharing information:} $t_i~\text{and}~n_i~\text{for}~i = 0, \dotsc,R_t$.
    %\item {\bf Estimated parameters:} $\phi(s), \alpha_t, \gamma_t, n_{*}$
    % $R_t, \hat{p}_t.$,

% estimate of infectiousness parameter $\hat{p}_t$,
%     current retweet count $R_t$, retweet times $t_i, i = 0, \dotsc,
%     R_t$, degrees of nodes $n_i, i = 0, \dotsc, R_t$, memory kernel
%     $\phi(s)$(see section~\ref{sec:parameter-estimation}), parameters
%     $\alpha_t, \gamma_t, n_{*}$(see
%     section~\ref{sec:parameter-estimation} \hera{not there now, check later})
    \State \textbf{Algorithm:}
    \State
    $N_{t}$ = 0, $N_{t}^{e}$ = 0
    \For {$i =  0, \dotsc, R_t$}
    \State $N_{t}$ += $n_i$
    \State $N_{t}^{e}$ += $n_i\int_{t_i}^{t} \phi(s - t_i)ds$ \hfill(Sec.~\ref{sec:human-reaction-time})
    \EndFor
    \State $\hat{R}_{\infty}(t) = R_t + \alpha_t \hat{p}_t (N_t - N^e_t) / (1 - \gamma_t \hat{p}_t n_{*})$ \hfill(Alg.~\ref{alg:1})
    \State \textbf{Deliver:} $\hat{R}_{\infty}(t)$
  \end{algorithmic}
\end{algorithm}

\begin{algorithm}[t]
  \caption{Compute real-time infectiousness $\hat{p}(t)$}
  \label{alg:1}
  \begin{algorithmic}
    \State  \textbf{Purpose:} {For a given post $w$, calculate infectiousness $p_t$ with information about $w$ prior to time $t$}
    \State \textbf{Input:} {Post resharing information:} $t_i~\text{and}~n_i~\text{for}~i = 0, \dotsc, R_t$.
    %\item {\bf Reweighting kernel} $K_t(s)$
    %\item {\bf Estimated parameters} $\phi(s)$


% current retweet count $R_t$, retweet times
%     $t_i, i = 0, \dotsc, R_t$, degrees of nodes $n_i, i = 0, \dotsc,
%     R_t$,
%     reweight kernel $K_t(s)$(see Eq.~\eqref{eq:weighting-kernel}),
% memory kernel $\phi(s)$(see section~\ref{sec:parameter-estimation})
    \State \textbf{Algorithm:}
    \State
    $\tilde{R}_t$ = 0, $\tilde{N}_t^{e}$ = 0
    \For {$i =  0, \dotsc, R_t$}
    \State $\tilde{R}_t$ += $K_t(t - t_i)$
    \EndFor
    \For {$i =  0, \dotsc, R_t$}
    \State $\tilde{N}_t^{e}$ += $n_i\int_{t_i}^{t} K_t(t - s)\phi(s - t_i)ds$
    \hfill(Sec.~\ref{sec:estimation-infectiousness})
    \EndFor

\State
$p_t = \tilde{R}_t/\tilde{N}_t^{e}$
    \State \textbf{Deliver:} $p_t$
  \end{algorithmic}
\end{algorithm}

\xhdr{Computational complexity of \sem}
For any choice of $\phi(s)$ and $K_t(s)$, the computational cost of \sem is
$O(R_{t})$ for both calculating $\hat{p}_t$ and predicting $\hat{R}_{\infty}(t)$.
Of course, the actual computing time depends heavily on the
integration $\int_{t_i}^{t} K_t(t - s)\phi(s - t_i)ds$
and  $\int_{t_i}^{t} \phi(s - t_i)ds$. However, the overall computational cost of \sem is {\em linear} in the observed number of reshares $R_t$ of a given post by time $t$.

The linear time complexity is in part also due to the shape of our memory kernel. In Section~\ref{sec:parameter-estimation} we will estimate the memory kernel $\phi(s)$ for Twitter to have  the following form (for some $s_0 > 0$):
% \begin{equation}
%   \label{eq:memory-kernel}
%   \phi(s) = c \cdot \min \left\{ 1,~\left(s/s_0
%   \right)^{-(1+\theta)} \right\},~s > 0
% \end{equation}
\begin{align}
  \label{eq:memory-kernel}
  \phi(s) =
  \begin{cases}
  c  &\text{if $0 < s \le s_0$}, \\
  c(s/s_0)^{-(1+\theta)} & \text{if $s > s_{0}$}.
  \end{cases}
\end{align}
This means that with the memory kernel $\phi(s)$ in Eq.~\eqref{eq:memory-kernel} and triangular weighting kernel $K_t(s)$ in Eq.~\eqref{eq:weighting-kernel}, both integrals can be evaluated in closed form because they are piece-wise polynomials (polynomial with possibly non-integer exponents), which greatly decreases computational cost of \sem.
%We omit the details for brevity.
% \jure{If we have space, can we actually work out the two integrals and give the derivation in the paper.}

% The computational cost of our method is indeed linear in the total
% number of retweets. Suppose the tweet gets $R$ retweets in the end
% there is a fixed grid of time $(s_1, s_2, \ldots s_m)$ that we want to
% compute our estimate $\hat{p}_{s_j}$ and prediction $\hat{R}_{\infty}(s_j)$,
% $j=1,\ldots,m$.
% The computational cost of getting all the integrals
% $\int_{s_{j-1}}^{s_j} d N^e_s$ and $\int_{s_{j-1}}^{s_j} K_{t_i}(t_i-s) d
% N^e_s$ for $i=1,\ldots,R$ and $j=1,\ldots,m$ is just $O(mR)$ if we use
% the triangular kernel. If we use other kernel functions, the
% computational cost is $O(mR^2)$. \qz{Hera, please check this.}
% \jure{I suggest we put together the ``algorithm'' description. Create an algorithm environment and there clearly describe what are inputs, what are the estimated parameters, and what's the output. We can then also discuss the computational complexity and other details of the algorithm. Also, discuss how many parameters do we have in our model and then point forward to 5.2 where we show how to estimate them.}

paper-twitter.bbl
\begin{thebibliography}{10}

\bibitem{gaddafi-bieber}
\url{https://twitter.com/mottbollomy/status/127001313513967616}.

\bibitem{Agarwal2009}
D.~Agarwal, B.-C. Chen, and P.~Elango.
\newblock Spatio-temporal models for estimating click-through rate.
\newblock In {\em WWW '09}, 2009.

\bibitem{bakshy2011everyone}
E.~Bakshy, J.~M. Hofman, W.~A. Mason, and D.~J. Watts.
\newblock Everyone's an influencer: quantifying influence on twitter.
\newblock In {\em WSDM '11}, 2011.

\bibitem{bandari2012pulse}
R.~Bandari, S.~Asur, and B.~A. Huberman.
\newblock The pulse of news in social media: Forecasting popularity.
\newblock In {\em ICWSM '12}, pages 26--33, 2012.

\bibitem{Barabasi2005}
A.-L. Barabasi.
\newblock The origin of bursts and heavy tails in human dynamics.
\newblock {\em Nature}, 435:207, 2005.

\bibitem{cheng2014can}
J.~Cheng, L.~Adamic, P.~A. Dow, J.~M. Kleinberg, and J.~Leskovec.
\newblock Can cascades be predicted?
\newblock In {\em WWW '14}, 2014.

\bibitem{Crane2008}
R.~Crane and D.~Sornette.
\newblock Robust dynamic classes revealed by measuring the response function of
  a social system.
\newblock {\em PNAS}, 105(41), 2008.

\bibitem{daneshmand14netrate}
H.~Daneshmand, M.~Gomez-Rodriguez, L.~Song, and B.~Sch{\"o}lkopf.
\newblock Estimating diffusion network structures: Recovery conditions, sample
  complexity \& soft-thresholding algorithm.
\newblock In {\em ICML '14}, 2014.

\bibitem{dow2013anatomy}
P.~A. Dow, L.~A. Adamic, and A.~Friggeri.
\newblock The anatomy of large facebook cascades.
\newblock In {\em ICWSM '13}, 2013.

\bibitem{du2012learning}
N.~Du, L.~Song, M.~Yuan, and A.~J. Smola.
\newblock Learning networks of heterogeneous influence.
\newblock In {\em NIPS '12}, 2012.

\bibitem{durrett2010probability}
R.~Durrett.
\newblock {\em Probability: theory and examples}.
\newblock Cambridge university press, 2010.

\bibitem{gao2015modeling}
S.~Gao, J.~Ma, and Z.~Chen.
\newblock Modeling and predicting retweeting dynamics on microblogging
  platforms.
\newblock In {\em WSDM '15}, 2015.

\bibitem{manuel13pathways}
M.~Gomez-Rodriguez, J.~Leskovec, D.~Balduzzi, and B.~Sch\"{o}lkopf.
\newblock Uncovering the structure and temporal dynamics of information
  propagation.
\newblock {\em Network Science}, 2:26--65, 4 2014.

\bibitem{rodriguez2013modeling}
M.~Gomez-Rodriguez, J.~Leskovec, and B.~Sch\"{o}lkopf.
\newblock Modeling information propagation with survival theory.
\newblock In {\em ICML '13}, 2013.

\bibitem{manuel13dynamic}
M.~Gomez-Rodriguez, J.~Leskovec, and B.~Sch\"{o}lkopf.
\newblock {Structure and Dynamics of Information Pathways in On-line Media}.
\newblock In {\em WSDM '13}, 2013.

\bibitem{hawkes1971}
A.~G. Hawkes.
\newblock Spectra of some self-exciting and mutually exciting point processes.
\newblock {\em Biometrika}, 58(1), 1971.

\bibitem{hong2011predicting}
L.~Hong, O.~Dan, and B.~D. Davison.
\newblock Predicting popular messages in twitter.
\newblock In {\em WWW '11}, 2011.

\bibitem{hunter2011dynamic}
D.~Hunter, P.~Smyth, D.~Q. Vu, and A.~U. Asuncion.
\newblock Dynamic egocentric models for citation networks.
\newblock In {\em ICML '11}, 2011.

\bibitem{kendall1938new}
M.~G. Kendall.
\newblock A new measure of rank correlation.
\newblock {\em Biometrika}, pages 81--93, 1938.

\bibitem{kupavski2012cikm}
A.~Kupavskii, L.~Ostroumova, A.~Umnov, S.~Usachev, P.~Serdyukov, G.~Gusev, and
  A.~Kustarev.
\newblock Prediction of retweet cascade size over time.
\newblock In {\em CIKM '12}, 2012.

\bibitem{nowell08letter}
D.~Liben-Nowell and J.~Kleinberg.
\newblock Tracing the flow of information on a global scale using {I}nternet
  chain-letter data.
\newblock {\em Proceedings of the National Academy of Sciences},
  105(12):4633--4638, 2008.

\bibitem{Matsubara2012rise}
Y.~Matsubara, Y.~Sakurai, B.~A. Prakash, L.~Li, and C.~Faloutsos.
\newblock Rise and fall patterns of information diffusion: Model and
  implications.
\newblock In {\em KDD '12}, 2012.

\bibitem{mohler2011}
G.~O. Mohler, M.~B. Short, P.~J. Brantingham, F.~P. Schoenberg, and G.~E. Tita.
\newblock Self-exciting point process modeling of crime.
\newblock {\em Journal of the American Statistical Association},
  106(493):100--108, 2011.

\bibitem{naveed2011bad}
N.~Naveed, T.~Gottron, J.~Kunegis, and A.~C. Alhadi.
\newblock Bad news travel fast: A content-based analysis of interestingness on
  twitter.
\newblock In {\em ACM WebSci '11}, 2011.

\bibitem{ogata1988}
Y.~Ogata.
\newblock Statistical models for earthquake occurrences and residual analysis
  for point processes.
\newblock {\em Journal of the American Statistical Association}, 83, 1988.

\bibitem{petrovic2011rt}
S.~Petrovic, M.~Osborne, and V.~Lavrenko.
\newblock {RT to Win! Predicting Message Propagation in Twitter.}
\newblock In {\em ICWSM '11}, 2011.

\bibitem{rogers95diffusion}
E.~M. Rogers.
\newblock {\em Diffusion of innovations}.
\newblock Simon and Schuster, 2010.

\bibitem{shen2014modeling}
H.-W. Shen, D.~Wang, C.~Song, and A.-L. Barab{\'a}si.
\newblock Modeling and predicting popularity dynamics via reinforced poisson
  processes.
\newblock {\em arXiv:1401.0778}, 2014.

\bibitem{snyder2011}
D.~L. Snyder and M.~I. Miller.
\newblock {\em Random Point Processes in Time and Space}.
\newblock Springer, 2011.

\bibitem{suh2010want}
B.~Suh, L.~Hong, P.~Pirolli, and E.~H. Chi.
\newblock Want to be retweeted? large scale analytics on factors impacting
  retweet in twitter network.
\newblock In {\em SOCIALCOM '10}, 2010.

\bibitem{Szabo2010}
G.~Szabo and B.~A. Huberman.
\newblock Predicting the popularity of online content.
\newblock {\em Communications of the ACM}, 53(8):80--88, Aug. 2010.

\bibitem{yang2011}
J.~Yang and J.~Leskovec.
\newblock Patterns of temporal variation in online media.
\newblock In {\em WSDM '11}, 2011.

\bibitem{yang2013mixture}
S.-H. Yang and H.~Zha.
\newblock Mixture of mutually exciting processes for viral diffusion.
\newblock In {\em ICML '13}, 2013.

\bibitem{Zaman2014}
T.~Zaman, E.~Fox, and E.~Bradlow.
\newblock A {B}ayesian approach for predicting the popularity of tweets.
\newblock {\em Annals of Applied Statistics}, 8(3):1583--1611, 2014.

\bibitem{zaman2010predicting}
T.~R. Zaman, R.~Herbrich, J.~Van~Gael, and D.~Stern.
\newblock Predicting information spreading in twitter.
\newblock In {\em Computational Social Science and the Wisdom of Crowds
  Workshop, NIPS}, 2010.

\bibitem{zhou2013learning}
K.~Zhou, H.~Zha, and L.~Song.
\newblock Learning social infectivity in sparse low-rank networks using
  multi-dimensional hawkes processes.
\newblock In {\em AISTATS '13}, 2013.

\end{thebibliography}
