Authors: Chen Ling, Guangmo Tong, Mozi Chen

This Seed edition’s formatting was converted from the ACM version of record under the supplied ACM publication authorization.

Abstract

Online discussion forum creates an asynchronous conversation environment for online users to exchange ideas and share opinions through a unique thread-reply communication mode. Accurately modeling information dynamics under such a mode is important, as it provides a means of mining latent spread patterns and understanding user behaviors. In this paper, we design a novel temporal point process model to characterize information cascades in online discussion forums. The proposed model views the entire event space as a nested structure composed of main thread streams and their linked reply streams, and it explicitly models the correlations between these two types of streams through their intensity functions. Leveraging the Reddit data, we examine the performance of the designed model in different applications and compare it with other popular methods. The experimental results have shown that our model can produce competitive results, and it outperforms state-of-the-art methods in most cases.

CCS Concepts

Computing methodologies → Temporal reasoning.

Keywords

temporal point process, online discussion forum, information dynamics

ACM Reference Format: Chen Ling, Guangmo Tong, and Mozi Chen. 2020. NesTPP: Modeling Thread Dynamics in Online Discussion Forums. In 31st ACM Conference on Hypertext and Social Media (HT ’20), July 13–15, 2020, Virtual Event, USA. ACM, New York, NY, USA, 10 pages. https://doi.org/10.1145/3372923.3404796

1 INTRODUCTION

The ways of human interaction have long been a subject of interest. Recently, the rise of online social networks provides a rich substrate for large-scale online user interaction for sharing and exchanging information. Understanding the latent mechanism of such information dynamics has been an active topic, because it provides us with new insights into the needs, opinions, and experiences of

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.

individuals [25]. Through modeling such information diffusion dynamics, the existing works have greatly promoted the development of online social networks by various applications, such as content recommendation ([1, 13]) and anomaly detection ([16, 24]).

As a subclass of online social networks, the online discussion forum (ODF) has become a significant platform of knowledge sharing for the past decade. In the area of online education, MOOC (Massive Online Open Course) is an exemplary ODF that enables students in online courses to learn socially as a supplement to their studying of the course content individually. ODFs are distinct from other platforms in primarily two aspects. First, unlike Facebook or Twitter, ODFs are not built through user relationships (e.g., friendship and follower-followee relationship), and their contents are publicly available to all visitors. Online users have the flexibility to reflect on their thoughts and read the responses of any public posts. Second, ODFs allow high-volume asynchronous interactions through the thread-reply mode in which participants can create threads (e.g., posts and questions) and react to the threads by making replies (e.g., comments, votes, and answers). Universally, the ODF promotes users to popularize well-regarded threads to the front page via replies, and such a process of information exchange exhibits a unique nested thread-reply structure in which these two types of streams are correlated with each other. Given these unique characteristics and successful examples, in this paper we study the problem of modeling thread dynamics in ODFs.

Challenges. The primary problem in modeling information dy- namics is to predict the arrival time of the subsequent events (

[1, 6, 12, 18, 30]). In ODFs, there are two main challenges in studying the thread dynamics. First, we often have very limited historical temporal information (e.g., arrival time or inter-arrival time) that is not sufficient for learning an expressive model, which is exacerbated by the high uncertainty of the eventual scope of an information cascade [7]. The common solution is to incorporate exogenous features (e.g., context, user profile, and other network information) to support the prediction. However, discriminative models with extra features cannot make adaptive predictions as the features of future events are not known to us. In the scenario of ODFs, if we would use semantic features, it is not possible to predict the arrival time of future threads adaptively unless we could also predict the future contents. On the other hand, training a generative model that simultaneously predicts all the features can be overambitious since we, in fact, care only the temporal patterns of information dynamics but not everything happening in the future. Secondly, despite the extensive research carried out on analyzing the unique discussion structure of the ODF ([2, 17, 26]), few studies have considered if there exists an impact of the natural thread-reply structure to the information exchange pattern in the ODF. Moreover, can we utilize

the unique nested structure of ODFs in predicting its future thread dynamics? In this work, we aim to propose an effective framework to resolve such difficulties.

Our Work. To model the thread dynamics in ODFs, we design the Nested Temporal Point Process (NesTPP) model that leverages the unique nested thread-reply structure without using excessive features. The major contributions are summarized as follows.

We build the NesTPP framework for modeling temporal

dynamics in the ODF by taking the main thread stream and associated reply stream as combined self-exciting temporal point processes with carefully designed intensity functions.

We derive a closed-form solution of the likelihood function

and utilize an MLE based algorithm with a quasi-Newton optimization method to estimate the parameters of the likelihood function in NesTPP. An adaptive sampling algorithm is also proposed to simultaneously generate the future main threads and replies without assuming a fixed dimension, making NesTPP applicable to several applications.

We show that NesTPP is practically effective through the

experiments on real-world social media data. According to the results, the NesTPP model produces a clear improvement over the existing state-of-the-art methods in several prediction tasks. We also demonstrate that NesTPP can be used as a tool for visualizing the correlation between event streams.

Road-map. Sec. 2 surveys the related works. In Sec. 3, we de- scribe the NesTPP model and its properties. The following Sec. 4 presents the experiment results. In the end, Sec. 5 concludes the paper and discusses potential future works.

2 RELATED WORK

Temporal Point Process (TPP). Temporal point processes lever- age the fine-grained time information and related features from the event stream to understand the diffusion mechanism in social networks, which have been viewed as a natural choice of modeling social interactions for many years. Among the variants, Hawkes process [10], as a subset of non-homogeneous Poisson process, has been broadly employed in modeling more intricate information propagation process. Zhao et al. [30] implemented the SEISMIC model based on the self-exciting point process to predict the final volume of the retweet cascade. Similarly, Kobayashi [12] and Chen

[6] utilized additional mark information[1] to more accurately model and predict the retweeting dynamics in Twitter. There also exists literature [4, 8, 11, 15] studying the latent relationship between different components, involving users, social activities, and network structures, by the TPP model. NesTPP differs from the existing ones in that we regard both thread stream events and reply stream events as the separate but correlated self-exciting point processes in the same event space. Furthermore, our model utilizes only internallygenerated mark information, enabling stronger applicability to other thread-reply scenarios. Additionally, each thread-reply cascade in ODFs can be regarded as an individual point process, which forms a special case of the multivariate point processes with dynamic dimensions. Unlike other methods ([5, 18]) that adopted only

1Features other than event arrival time, such as the number of followers of a user, the periodic factor, and the social popularity of a discussion event.

fixed-dimension multivariate point processes, our model can adaptively learn the latent influence among thread-reply cascades and simulate new cascade by creating new dimensions.

Online Discussion Forum. In the study of ODFs, a large vol- ume of works ([13, 28]) have investigated the information exchange dynamics in MOOC platform (i.e., Massive Open Online Courses), a special form of an ODF for education only. Studying the information exchange dynamics in a more general ODF is needed. Recently, Gomez et al. presented a generative model [9] to capture the temporal evolution of the observed thread-reply structure. In [27], the authors presented a dynamic model that predicts the growth trends and structural properties of the online conversation threads; however, their works have limitations in processing real-world data and predicting future cascade size because of the mean-field nature of the adopted Lévy process model. In addition, Ryosuke [21] and Medvedev [17] also proposed different models to predict the temporal dynamics of main threads as a discussion tree. More recently, [16] utilized the Hawkes process to target the user and event clustering in the ODF. Nonetheless, their works have treated all events in an ODF as a unified point process. In practice, the information diffusion pattern between the main thread stream and reply stream should be governed by different point processes since they may have different diffusion patterns. Moreover, existing works

[2, 13, 17] have used additional mark information in their models for various prediction tasks in ODFs. However, the application of future cascade prediction requires long-range adaptively prediction, which is not applicable to utilize external mark information to enhance the prediction accuracy. The NesTPP proposed in this paper focuses on utilizing only the natural nested structure and easy-to-retrieved mark information to capture more subtle shifts in the information cascade evolution.

Other Related Works. Other than the TPP based methods, there also exist a large volume of feature-based approaches ([7, 20, 29]) that study the information propagation pattern mostly in friendship-based social networks. These methods need to extract extensive features and utilize learning algorithms (e.g., SVM and neural networks) to capture the propagation pattern from data. Such approaches have limited applicability because feature engineering is often very expensive and time-consuming, and most of the works are classification-based models, which cannot be used to predict future cascade evolution. As we stated in the Introduction, exogenous features are hard to retrieve in the task of adaptive prediction, and they cannot be applied directly in our scenario. Our work differs from them because the only feature utilized is the arrival time of each event; other mark information is also derived from the event arrival time to enhance the model’s forecasting capability.

3 PROPOSED MODEL

In this section, we start by introducing the problem setting and the key concepts of the TPP. We then present the NesTPP model with the design of intensity functions, model complexity, sampling algorithm, and properties of our model.

3.1 Problem Setting

Our paper targets the online discussion forum operated in the thread-reply mode composed of two types of event streams, thread

Col1	t1 t2 t3	tm
t1,1 t1,2 t1,n1	t2,1 t3,2 t2,2 t3,1 t2,n2 t3,n3	tm,1 tm,2 tm,n

stream and reply stream, where the threads {ti } are created as new web content to which users can respond through replies {ti,j }, as illustrated in Fig. 1. Note that we use the arrival time of events to denote the events. In this paper, we aim to design a model that can understand the latent diffusion mechanism of the event streams under such a nested communication mode. Additionally, to better model the dynamics of information cascades in ODFs, most of the previous works utilized exogenous mark information to enhance the influence of past events in the TPPs, including the number of upvotes, received awards, and the profile information of online users. However, additional mark information is usually hard to retrieve as it varies with time, and it thus cannot be directly employed to model the temporal change of the event cascade. For better applicability, we utilize only the count of replies to the main thread at the current timestamp as the mark information.

3.2 Temporal Point Process

In general, a TPP is defined as a random and finite series of events with associated marks governed by a probabilistic rule. Let a sequence of events {ei } = {(ti, pi ), i ∈ Z[+]} represents a marked TPP, where ti ∈ R[+] is the occurrence time of each event and the pi denotes the corresponding event mark of ei . We use Ht = {ti < t } to denote the sequence of events arrival time until the current time t. The simplest class of TPP is the Poisson process in which events are arriving at an average rate of λ ∈ R[+] per unit time, and the intensity of the Poisson process is defined as λ.

A self-exciting TPP (also known as the Hawkes Process) is essentially a non-homogeneous Poisson process where the event intensity λ is determined by all previous events Ht, and a conditional intensity function gives the expression of λ:

ipfs://bafkreibl5hbhzg6myehuzld5hlqnrdj3ttucgwjyjhqwkx6xeldb4uegca)

3.3 Nested Temporal Point Process: NesTPP

Nested Structure. The existing Hawkes-based TPP models often treat the evolution of main threads and associated replies as a unified TPP in one dimension. However, the diffusion patterns of different event streams are typically governed by different but correlated probabilistic rules. For example, the occurrence of a new main thread not only depends on the impact of all previous main threads but also from all the associated replies, and the generation of reply events also relies on the influence of the linked main threads. The latent relation between both event streams forms the nested structure of the information cascade. Fig. 2 illustratively presents the unique diffusion mechanism in an ODF. In order to comprehend such a mechanism, we design the NesTPP that treats both types of event streams as separate self-exciting point processes controlled by inter-dependent intensity functions. In what follows, we present detailed designs of our model.

Reply Stream. The reply stream intensity function λ[i]reply[(·)]

derives from the intuition of the univariate Hawkes process defined in Eq. 1 with an exponential decaying kernel. Recall that each main thread ti has ni reply events, and the arrival time of each linked reply is ti,j . The intensity function of reply stream λ[i]reply[(·)][ of][ i][-th]

main thread is defined as:

λ(t | Ht ) = µ0(t) +

�

i:t >ti

ψ (t − ti, pi ), (1)

where t ∈ R[+] represents the current timestamp, µ0(t) ∈ R[+] denotes the base intensity of each incoming event at time t, and ψ (·) is called the memory kernel. In specific, the memory kernel modulates the influence of a previous event at time ti to the later events. Typically, ψ (·) is taken to be monotonically decreasing so that more recent

events have a higher influence on the current event intensity, compared to events having occurred further away in time [10]. In this paper, we utilize the modified standard exponential decay memory kernel [10] and power-law memory kernel [23] to explicitly fit different event stream diffusion patterns.

The term µreply ∈ R[+] denotes the base intensity of the reply stream point process, and ψreply(t) represents the reply stream memory kernel. The positive constant α, β ∈ R[+] in the memory kernel have the following interpretations: each arrival of a reply in the system instantaneously increases the arrival intensity by α, then

αe[−][β] [(][t] [−][t][i] [,] [j] [)] �� �� � �� ψreply(t )

λ[i]reply[(][t][)][ =][ µ][reply][ +][ q][(][t][) ·]

ni �

j=1

. (2)

the influence of this arrival decays at rate β over time. Furthermore, q(t) ∈ R[+] is the additional mark information which models the infectivity of the linked main thread, and it is defined as follows:

q(t) = e[−][δ] [(][t] [−][t][0][)],

where t −t0 denotes the duration of time from the current timestamp t to the arrival time of the associated main thread t0, and δ ∈ R[+]

represents the decaying rate of the associated main thread infectivity to the reply stream. Intuitively, q(t) scales down the estimated infectivity of the linked main thread over time, which accounts for the thread getting outdated based on the newsworthiness of a discussion topic.

Main Thread Stream. Recalling the definition of the event in- tensity function in Eq. 1, the arrival rate of new threads depends on each previously occurred thread ti through the triggering kernel ψ (t). In addition, the reply streams of each previously occurred

thread also impact the arrival of new threads. We hereby construct the power-law based kernel function λmain(t) as follows:

Algorithm 1: Adaptive Sampling for Main Threads

Input: N, M, R, Eq. 2 and 3. Output: The list of sampled main threads time M. Set counter c ← 0, t ← M[−1] (Last item in M); while c < N do

Update reply time series: R ← Alg. 2; Get events intensity upper bound λmain ← λmain(t) (Eq.

3);

λ[i]reply[(][t][) ·][ p]i[γ] [· (][t] [−] [t][i] [+][ c][)][−(][η][+][1][)], (3)

�� �� � �� ψmain(t )

Draw s ∼ U (0, 1), and τ ←− λ[ln]main[(][s][)] [;]

Update the current time: t ← t + τ ; Draw s [′] ∼ U (0, λmain); if s [′] < λmain(t) then

Update the main thread series: M.append(t); Update the reply series: R.append([ ]); Update the counter: c ← c + 1; else

go back to the beginning of the while section;

function. According to the likelihood function described in Eq. 4, we obtain the log-likelihood function by introducing both main thread stream and reply stream intensity function into Eq. 4. Then, the log-likelihood function is:

λmain(t) = µmain +

m �

i=1

where µmain ∈ R[+] is the base intensity of the main thread stream and ψmain(t) is the memory kernel of main thread stream. pi[γ] [∈] [R][+]

denotes the influence of the mark information from each individual main thread with γ ∈ R[+] being a warping effect. Note that we assume that pi is the number of replies of the main thread up to the time ti . Moreover, (η + 1), η ∈ R[+] is the power-law exponent representing the decaying rate of the influence of each previous event ti, and parameter c ∈ R[+] is a regularization term in order to keep the exponential term λmain(·) bounded when t −ti approaches

Finally, the term λ[i]reply[(][t][)][ denotes the influence factor carried by]

its associated reply streams, which has been defined in the Reply Stream part. In this power-law based intensity function, λ[i]reply[(][t][) ·]

pi[γ] [<][ η][ ·][ c][η] [denotes the overall magnitude of influence to the main]

thread stream.

In summary, the NesTPP models the cascade evolution by defining the TPP for each event stream with intensity functions (Eq. 2 and 3), and the parameters can be estimated through maximizing the joint likelihood function since two intensity functions are correlated.

3.4 Parameters Estimation and Training Complexity

Given the complete event sequence history Ht with associated marks in a point process, the conditional density function can be computed as f (t) = f (t |Ht ):

ni �

j=1

log(L) =

m �

i=1

� log λmain(t)[�] + log λ[i]reply[(][t][)][��]

[�] [�]

− Λmain(tm ) −

m �

i=1

Λ[i]reply[(][t][n][i][ )][,]

(4)

�

L = f (t) = f (t1 · t2 · ... · tN ) =

N �

n=1

� t |t1, t2, ..., tN

where Λmain(·) and Λ[i]reply[(·)][ is the integrated conditional intensity]

function, namely the compensator for both main thread stream and associated reply streams [14]. We present the complete derivation of the log-likelihood function of NesTPP as well as compensators Λmain(·) and Λ[i]reply[(·)][ in Appendix A.1.]

Due to the non-convexity of this likelihood function, we utilize the limited-memory Broyden-Fletcher-Goldfarb-Shanno algorithm (L-BFGS)[3], a quasi-Newton gradient-based optimization technique, to solve the nonlinear and unconstrained likelihood function and update parameters. The L-BFGS optimization method has the time complexity O(k - s), where k is the number of parameters that we aim to estimate, and s is the number of steps stored in memory by parameter declaration. The complexity of the log-likelihood function is taken to be O(Γ), where the Γ is the total number of events in the training set. Taken together, the upper bound of the training complexity of NesTPP is O(Γ - k - s). To avoid the local optimum caused by non-convexity of the likelihood function, we sample several initializations of the parameter set at the start point and choose the parameter set with the best performance. Moreover, we regulate the upper and lower bounds for all the parameters in order to avoid potential calculation overflow and stabilize the training process.

� - exp(− ∫ tn λ(u) du)

� �[N]

n=1

λ(tn )

Directly computing the likelihood function has the potential risks of underflow, thus it is customary to maximize the log-likelihood

Algorithm 2: Adaptive Sampling for Reply Events

Input: T, M[i], R, C, Eq. 2. Output: The list of sampled events time R. Set counter c ← 0; for (i = 0; i < len(R); i + +) do

if R[i] is not empty then

t ← R[i][−1] (Last item in R[i]); else

t ← M[i];

Col1	Sports Dataset Movie Dataset
Main Threads Replies Involved Users Replies per Thread	1,610 2,261 71,638 8,239 17,982 4,152 44.496 1.98

while t ≤ T and c ≤ C do

Get reply event intensity upper bound

λ[i]reply [←] [λ][i]reply[(][t][)][ (Eq. 2);]

Draw s ∼ U (0, 1), and τ ←− [ln][(][s][)] ;

λreply[i]

Update the current time: t ← t + τ ; Draw s [′] ∼ U (0, λ[i]reply[)][;]

if s [′] < λ[i]reply[(][t][)][ then]

Update the reply time series: R[i].append(t); Update the counter: c ← c + 1 else

go back to the head of the while section;

3.5 Properties of NesTPP

Prediction of Future Dynamics. Having observed the evolution of an information cascade until the current time under a given TPP model, one can simulate a possible continuation of the cascade using the standard thinning technique [22]. Through simulating the expected number of all descendent main threads and associated replies, the temporal size of the information cascade can thus be quantified. Considering the natural nested structure of the ODF, we modify the standard thinning technique to adaptively and simultaneously generate main threads and the linked replies. The complete process has been concluded in Alg. 1 and 2.

Specifically, the adaptive sampling algorithm is composed of two parts: simulating main threads and simulating the associated replies of each simulated main thread. The simulation of the main threads takes the expected number of future main threads N, the observed main thread stream M, the associated reply streams R, and the fitted parameters as inputs. At each iteration, the arrival time ti of a new main thread is estimated through our NesTPP model (Eq. 2 and 3), as shown in Alg. 1. Meanwhile, the arrival time of replies ti,j under each main thread can also be sampled. As stated in Alg. 2, the simulation of the reply stream of each main thread takes some extra inputs: T, M[i], and C. T is the size of the time window in which allows the i-th main thread to simulated the associated replies, and M[i] is the arrival time of the linked i-th main thread. After the simulated arrival time of a reply exceeds the time window T or the number of the simulated replies exceeds the given threshold C, the model would begin to simulate the next (i + 1)-th main thread. Therefore, the arrival time ti as well as its linked ti,j of a new main thread can be sampled through our NesTPP model (Eq. 2 and 3) simultaneously.

Table 1: Dataset Overview

Final Popularity. As aforementioned, one can estimate the final cascade size by the standard simulation techniques. However, there also exists a closed-form solution to calculate the expected number of future events in the cascade. Explicitly, as introduced in [14], the branching factor n[∗] of the TPP can be employed to estimate the final cascade size. Through the branching factor, it is also possible to estimate the potential breakout of an information cascade [30]. We obtain the closed-form expression of the branching factor of the main thread stream by integrating the memory kernel ψ (t) of our main thread stream intensity function (Eq. 3).

Corollary 3.1. The infectious rate n[∗]main [of the main thread in]

proposed NesTPP model is the integral of the memory kernel ψ (·) in Eq. 3.

λ[i]reply[(][t][) ·][ p]i[γ] [· (][c][ −] [t][i] [)][η] �

m �

i=1

n[∗]main [=]

∫ ∞

ψ (t |Ht ) = 0

�

The branching factor n[∗]main [describes the expected number of]

main threads in a complete process, or informally, the virality of the cascade. n[∗]main [can also indicate whether the information cascade]

will become an infinite set, i.e., the outbreak of information cascade. For the infectious rate in the subcritical state (n[∗]main [<][ 1), the size]

of the information cascade is bounded, which makes it possible to predict the ultimate popularity Rmain[∞] [of the cascade. Conversely,]

the main thread stream would be viral if the infectious rate is in the supercritical state (n[∗]main [>][ 1). When][ n][∗] [is in the subcritical state,]

the closed-form of the expected number of future thread events Rmain[∞] [is given by:]

Rmain[∞] [=]

∞ 1 �(n[∗]main[)][i] [=]

0 1 − n[∗]main

Similarly, one can also identify the infectious rate of reply streams of each main thread by the integral of the reply stream memory kernel function (Eq. 2).

4 EXPERIMENT

In this section, we present the experiments done for a) examining the effect of the correlation between main threads and associated replies in modeling the cascade dynamics and b) evaluating NesTPP by comparing it with other approaches. In addition, we show that NesTPP, as a visualization tool, can explicitly characterize the correlation between event streams of different types. For reproducibility, we maintain this project on our Github repository[2].

4.1 Experiment Setup

Data. We adopted the dataset of Reddit and selected two popular subforums: Sports and Movie. For the Sports dataset, we collected

2https://github.com/lingchen0331/NesTPP

85000

80000

2.0

1.5

NesTPP NesTPP w/o. Main

0 1 2 3 4 5 6 7 8 9 Simulated Events Number (N = 10)

75000

70000

1.0

0.5

65000

Col1	Col2	NesT NesT	PP PP w/	o. Ma	in	Col7	Col8	Col9	Col10	Col11

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

40 39 Ground Truth +1.5554e9 NesTPP 35 33 NesTPP w/o. Main Ground Truth 32 32 NesTPP 30 30 30 29 NesTPP w/o. Reply 25 24 25 25 Numbers 21 20 19 18 17 Reply 15 13 10 5	Col2	Col3	Col4	Col5	Col6	Col7	Col8	Col9	Col10	Col11	Col12	Col13	Col14	Col15	Col16	Col17	Col18	Col19	Col20	Col21	Col22	Col23
+1.5554e9 ~~Ground Truth~~ NesTPP NesTPP w/o. Reply 5 10 15 20 25 30 35 40 Reply Numbers 30 39 25 18 32 32 33 30 25 29 24 21 13 19 17 Ground Truth NesTPP NesTPP w/o. Main	+1.5554e9 ~~Ground Truth~~ NesTPP NesTPP w/o. Reply 5 10 15 20 25 30 35 40 Reply Numbers 30 39 25 18 32 32 33 30 25 29 24 21 13 19 17 Ground Truth NesTPP NesTPP w/o. Main	+1.5554e9 ~~Ground Truth~~ NesTPP NesTPP w/o. Reply 5 10 15 20 25 30 35 40 Reply Numbers 30 39 25 18 32 32 33 30 25 29 24 21 13 19 17 Ground Truth NesTPP NesTPP w/o. Main	+1.5554e9 ~~Ground Truth~~ NesTPP NesTPP w/o. Reply 5 10 15 20 25 30 35 40 Reply Numbers 30 39 25 18 32 32 33 30 25 29 24 21 13 19 17 Ground Truth NesTPP NesTPP w/o. Main	+1.5554e9 ~~Ground Truth~~ NesTPP NesTPP w/o. Reply 5 10 15 20 25 30 35 40 Reply Numbers 30 39 25 18 32 32 33 30 25 29 24 21 13 19 17 Ground Truth NesTPP NesTPP w/o. Main	+1.5554e9 ~~Ground Truth~~ NesTPP NesTPP w/o. Reply 5 10 15 20 25 30 35 40 Reply Numbers 30 39 25 18 32 32 33 30 25 29 24 21 13 19 17 Ground Truth NesTPP NesTPP w/o. Main	+1.5554e9 ~~Ground Truth~~ NesTPP NesTPP w/o. Reply 5 10 15 20 25 30 35 40 Reply Numbers 30 39 25 18 32 32 33 30 25 29 24 21 13 19 17 Ground Truth NesTPP NesTPP w/o. Main	+1.5554e9 ~~Ground Truth~~ NesTPP NesTPP w/o. Reply 5 10 15 20 25 30 35 40 Reply Numbers 30 39 25 18 32 32 33 30 25 29 24 21 13 19 17 Ground Truth NesTPP NesTPP w/o. Main	+1.5554e9 ~~Ground Truth~~ NesTPP NesTPP w/o. Reply 5 10 15 20 25 30 35 40 Reply Numbers 30 39 25 18 32 32 33 30 25 29 24 21 13 19 17 Ground Truth NesTPP NesTPP w/o. Main	+1.5554e9 ~~Ground Truth~~ NesTPP NesTPP w/o. Reply 5 10 15 20 25 30 35 40 Reply Numbers 30 39 25 18 32 32 33 30 25 29 24 21 13 19 17 Ground Truth NesTPP NesTPP w/o. Main	+1.5554e9 ~~Ground Truth~~ NesTPP NesTPP w/o. Reply 5 10 15 20 25 30 35 40 Reply Numbers 30 39 25 18 32 32 33 30 25 29 24 21 13 19 17 Ground Truth NesTPP NesTPP w/o. Main	+1.5554e9 ~~Ground Truth~~ NesTPP NesTPP w/o. Reply 5 10 15 20 25 30 35 40 Reply Numbers 30 39 25 18 32 32 33 30 25 29 24 21 13 19 17 Ground Truth NesTPP NesTPP w/o. Main	+1.5554e9 ~~Ground Truth~~ NesTPP NesTPP w/o. Reply 5 10 15 20 25 30 35 40 Reply Numbers 30 39 25 18 32 32 33 30 25 29 24 21 13 19 17 Ground Truth NesTPP NesTPP w/o. Main	+1.5554e9 ~~Ground Truth~~ NesTPP NesTPP w/o. Reply 5 10 15 20 25 30 35 40 Reply Numbers 30 39 25 18 32 32 33 30 25 29 24 21 13 19 17 Ground Truth NesTPP NesTPP w/o. Main	+1.5554e9 ~~Ground Truth~~ NesTPP NesTPP w/o. Reply 5 10 15 20 25 30 35 40 Reply Numbers 30 39 25 18 32 32 33 30 25 29 24 21 13 19 17 Ground Truth NesTPP NesTPP w/o. Main	+1.5554e9 ~~Ground Truth~~ NesTPP NesTPP w/o. Reply 5 10 15 20 25 30 35 40 Reply Numbers 30 39 25 18 32 32 33 30 25 29 24 21 13 19 17 Ground Truth NesTPP NesTPP w/o. Main	+1.5554e9 ~~Ground Truth~~ NesTPP NesTPP w/o. Reply 5 10 15 20 25 30 35 40 Reply Numbers 30 39 25 18 32 32 33 30 25 29 24 21 13 19 17 Ground Truth NesTPP NesTPP w/o. Main	+1.5554e9 ~~Ground Truth~~ NesTPP NesTPP w/o. Reply 5 10 15 20 25 30 35 40 Reply Numbers 30 39 25 18 32 32 33 30 25 29 24 21 13 19 17 Ground Truth NesTPP NesTPP w/o. Main	+1.5554e9 ~~Ground Truth~~ NesTPP NesTPP w/o. Reply 5 10 15 20 25 30 35 40 Reply Numbers 30 39 25 18 32 32 33 30 25 29 24 21 13 19 17 Ground Truth NesTPP NesTPP w/o. Main	+1.5554e9 ~~Ground Truth~~ NesTPP NesTPP w/o. Reply 5 10 15 20 25 30 35 40 Reply Numbers 30 39 25 18 32 32 33 30 25 29 24 21 13 19 17 Ground Truth NesTPP NesTPP w/o. Main	+1.5554e9 ~~Ground Truth~~ NesTPP NesTPP w/o. Reply 5 10 15 20 25 30 35 40 Reply Numbers 30 39 25 18 32 32 33 30 25 29 24 21 13 19 17 Ground Truth NesTPP NesTPP w/o. Main	30 39 25 18 32 32 33 30 25 29 24 21 13 19 17 Ground Truth NesTPP NesTPP w/o. Main	Ground Truth NesTPP NesTPP w/o. Main
		Gr Ne Ne	~~oun~~ sTP sTP	~~d T~~ P P w	~~ruth~~ /o.	Repl	y

P1 P2 P3 P4 P5 Events with Replies Greater Than 15

Simulated Events Number (N = 20)

(a) Trend of Main Thread Arrival Time (Sports)

(b) Comparison of Sampled Reply Number (Sports)

(c) MAE in Sampled Reply Time (Sports)

all the main threads and their replies related to the famous NBA player LeBron James during the NBA Playoffs (April 2019), which attracts the most attention in a season. For the movie dataset, we retrieved the discussions of the popular movie Avengers: Endgame during the first week since the movie was released. Note that the selection of thread-reply cascades has to be topic-related, since the whole community of an ODF is topic-driven. Table 1 gives an overview of two datasets. For both threads and replies, we use UNIX Epoch time to denote the arrival time of events, which is a 10-digit sequence of seconds. Additionally, it can be seen from the table that the distinction in reply density (replies per thread) is obvious, which indicates the main threads in Sports subforum tend to draw more attention than threads in Movie subforum. Moreover, considering the time granularity of both datasets, the amount of the threads in the movie subforum is much more than those in the Sports subforum indicating a different event diffusion pattern. We aim at examining the capability of NesTPP in mining different event patterns with different reply densities.

Evaluation Metrics. We employ the following evaluation met- rics to validate the prediction accuracy in our experiment:

Mean Absolute Error in Event Time (MAEt ):

MAEt = [1] � |ti − t[¯]i |,

ti ∈T

where T = {t1, t2, ...} and T[¯] = {t[¯]1, t[¯]2, ...} are the sequences of ground-truth and simulated event arrival time, respectively. The arrival times ti and t[¯]i in both T and T[¯] are ordered chronologically.

Mean Absolute Error in Total Cascade Size (MAEn ):

time window T in Alg. 2 can affect the prediction accuracy in different experiments. In the following experiments, T is set to be 5 seconds in the event arrival time prediction and 100 seconds in the total cascade size prediction.

4.2 The Correlation Between Main Threads and Reply Posts

In the first experiment, we aim to examine whether or not modeling the nested structure can help better predict the future cascade evolution by comparing NesTPP with regular Hawkes-based models that view each stream as a separate point process. To this end, we modify the intensity function of the main thread stream and reply stream (Eq. 2 and 3) assuming the information dynamics of both event streams do not affect each other. The modified conditional intensity functions λmain[′] [(·)][ and][ λ]reply[′] [(·)][ are defined by:]

p · (t − ti + c)[−(][η][+][1][)], (5)

λmain[′] [(][t][)][ =][ µ][main][ +]

�

i=1

and

αe[−][β] [(][t] [−][t][j] [)], (6)

λreply[′] [(][t][)][ =][ µ][reply][ +]

ni �

MAEn = |n − n¯|,

where the n and n¯ are the ground truth information cascade size (i.e., the total number of simulated replies) and predicted cascade size, respectively. Furthermore, the simulations of all experiments were repeated until the results converge. We observed that typically 100 times of simulations would be sufficient for such purpose. During the experiment, we found that the different settings of reply simulation

j=1

where p ∈ R[+] in Eq. 5 is a parameter which denotes the infectious rate in the power law decaying function [12].

Influence of Reply Events to Main Threads. To explore the influence of reply stream in modeling the dynamics of main thread cascade, we fit the NesTPP model with 1, 000 randomly-picked consecutive main threads with associated replies; and we train the control model only with the main threads by the intensity function (Eq. 5). Next, the two fitted models are applied to simulate the arrival time of the next 20 threads and compare the simulation results with the arrival time of ground truth threads. The growth trend of both models is shown in Fig. 3a. As shown in the figure, NesTPP consistently outperforms the regular Hawkes-based model. Moreover, there exists a relatively long delay in the arrival time between 9-th and 11-th main threads in the figure. As one can see, the NesTPP can infer and predict such a delay by considering the influence of the reply stream, while the control model fails to

Sports Dataset

1 0.059 ± 0.017 0.037 ± 0.05 0.016 ± 0.04 0.026 ± 0.015 5 0.174 ± 0.039 0.093 ± 0.07 0.065 ± 0.027 0.049 ± 0.08 10 0.313 ± 0.07 0.156 ± 0.12 0.138 ± 0.11 0.112 ± 0.073 20 0.569 ± 0.17 0.441 ± 0.12 0.258 ± 0.39 0.221 ± 0.174 30 0.843 ± 0.34 0.612 ± 0.19 0.479 ± 0.7 0.387 ± 0.456

Col1	Col2	Poisson	Hawkes	SEISMIC	NesTPP
Sports Dataset	1 5 10 20 30	0.059 ± 0.017 0.174 ± 0.039 0.313 ± 0.07 0.569 ± 0.17 0.843 ± 0.34	0.037 ± 0.05 0.093 ± 0.07 0.156 ± 0.12 0.441 ± 0.12 0.612 ± 0.19	0.016 ± 0.04 0.065 ± 0.027 0.138 ± 0.11 0.258 ± 0.39 0.479 ± 0.7	0.026 ± 0.015 0.049 ± 0.08 0.112 ± 0.073 0.221 ± 0.174 0.387 ± 0.456
Movie Dataset	1 3 6 9 15	3.755 ± 1.72 5.371 ± 3.42 8.19 ± 6.28 9.75 ± 6.94 12.04 ± 4.4	1.084 ± 0.83 1.834 ± 1.24 3.49 ± 1.13 4.807 ± 1.35 7.46 ± 1.8	1.215 ± 0.46 1.923 ± 1.39 2.784 ± 1.81 3.742 ± 1.94 6.32 ± 2.73	0.546 ± 0.84 1.057 ± 0.03 1.66 ± 1.14 2.216 ± 1.35 3.34 ± 1.77

Col1	Col2	Poisson	Hawkes	SEISMIC	NesTPP
Sports Dataset	1 5 10 15 20	1.694 ± 1.71 1.8 ± 1.28 1.91 ± 1.29 1.852 ± 1.14 2.012 ± 1.3	0.62 ± 0.4 1.616 ± 1 2.949 ± 1.63 4.01 ± 1.76 4.91 ± 1.84	0.55 ± 0.3 1.011 ± 0.88 1.62 ± 1.5 1.92 ± 1.67 2.08 ± 1.75	0.42 ± 0.51 0.989 ± 0.86 1.579 ± 1.65 1.788 ± 1.26 1.838 ± 1.28
Movie Dataset	1 5 10 15 20	1.78 ± 1.26 1.84 ± 1.28 1.85 ± 1.22 1.929 ± 1.31 2.089 ± 1.74	0.94 ± 0.89 1.19 ± 0.91 1.146 ± 0.73 1.571 ± 1.12 2.316 ± 1.74	0.78 ± 0.67 0.955 ± 0.47 1.386 ± 0.95 1.552 ± 1.04 2.137 ± 1.45	0.22 ± 0.06 0.65 ± 0.07 1.181 ± 0.13 1.536 ± 0.19 1.968 ± 0.27

Table 2: Adaptive Prediction of Main Thread Arrival Time

capture such subtle changes as the resulted curve tends to be stable all along.

Influence of Main Threads to Reply Events. We also aim at examining the influence of main threads in predicting the number and arrival time of linked replies. Similarly, we fit NesTPP with 47, 876 reply events as well as the 1, 000 consecutive main threads and simulate the reply stream of immediate 20 main threads. In the control model, we assume that the reply stream dynamics is governed by a unified point process, and we only fit 47, 876 replies into the intensity function (Eq. 6) and simulate the total number of replies for the next 20 main threads.

We begin by comparing the accuracy of forecasting the number of replies under each main thread, and we focus only on the main threads that have more than 15 replies for examining the model capability in predicting the large volume replies. Fig. 3b shows the result of the total number of simulated reply events between both experiment models and ground-truth data. On average, the prediction under NesTPP is closer to the ground truth comparing with the one without considering the influence of main thread stream, which demonstrates the positive impact of main thread stream information in forecasting the reply stream dynamics.

Furthermore, we also validate our model in estimating the arrival time of replies under each parent thread. Similarly, we focus on examining the reply reaction time of those threads by the average MAE of the first 10 replies reaction time among those threads were recorded in Fig. 3c. As the simulated reply number increases, the MAE in time also increases in both models. However, NesTPPsimulated reply time still outperforms the Hawkes-based control model. Therefore, modeling the influence of main thread stream is also effective in predicting the future reply dynamics. Taken together, the nested structure of the ODF and the correlation between the main thread and associated replies are helpful in estimating the future cascade evolution.

4.3 The Comparison with Existing Approaches

In the second experiment, we assess the performance of NesTPP with other state-of-the-art approaches in terms of predicting the temporal dynamics of information cascade. Note that the selected methods were originally designed for different prediction tasks, and we slightly modify them to fit our data and scenario.

Baselines. We consider three TPP models for comparison, in- cluding the non-homogeneous Poisson Process, classic self-exciting

Table 3: Adaptive Prediction of Reply Arrival Time

point process (Hawkes Process), and the modified SEISMIC model introduced in [30]. The details of the selected models are as follows:

Poisson Process: The Poisson process is the basic model of

the TPP. We adopt the non-homogeneous Poisson process, in which the rate of event arrivals is a function of time, and it can intuitively be interpreted as events are arriving at an average rate of λ per unit time.

Hawkes Process: Hawkes Process has been extensively ap-

plied in modeling the temporal dynamics of information cascades in recent literature, and it is one of the most fundamental frameworks adopted in the existing methods (

[6, 12, 17, 24]). We therefore only choose Hawkes Process as one of our baselines.

SEISMIC: As one of the state-of-the-art approaches, SEISMIC [30] has drawn much attention and followed by other

recent approaches ([12, 19, 24]). SEISMIC tries to predict the infectivity as well as the final cascade size of a tweet post. We follow the hyper-parameter setting used in the original paper. Note that we replace the follower’s count of a user in SEISMIC to the number of replies for feature consistency with our model.

We do not consider other multivariate TPP models since they can only fit and simulate fixed-dimension event sequences. In addition, other non-TPP models either utilized additional mark information or originally applied in other forms of online social networks, which also cannot be directly employed in our proposed scenario.

Prediction of Future Main Thread Stream. Let us first con- sider the problem of predicting the arrival time of the future main threads. As described in Sec. 3.5, NesTPP can simulate the arrival time of future main threads using the adaptive thinning technique. Alternatively, since other approaches do not consider the correlation between two event streams, we use standard thinning techniques [22] for other models to sample the arrival time of future threads. For both datasets, we apply cross-validation to measure the effectiveness of our model and select a total of 10 groups of 100 and 150 randomly-picked consecutive main threads with corresponding replies to simulate the arrival time of the next 20 main threads in different datasets. We record the average MAEt for the first main thread, the first 5 main threads, the first 10 main threads, the first 15 main threads, and the total simulated threads. The result of MAEt are summarized in Table 2. As shown in the table, the average MAEt of all models in the sampled threads arrival time increase with time, and NesTPP outperforms other approaches

NesTPP 56.61 87.85 95.25 239.81 400.75

Table 4: Total Cascade Size Prediction of Sports Dataset

by a lower average error. For other baselines, the simulation of the Poisson process does not incorporate any provided previous main thread history and reply stream information. Therefore, the deviation of the first simulated event arrival time is less accurate than other approaches. However, for this reason, the rate of error cumulation in the adaptive prediction of the Poisson process is slower than other baselines. For other baselines that consider the historical main thread information, Hawkes process and SEISMIC have the close MAEt at the first few simulated main threads. The gaps in prediction performance with NesTPP gradually show as the number of simulated main threads grows. With the consideration of the reply stream, the NesTPP model can more accurately predict the temporal evolution of the main threads in terms of arrival time.

Prediction of Future Reply Stream. Similarly, following the experiment procedures in sampling the arrival time of the main threads, we now examine the performance of NesTPP in forecasting the reply stream dynamics. In specific, we aim to show the MAEt of the simulated reply arrival time of each main thread by given a limited history of each reply stream. Considering the difference between the reply density in different datasets, we choose to test the MAEt of different reply numbers in different datasets. We randomly select 100 and 50 reply streams and provide all models the beginning 10 reply arrival time of each reply stream in the Sports dataset and Movie dataset, respectively. We record the relative error of sampling a total of 30 and 15 subsequent replies in both datasets, and the results are shown in Table 3. Overall, by modeling the reply event infectivity in Eq. 2, NesTPP provides a consistent improvement in predicting the long-term reply stream diffusion dynamics comparing with other methods by an evident margin in both datasets. Although the MAEt of the first predicted replies in the Sports dataset are close among all baselines and the performance of NesTPP is not the best, it is needed to consider the high randomness of predicting a single event in the reply stream.

Total Cascade Popularity. In this experiment, we aim to test the model’s ability to predict the final cascade size (i.e., the total number of replies for all simulated main threads). We apply the adaptive sampling method to simulate the main threads and associated replies together. For other baselines, we firstly simulate the total number of main threads up to the pre-defined time limit, we then sample reply streams for each simulated main thread with the time limit up to the arrival time of the last simulated main thread. On both datasets, we apply 10-fold cross-validation to test the relative error MAEn between the prediction result and ground truth on the randomly-picked time point’s following time durations. Based on the different time granularity in both datasets, we choose to test the prediction performance with different window sizes. The results are summarized in Table 4 and 5.

Poisson 11.99 26.45 40.29 102.9 223.21 Hawkes 13.02 19.01 68.11 78.69 192.71 SEISMIC 16.78 21.43 45.51 68.54 132.94 NesTPP 6.99 10.13 33.61 56.75 96.35

Table 5: Total Cascade Size Prediction of Movie Dataset

LBJ is the

Best SF

Top 5 Small Forward

in the League?

Interesting fact

before Lebron reportedly hurt

04/25 04:32 PM 04/25 04:47 PM 04/25 04:50 PM Time

We can see from both tables that the average prediction errors for all models gradually increases with the enlarging prediction window size because of the accumulated bias exposure when conducting long-range prediction. In the Sports dataset, comparing with other non-homogeneous TPP, NesTPP can consistently provide a more reliable prediction result in different window sizes, and the margin becomes more evident as the time window size increases. Similarly, the relative prediction error of NesTPP in the Movie dataset also exhibits a clear prediction gap with other approaches. Considering the reply density varies in both datasets, NesTPP shows excellent robustness when forecasting the ODF temporal cascade size in different reply intensities. By modeling the nested structure and mutual influence between two event streams, NesTPP can capture the arrival frequency of replies and provide a more reliable prediction result.

In summary, NesTPP shows competitive results in different prediction tasks comparing with other state-of-the-art approaches in most cases. By modeling the natural nested structure with explicit intensity functions, NesTPP can be better served at characterizing the cascade dynamics in ODFs operated in the thread-reply mode.

4.4 Visualization of Correlation Between Cascades

In addition to the previous applications, NesTPP can be utilized as a tool to visualize the correlation between cascades. Through analyzing the value of the reply stream intensity in main thread intensity function (Eq. 3), one can determine the influence of the linked reply

Sports Dataset Model 0.5 Hrs 1 Hrs 3 Hrs 9 Hrs 12 Hrs	Col2
Poisson Hawkes SEISMIC NesTPP	64.09 108.4 98.52 364.17 468.5 63.89 109.36 114.63 380.1 459.26 60.91 98.64 101.12 316.03 425.75 56.61 87.85 95.25 239.81 400.75

Movie Dataset Model 0.5 Hrs 1 Hrs 3 Hrs 4.5 Hrs 6 Hrs	Col2
Poisson Hawkes SEISMIC NesTPP	11.99 26.45 40.29 102.9 223.21 13.02 19.01 68.11 78.69 192.71 16.78 21.43 45.51 68.54 132.94 6.99 10.13 33.61 56.75 96.35

Col1	Col2
E1

stream in modeling the main thread dynamics, so that the correlation between thread-reply cascade can thus be characterized. For a case study, we select three consecutive main threads E1, E2, and E3 discussing the famous basketball player - LeBron James during the NBA Playoffs in the Sports dataset, where each main thread is connected with a reply stream. In Fig. 4, we visually present such correlations according to the intensity values. Thread E1 has relatively fewer replies than others since users show less interest in the discussion topic, which illustrates that the non-topical thread fails to stimulate the arrival of a new thread with the similar content. After 15 minutes, the next thread debating a controversial topic of the player draws tremendous attention and rapidly generates a conversation wave. While the thread E2 is still under discussion, a new main thread E3 is posted after 3 minutes, which can be viewed as the continuity of the conversation in thread E2. More interestingly, the person who posts E3 is observed to be one of the repliers under the thread E2, which can be interpreted as the discussion rush of a controversial topic can rapidly spur the occurrence of a related thread in an ODF; and followers in the related threads may also turn to start a new thread discussing the similar content.

5 CONCLUSION AND FUTURE WORK

Conclusion. In this paper, by utilizing the self-exciting point pro- cess, we have introduced a novel framework - NesTPP that models the correlation between different types of event streams in the ODF using the arrival time of each event and self-contained mark information. Further, we have derived a maximum likelihood approach to estimate parameters in the proposed model. Two individual but correlated sampling methods are proposed to simulate the arrival of the future main threads and associated replies simultaneously. Through the competitive experiment results and additional applications, we verify the NesTPP is not only theoretically grounded but also effective in most cases.

Future Work. NesTPP can easily be transferred to other social network scenarios with the thread-reply communication structure. In addition, online users may reply to one of the replies in a cascade instead of directly replying to the main thread, which forms the so-called nest-of-nest structure. Modeling the nest-of-nest structure may capture more subtle changes in the temporal dynamics of the reply stream. Last but not least, recurrent neural networks (RNN) are prominent in modeling the complex sequential dependencies, and a few successful examples ([5, 18]) have applied the RNN architectures to replace the intensity function in the point process. One concrete future work is to employ multi-dimensional RNN to model the intricate nested communication structure in ODFs.

A PROOFS A.1 Likelihood Function Derivation

Given the finite set of the main thread stream arrival time up to but not including time t: Ht = {t1, ..., tm }, and the set of the arrival time of replies of i-th main thread H(ti,j ) = {ti,1, ti,2, ..., ti,ni } on the same timeline. Let f (t) be the joint conditional density function

of the time of the next event given the history of all previous events,

f (t |H(ti ), H(ti,j )) = f (t1, t1,1, t2, t2,1..., tm,1, ...)

ni �

j=1

(7) f (ti,j |Hti,j ),

m �

i=1

f (ti |Hti )

which considers the historical occurrence of all previous events from both main and reply stream. m denotes the total number of posts from main stream, and ni denotes the number of the reply stream events of the i-th main thread.

According to [10], the event intensity λ(t) for both event streams can be expressed in terms of the conditional density f (t) and its corresponding cumulative distribution function F (t):

f (t) λ(t) = 1 − F (t) [=]

∂ ∂t [F] [(][t][)] (8)

1 − F (t) [=][ −] ∂[∂]t [log][ (][1][ −] [F] [(][t][))][,]

where the λ(t) represents the conditional intensity function of main stream events as we stated in Eq. 3. For main stream posts, the conditional intensity function can be derived as integrating both sides of Eq. 8 over the interval (tm, t):

∫ t

λmain(u) du = log(1 − Fmain(tm )) − log (1 − Fmain(t))

= − log(1 − Fmain(t)).

(9)

Rearranging the Eq. 9, we can get the expression of cumulative density function Fmain(t), and joint probability density function

fmain(t) for main stream posts.

Fmain(t) = 1 − exp(−

∫ t

λmain(u) du)

fmain(t) = λmain(t) · exp(−

∫ t

λmain(u) du)

Similarly, we can get the expression of joint likelihood function for the reply stream of the i-th main stream:

∫ t

freply[i] [(][t][)][ =][ λ][i]reply[(][t][) ·][ exp][(−]

tm,ni

λ[i]reply[(][u][)][ d][u][)]

By introducing the reply thread stream and main stream intensity function (Eq. 2, 3) into the likelihood function Eq. 7, the complete likelihood function L can be derived as:

L =

m ni �[fmain(ti |Hti )] · �[freply[i] [(][t][i][,][j][ |H][t][i] [,][j][ )]]

i=1 j=1

�m �λmain(ti ) · exp(− ∫ ti λmain(u) du)

i=1 ti −1

�ni λ[i]reply[(][t][i] [) ·][ exp][(]∫ ti, j λ[i]reply[(][u][)][ d][u][)]�

j=1 ti, j−1

� �[m]

i=1

�

λmain(ti ) · λ[i]reply[(][t][i][,][j] [)]

ni �

j=1

∫ tm

λmain(u) du). 0

(10)

m � exp(−

i=1

∫ tni

tn1

λ[i]reply[(][u][)][ d][u][) ·][ exp][(−]

We can estimate the set of parameters of our NesTPP model by maximizing the likelihood function (Eq. 10). To avoid the potential underflow of calculating the very small likelihood, we instead maximize the log of the likelihood function:

l = log(L) =

� �[m] �

i=1 j=1

log(λmain(ti )) + log(λ[i]reply[(][t][i][,][j] [))]�

(11)

− Λmain(tm ) −

m �

i=1

Λ[i]reply[(][t][n][i][ )][,]

where the Λmain(tm ) and Λ[i]reply[(][t][n][i][ )][ in Eq. 11 represent the com-]

pensator of the main and reply event streams. We also present the derivation of both compensators here.

Λmain(tm ) =

∫ tm

λmain(u) du 0

∫ tm

µmain + ψmain(u, tm ) du 0

∫ tm m−1 ∫ i+1

µmain + � ψmain(u, tm ) du 0 0 i

(12)

= µmaintm +

m �

i=1

∫ tm

ψmain(u, ti ) du.

By introducing Eq. 3 into Eq. 12, we have the complete equation of main stream compensator Λmain(·).

m �

i=1

Λmain(tm ) =

∫ tm

� µreply + q(tm ) ·

λ[i]reply[(][t][i] [)(][p][i] [)][γ][ (][u][ −] [t][i] [+][ c][)][−(][1][+][η][)][ d][u]

µmaintm

Figure 1: The Nested Diffusion Structure in ODFs

Figure 2: The relation between main thread stream and reply stream simulated by NesTPP. The upper figure shows the evolution of event intensity, and the lower figure depicts a slice of the event pattern including both main threads and associated reply events. It is clear from the figure that thread t6 draws tremendous replies and effectively stimulates the arrival of next thread t7.

Figure 3: After training with 1, 000 consecutive main threads and 47, 876 associated replies, we show the performance in different evaluation metrics between NesTPP and NesTPP without the influence of the main thread or reply event stream. In general, the NesTPP model exhibits a better performance in each experiment, which indicates the effectiveness of the correlation between the main thread stream and associated reply stream in modeling information dynamics.

Figure 4: Correlation visualization between cascades: The yellow node Ei represents the main threads occurs in a non- negative timeline, and the associated blue nodes linked to a main thread denote the replies to the main thread.

REFERENCES

[1] Sitaram Asur and Bernardo A Huberman. 2010. Predicting the future with social

media. In Proc. of WI-IAT. 492–499.

[2] Erik Aumayr, Jeffrey Chan, and Conor Hayes. 2011. Reconstruction of threaded

conversations in online discussion forums. In Proc. of AAAI ICWSM.

[3] Mordecai Avriel. 2003. Nonlinear programming: analysis and methods. Courier

Corporation.

[4] Charles Blundell, Jeff Beck, and Katherine A Heller. 2012. Modelling recipro cating relationships with Hawkes processes. In Advances in Neural Information Processing Systems. 2600–2608.

[5] Qi Cao, Huawei Shen, Keting Cen, Wentao Ouyang, and Xueqi Cheng. 2017. Deep hawkes: Bridging the gap between prediction and understanding of information cascades. In Proc. of CIKM.

[6] Feng Chen and Tanwai Hong. 2018. Marked self-exciting point process modelling

of information diffusion on Twitter. ANN APPL STAT 12, 4 (2018), 2175–2196.

[7] Justin Cheng, Lada Adamic, P Alex Dow, Jon Michael Kleinberg, and Jure

Leskovec. 2014. Can cascades be predicted?. In Proc. of WWW. 925–936.

[8] Mehrdad Farajtabar, Yichen Wang, Manuel Gomez-Rodriguez, Shuang Li,

Hongyuan Zha, and Le Song. 2017. Coevolve: A joint point process model for information diffusion and network evolution. The Journal of Machine Learning Research 18, 1 (2017), 1305–1353.

[9] Vicenç Gómez, Hilbert J Kappen, and Andreas Kaltenbrunner. 2011. Modeling

the structure and evolution of discussion cascades. In Proc. of HT. 181–190.

[10] Alan G Hawkes. 1971. Point spectra of some mutually exciting point processes.

Journal of the Royal Statistical Society: Series B 33, 3 (1971), 438–443.

[11] Tomoharu Iwata, Amar Shah, and Zoubin Ghahramani. 2013. Discovering latent

influence in online social activities via shared cascade poisson processes. In Proc. of SIGKDD. 266–274.

[12] Ryota Kobayashi and Renaud Lambiotte. 2016. Tideh: Time-dependent hawkes

process for predicting retweet dynamics. In Proc. of ICWSM.

[13] Andrew S Lan, Jonathan C Spencer, Ziqi Chen, Christopher G Brinton, and Mung

Chiang. 2018. Personalized thread recommendation for MOOC discussion forums. In Proc. of ECML PKDD. 725–740.

[14] Patrick J Laub, Thomas Taimre, and Philip K Pollett. 2015. Hawkes processes.

arXiv preprint arXiv:1507.02822 (2015).

[15] Scott Linderman and Ryan Adams. 2014. Discovering latent network structure

in point process data. In Proc. ICML. 1413–1421.

[16] Shengzhong Liu, Shuochao Yao, Dongxin Liu, Huajie Shao, Yiran Zhao, Xinzhe

Fu, and Tarek Abdelzaher. 2019. A Latent Hawkes Process Model for Event Clustering and Temporal Dynamics Learning with Applications in GitHub. In Proc. of ICDCS. 1275–1285.

[17] Alexey N Medvedev, Jean-Charles Delvenne, and Renaud Lambiotte. 2018. Mod elling structure and predicting dynamics of discussion threads in online boards. Journal of Complex Networks 7, 1 (2018), 67–82.

[18] Hongyuan Mei and Jason M Eisner. 2017. The neural hawkes process: A neurally

self-modulating multivariate point process. In Proc. of NIPS. 6754–6764.

[19] Swapnil Mishra, Marian-Andrei Rizoiu, and Lexing Xie. 2016. Feature driven and

point process approaches for popularity prediction. In Proc. of CIKM.

[20] Nasir Naveed, Thomas Gottron, Jérôme Kunegis, and Arifah Che Alhadi. 2011.

Bad news travel fast: A content-based analysis of interestingness on twitter. In Proc. of WWW.

[21] Ryosuke Nishi, Taro Takaguchi, Keigo Oka, Takanori Maehara, Masashi Toyoda,

Ken-ichi Kawarabayashi, and Naoki Masuda. 2016. Reply trees in twitter: data analysis and branching process models. SNAM 6, 1 (2016), 26.

[22] Yosihiko Ogata. 1981. On Lewis’ simulation method for point processes. ITIT 27,

1 (1981), 23–31.

[23] Tohru Ozaki. 1979. Maximum likelihood estimation of Hawkes’ self-exciting

point processes. ANN I STAT MATH 31, 1 (1979), 145–155.

[24] Marian-Andrei Rizoiu, Lexing Xie, Scott Sanner, Manuel Cebrian, Honglin Yu, and

Pascal Van Hentenryck. 2017. Expecting to be hip: Hawkes intensity processes for social media popularity. In Proc. of WWW. 735–744.

[25] Richard M Smedley and Neil S Coulson. 2018. A practical guide to analysing

online support forums. Qualitative Research in Psychology (2018), 1–28.

[26] Matthew JW Thomas. 2002. Learning within incoherent structures: The space

of online discussion forums. Journal of Computer Assisted Learning 18, 3 (2002), 351–366.

[27] Chunyan Wang, Mao Ye, and Bernardo A Huberman. 2012. From user comments

to on-line conversations. In Proc. of SIGKDD. 244–252.

[28] Norazah Yusof, Azizah Abdul Rahman, et al. 2009. Students’ interactions in online

asynchronous discussion forum: A Social Network Analysis. In 2009 International Conference on Education Technology and Computer. 25–29.

[29] Tauhid R Zaman, Ralf Herbrich, Jurgen Van Gael, and David Stern. 2010. Predict ing information spreading in twitter. In Workshop on computational social science and the wisdom of crowds, nips, Vol. 104. 17599–601.

[30] Qingyuan Zhao, Murat A Erdogdu, Hera Y He, Anand Rajaraman, and Jure

Leskovec. 2015. Seismic: A self-exciting point process model for predicting tweet popularity. In Proc. of SIGKDD.

m �

i=1

αe[−][β] [(][t][i] [−][t][i] [,][j] [)][�]

(13)

� �µreply + q(tm ) · � αe

i=1 ti,j <ti

[−] [t][i] [+][ c][)][−][η]

(pi )[γ][ �] ηc[1][η] [−(][t][m] η

�

µmaintm .

Similarly, we can derive the reply stream compensator Λ[i]reply[(·)][.]

∫ t1 ni −1 ∫ tj+1

Λ[i]reply[(][t][n][i][ )][ =] µreply du + � µreply

0 j=1 tj

q(u) · � αe[−][β] [(][u][−][t][k][ )] du

tk <u

= µreplytni + q(tnm −1) · α � [n]�m [−][1] ∫ tj

j=1 tj+1

j �

k =1

e[−][β] [(][u][−][t][k][ )]u

�

�e[−][β] [(][t][ni][ −][t][j] [)] − 1� .

= µreplytni − [α]

β [·][ q][(][t][n][m][ )]

nm �

β j=1

(14) Finally, we have different intensity functions (Eq. 2 and 3) and compensators (Eq. 12 and 14) for the main thread stream and reply event stream, respectively. The complete log-likelihood function that we aim to maximize can be derived from introducing the above equations into the log-likelihood function Eq. 11.