LMPP: A Large Margin Point Process Combining Reinforcement and Competition for Modeling Hashtag Popularity

1 Introduction

To improve the efficacy of Twitter, prediction of hashtag flow (e.g., early detection of trending hashtags [Mathioudakis and Koudas, 2010]) is important. Thus, a large amount of research on viral marketing and information cascades [Cheng et al., 2016; Chakraborty et al., 2016; Sikdar et al., 2016] have focused on analyzing hashtag-popularity and its role in tweet propagation.

Prior works and their limitations: Research on predictive aspects of hashtag-popularity primarily follows two kinds of models: (i) Static feature-based models ([Rosenfeld et al., 2016; Bourigault et al., 2014; Shi et al., 2016] and the citations therein), and (ii) Temporal models ([Zhao et al., 2015; Kobayashi and Lambiotte, 2016; Bi and Cho, 2016; De et al., 2016a; Iwata et al., 2013; De et al., 2014; Kupavskii et al., 2012; Hua-Wei et al., 2014; Shuai and Jun, 2015; Gao et al., 2016; Ferraz Costa et al., 2015; Bao et al., 2015; Gomez-Rodriguez et al., 2011; De et al., 2016b]). In the static models, the temporal properties (e.g., time of posts, no. of retweets) are embedded into feature maps, and the parameters are learned following a supervised approach. However, in practice, future temporal properties are not known in advance, which in turn constrains their forecasting prowess. The temporal models aim to address this shortcoming by modeling the stochastic nature of hashtag-dynamics, using point-process, survival theory, etc. However, most existing temporal models focus on tweet-propagation rather than hashtags, thereby skirting several realistic aspects of hashtag-flow, and resulting in modest prediction performance. More importantly, they are largely unable to reproduce any microscopic feature in hashtag dynamics (e.g., relative popularity variation, sudden trend change etc.).

In general, the popularity of a hashtag depends on two primary factors: (i) hashtag-tweet reinforcement, and (ii) interhashtag competitions. Every hashtag has an intrinsic attractiveness, and similarly the tweets bearing the hashtag also have their own appeal. In our earlier work [Samanta et al., 2017], we showed that these two factors often reinforce each other. For example, an unpopular hashtag sometimes becomes viral due to the presence of some popular tweets. Similarly, a not-so-popular tweet may become popular later on due to the popularity of the hashtag it is bearing. Since traditional temporal approaches bank on modeling only tweetpropagation, simply extending these prediction-frameworks to hashtags, would not produce accurate results (our experimental results also emphatically establish that).

However, considering only the hashtag-tweet reinforcement process still leaves a paucity in the realistic modeling of hashtag-flow, that demands a careful consideration of the inter-hashtag competitions. In many cases, a newly popular hashtag may abbreviate the visibility of other popular hashtags. For example, often a breaking-news hails new hashtags which quickly get popularized and in the process, at least for a short span of time, suppress the popularity of other consistently popular hashtags, i.e., in practice, two hashtags often compete, rather than reinforcing each other's dissemination. Some recent works [Valera and Gomez-Rodriguez, 2015; Myers and Leskovec, 2012] attempted to model competitions in different contexts; however, they rely heavily on featureengineering and underlying networks [De et al., 2013], making them inefficient in online learning.

Present work and road-map: In this paper, we develop Large Margin Point Process (LMPP), a novel probabilistic framework that models the dynamics of hashtag popularity by unifying the above two factors in a principled way. The inherent hashtag-popularity often reinforces the virality of its constituent tweet-chains and vice-versa, which LMPP aims to capture using a generalized triggering kernel. In this process, LMPP considers the hashtag-tweet reinforcement factor to vary widely across the popularity distribution of tweets.

Furthermore, LMPP aims to incorporate competition among the hashtags and its impact on hashtag dynamics. In order to do that, we probe into the variations in the popularity rankings of the concurrent and related hashtags. Therefore, to capture such signals, we suitably curate the parameter space of LMPP that ensures correct ordering of popularity across several time intervals. Such a formulation intuitively articulates the competition process, without drastically changing the model-setting. In fact, this additional trait helps to properly train the model, which in turn enables it to detect sudden drifts in popularity rankings of the competing hashtags.

Our contributions: Summarizing, in this paper, we develop a novel stochastic framework for modeling hashtag dissemination, that unifies the role of hashtag-tweet reinforcement process and inter-hashtag competition in a principled way. LMPP can also be seen as an instance of a large-margin estimation where the constraints utilize the popularity differences among competing hashtags, thereby enabling the model to maximize the associated popularity margins along with the corresponding likelihood. Such a setting helps the model to estimate ranks on the fly, a crucial practical challenge that was left unaddressed in the literature. On seven real-world datasets crawled from Twitter, LMPP offers substantial accuracy gains in predicting popularity of hashtags, beyond strong baselines. By accurately considering the competition process, it can successfully model the ranking dynamics over time, of the correlated hashtags, which none of the existing baselines can even consistently trace. Consequently, it can reasonably forecast the abrupt popularity changes of hashtags which, in general, is considered a difficult phenomenon to reproduce.

2 ProposedModel

2.1 Overview

Terminology: We define a tweet-chain as the set consisting of a tweet and all its retweet instances. In this work, we represent a tweet by a unique id, and a tweet-chain in terms of the posting times of the tweet and all her retweets. Formally, a tweet-chain Ci, corresponding to tweet i, can be written as Ci = {tj|tweet i is (re)tweeted at time tj}. Similarly, a hashtag H can be expressed in terms of the tweet-chains, H = {Ci|Ci is a tweet-chain bearingH}. Finally, the history of the hashtag H until and excluding time t, HH(t) can be represented as the union of the posting times of the corresponding (re)tweets posted before t.

Computation of hashtag popularity: In a similar spirit to [Zhao et al., 2015], we measure the popularity of a hashtag by the total number of its constituent tweet-posts. To do so, we propose LMPP, that models the temporal dynamics of the constituent tweets of a hashtag in terms of post-rate. While modeling such a post-rate, LMPP combines the role of hashtag-tweet reinforcement and hashtag competitions in the overall popularity dynamics.

Basic generative process for tweet-chains: At the outset, we represent the posting times of the (re)tweets as a pointprocess model. In particular, given a hashtag H, we define the counting variable as NH(t), where NH(t) ∈ {0} ∪ Z+ counts the number of (re)tweets posted until and excluding time t. Then, we characterize the conditional probability of observing an event in infinitesimal time interval [t, t+dt)] as

i.e., EdNH(t)∼{0,1}[dNH(t)|HH(t)] = λH(t)dt (2) Here dNH(t) indicates the number of (re)tweets in the infinitesimal time-window [t, t + dt) and λH(t) stands for the associated hashtag intensities, which further depends on the history HH(t). The functional form of λH(t) is chosen to capture the phenomenon of interests that possibly encompass hashtag-competitions, self-exciting dynamics or hashtag-tweet interactions. In the following, we present a specific characterization of λH(t) that captures the selfexciting nature of hashtag dynamics.

Self-exciting dynamics: To capture the mutual excitation between (re)tweet posting events, we rely on Hawkes process [Farajtabar et al., 2014; De et al., 2016b]. It is a particular type of functional form used in the growing literature on social activity modeling using point processes [Farajtabar et al., 2014; Valera and Gomez-Rodriguez, 2015]:

Here, λH,0 ⩾ 0, models the initial post-rate of (re)tweets, and the second term, with β ⩾ 0, assigns weight to the influence of the publication of earlier (re)tweets. κ(t) = e-ω0t is an exponential triggering kernel indicating the decay of influence of the past events over time, and ⋆ denotes the convolution operation.

2.2 LMPP: Modeling Hashtag-tweet Reinforcement and Inter-hashtag Competitions

Apart from the inherent popularity dynamics of the tweetchains, our proposed framework LMPP considers two more crucial factors in modeling the popularity dynamics of a hashtag: (i) the mutual reinforcement process between hashtags and tweets, and (ii) the competitions among hashtags.

We observe that, it is the intensity kernel κ(t) (in Eq (3)) that accounts for the self-exciting mechanism for the Hawkes process. Therefore, we aim to construct a suitable κ(t) which should, along with the self-exciting reinforcement process of the individual tweets, capture the hashtag-tweet reinforcement factor. Note that, the influence of a hashtag is only exposed through the tweets, and the effect of the hashtag on a tweet is more enunciated via a popular tweet than a rare tweet. Therefore, the hashtag-tweet reinforcement factor should vary across the popularity distribution of the tweets. Thus, the kernel should be further parameterized by tweetpopularity index k (defined in Section 2.3), to have κk(t). Particularly, κk(t) should be chosen in such way that:

• Given a hashtag, when a popular tweet is retweeted i.e., when k goes high, the inherent attractiveness of the hash-

tag heavily influences its propagation process. That is, κk(t) pushes λH(t) more towards a Hawkes process. Therefore, the overall resulting dynamics become more and more bursty.

· For non-popular tweets, the effect of the resultant influence of the hashtag is very low on its propagation process. Thus, a low value of κk(t) should fare in a relatively small λH (t).

Considering the above points, we take κk(t) as

κk(t) has two factors. κ∞(t) indicates the self exciting process of the tweets, while e- ωt k stands for the hashtag-tweet influence. Note that, the impact of a tweet on the hashtag grows high, as the popular tweets get posted and vice-versa. Furthermore, we try to approximate κ∞(t) as a more generalized intensity kernel κ∞(t) = ∑Mj=1 βje-ωjt where M is a large integer.

Then, the arrival rate of tweets can be written as

Here, k(ti) is the popularity of tweet posted at time ti, and k(t) := {k(ti)|ti ∈ HH(t)}. For compactness, we denote ω = [ω1, ω2, ....ωM]. Here, an additional decay factor e-ϵt is incorporated to diminish the effect of the initial condition, which we found to work well in practice.

2.3 Popularity Distribution

We observe that given a hashtag, the distribution of the popularity indices of individual tweets follows a power-law (figures omitted for brevity), which means that the tweets getting very high re-tweets are very small in number, whereas plenty of tweets are having small number of retweets. The distribution is captured as below:

where k is the popularity of a tweet-chain.

Hence, the expected arrival rate of the process having tweet-chains with random popularity can be formulated as:

2.4 Popularity Ranking in Hashtag Competition

In a tweet-diffusion process, concurrent hashtags often compete with each other for user attention. Such scenarios are usually pronounced through the variations of popularity rankings of the competing hashtags over time. To model it, one may specify λH(t), so that, it detects the variation in their popularity rankings across time. In particular, we say

where, NH[ts, tf ) denotes the number of (re)tweets of hashtagH posted in the interval [ts, tf)

2.5 Parameter Estimation

Given a set of N hashtags H = {Hl|1 ≤ l ≤ N}, we record a collection of posts HHl (T ) = {ti} for each hashtag Hl during a time period [0, T ). Using these posts, we attempt to find the optimal parameters λH,0 and βH = [β1H , β2H , ..., βM H ] for each hashtag H ∈ H by solving a maximum likelihood estimation (MLE) problem. To do so, it is easy to show that the resulting log-likelihood function is

where, λH,0 := [λH1,0, λH2,0, ..., λHN,0] and B ∈ RN×M with Bl,i = βiHl are the variables to be estimated.

To incorporate the effect of competing hashtags, we further restrict λH(t) following Eq (8), by first splitting the interval [0, T), into L sets of small, equal and disjoint subintervals [0, Ts), [Ts, 2Ts), . . . , [(L - 1)Ts, T ), where Ts = T/L, and then imposing the following constraints:

Similar to SVM [Weston, 2014], such a hard-margin approach often may lead to an infeasible solution. Therefore, we introduce slack variables,

with

yiH,H′ = sign(NH[iTs, (i + 1)Ts) - NH′ [iTs, (i + 1)Ts)) and cast the problem as

Note that the above problem is convex and thus can be solved efficiently. We call this framework, Large-Margin self-exciting Point Process (LMPP), since it incorporates the variations in ranking by increasing the popularity-margins of competing hashtags while maximizing the corresponding loglikelihood.

2.6 Popularity Forecasting

Our goal here is to develop efficient methods that leverage our model to forecast a hashtag's popularity at a given time t. In the context of our model, we aim to compute N ∗H (t) = EHH(t)[NH(t)], the expected value of total retweet counts of all tweets for a given hashtagH.

Theorem 1 The expected popularity of a hashtag H at time t is given by,

Proof From Eq. (7), we have

A trite calculation reduces Eq. (12) to,

where ajH = cβjH Γ(α - 1) = βjH Γ(α). Since EdNH(θ)∼{0,1}[dNH(θ)|HH(θ)] = λH(θ)dθ, by taking the Laplace transform of Eq (13) and then applying inverse Laplace transform, we obtain

On integrating the above, we obtain Eq. (11).

3 Experimental Evaluation

In this section, we first describe the datasets used, the evaluation protocol, a short description of baseline paradigms and then provide a detailed comparative performance analysis of our proposal and the baselines.

3.1 Datasets

To implement our proposal, we collected seven datasets associated with a diverse set of real events. The events are chosen in such a way that they provide significant number of messages. So, we focus on popular events from entertainment, sports, e-commerce and disaster. We used Twitter search API to collect all the tweets (corresponding to a 2-3 weeks period around the event date) of the following events/topics, also summarized in Table 1. (i) The Academy Awards 2016 (Oscars), (ii) MTV Awards 2016 (MTV), (iii) Earthquake in Nepal 2015 (Nepal-Earthquake), (iv) Democratic Primaries for US Presidential Election 2016 (Dem-Primary), (v) Big Billion Day sale of e-commerce site Flipkart 2014 (BBD),

(vi) Copa America Football Tournament 2016 (Copa), and (vii) T20 Cricket World Cup 2016 (T20WC). We crawled ∼2 million tweets for each dataset. Thereafter, from each dataset, we carefully select the hashtags in such a way that, (i) there are a significant number of concurrent hashtags with large tweet count, (ii) the hashtags have variations in terms of the number of constituent tweet chains and (iii) the hashtags show notable deviations in the popularity ranking list across time. As an aggregated measure of such deviations, we define rank-diversity of a hashtag as the fraction of times its rank has changed. If out of total I time-windows, a hashtag H ∈ H has changed her rank k times, then rank-diversity(H)=k/I. The mean rank-diversity of a dataset is thereby obtained by averaging the rank-diversity of all hashtags in the corresponding dataset (shown in Table 1).

3.2 Evaluation Protocol

Training and testing: Given a stream of temporal data HH for hashtags H ∈ H, we first split it into training and test set where training comprises of the first 80% of the total number of messages (|H|). We use this 80%messages as input to train our model for estimating the parameters. Here, to construct the constraints (Eq 10), we divide the training-time in several ten-hour intervals and compare the popularity of the competing hashtags in each of them. The estimated model is thereafter used to predict the popularity dynamics of the hashtags in the test set. In order to determine the predictive prowess of LMPP (and the baselines), we follow two different evaluation approaches.

• (i) Forecasting hashtag popularity: In this approach, the predictor aims to forecast the hashtag popularity by computing the expected number of message-posts in the test set.
• (ii) Rank prediction of competing hashtags: As mentioned earlier, hashtag competition usually exhibits variations in the popularity rankings of the corresponding hashtags. Here, we attempt to retrieve the popularity rankings of competing hashtags in the test-set, which in turn indicates how efficiently an algorithm captures the phenomenon of hashtag competition.

3.3 EvaluationMetrics

Mean Absolute Percentage Error (MAPE): It captures the mean deviation between the observed and the predicted popularity for a hahstag up to time t. It is defined by the formula

Here ˆNH(t) and NH(t) are the estimated and actual number of retweets for a hashtag H respectively, at time t. MH denotes the total number messages of hashtag H in the test-set. For a given dataset, we report MAPE as the average of all MAPE(H) over the hashtags H of that dataset.

Spearman's Rank Correlation Coefficient (SRCC): The Spearman's Rank Correlation Coefficient between predicted rank-list ˆRH, and actual rank-list RH of a hashtag set H can be defined as,

Here Cov(.) defines covariance of the two variables, and Var(.) denotes the variance.

Avg. Recall (AvRe) and Avg. Precision (AvPr) (for jump detection): If in two consecutive time-intervals there is a sudden change in the rank of a hashtag by more than half the total no. of competing hashtags, we call it a jump. Let the set of hashtags be H and the rank of a hashtag H ∈ H be rankH,[ti,ti+1) at time-interval [ti, ti+1). Then, if |rankH,[ti,ti+1) - rankH,[ti-1,ti)| ≥ |H|/2, it is considered a jump. Recall measures the fraction of cases an algorithm rightly identifies a jump, while precision measures the fraction of time a real jump has occurred when the algorithm predicts a jump. Incidentally a jump is also referred to as 'Flash in the pan' (as described in [Yang and Leskovec, 2011]).

3.4 Baselines

We compare LMPP with five strong baselines: (i) Reinforced Point Process (RPP) [Hua-Wei et al., 2014], (ii) Simple Hawkes process [Bao et al., 2015], (iii) SEISMIC [Zhao et al., 2015], (iv) SpikeM [Matsubara et al., 2015; Yang and Leskovec, 2011], and (v) HTR (Hashtag Tweet Reinforcement model). The baselines represent a diverse class of existing temporal models. For example, RPP considers intrinsic attractiveness followed by a decay in popularity, Hawkes and SEISMIC represent the self-exciting processes, whereas SpikeM is a temporal pattern based approach. RPP, Hawkes and SEISMIC were primarily proposed for single tweet popularity prediction, which we extended for hashtags by aggregating over the popularity of the corresponding tweets. Finally, HTR only considers hashtag-tweet reinforcement, but not the inter-hashtag competition. Comparing HTR with LMPP helps us to understand the role of hashtag competition in hashtag propagation.

3.5 Performance Comparison (MAPE)

Table 2 presents a comparative sketch in terms of MAPE on the 20% held-out set. We observe that for all datasets, LMPP performs best by achieving lowest MAPE compared to all other baselines. The performance of SpikeM and SEISMIC are consistently poor in most of the cases. This is because, SpikeM emphasizes on modeling realistic patterns from the temporal data (e.g., periodicity). However, the temporal patterns in training-set often do not match with that in the testset. The performance of SEISMIC is better than SpikeM in most of the datasets. In contrast to SpikeM, SEISMIC does not rely on a fixed set of temporal patterns present in the data. Rather, a point-process based formulation helps it to properly capture the stochastic dynamics of the (re)tweet posts.

We find the performance of RPP and Hawkes to be better than SEISMIC and SpikeM. RPP attempts to capture intrinsic attractiveness of a tweet, and the aging of different posts. There are mainly two distinctive features that help Hawkes to obtain a significant performance-boost. First, Hawkes models the temporal effect of each and every post rather than their simple collective effect, which is very well suited to capture the bursty nature of the tweets. Second, the underlying learning problem is convex for this approach. As a result, one can accurately estimate the parameters, making it a robustly identifiable learning model. However, both RPP and Hawkes are designed to model the popularity dynamics of a single tweet. So, they do not consider the reinforcement of a hashtag and tweet chains. Moreover, ignoring inter-hashtag competition further limits their predictive power.

We observe that HTR performs better than RPP and Hawkes in four datasets. Since HTR only captures the hashtag-tweet reinforcement, it can reasonably record the effect of inherent attractiveness of the hashtags on the tweets.

However, it does not incorporate hashtag competitions which in-turn constraints its performance.

The importance of hashtag competition is clearly reflected by the best performance of LMPP which properly blends both hashtag-tweet reinforcement and hashtag competition to accurately model the popularity dynamics. In particular, for four datasets viz. MTV-Awards, Nepal-Earthquake, DemPrimary and T20WC, the performance boost of LMPP is substantial compared to its immediate competitor. This is because, for each of these datasets, the rank diversity (Table 1, last column) is very high. As a result, LMPP exploits this signal to train the model better than others, which results in a significant performance boost.

Analysis of forecasting capabilities with time: To have a better understanding of the prediction performance of all the models w.r.t. time, we further probed the timestamps in the 20% held-out test set and computed MAPE for each sample point. Figure 1 (top row) shows the change of predictiveperformance of popularity with time (MAPE of sample points aggregated over time). We observe that the forecasting performance of LMPP is better than the other methods. As expected, as time progresses, the performance of all the approaches degrades - this rate is relatively much lower in LMPP than all other methods.

3.6 Performance Comparison (SRCC)

To evaluate the ability of the algorithms to detect variations in the popularity ranking of the competing hashtags, we divide the test time into several intervals of same duration. At each of them, we obtain a ranked list of the participating hashtags, based on the predicted popularity using LMPP as well as the baselines. On the other hand, from the original trace, we derive the ground-truth of these ranked lists. To measure how closely a predicted order matches the actual one, we compute Spearman's rank correlation coefficient (SRCC) between them. Table 2 and Figure 1 (bottom row) dissect a comparative analysis in terms of SRCC for all the proposals. We observe that LMPP performs significantly better than the baselines across all datasets. It is interesting to observe that, in this case, HTR outperforms the baselines only for two datasets. That is, here, HTR fares quite poorly as compared to its performance in terms of MAPE. Since HTR neglects the effect of hashtag competition, despite a strong forecasting power, it cannot accurately predict the relative variation of popularity among the competing hashtags. It is important to note that the performance of other baselines are poor and inconsistent across all the datasets. Although the baselines are specifically designed for popularity prediction, they are insensitive to ranking of hashtag popularity. That said, better MAPE does not guarantee that the relative popularity order will be maintained. This is because, MAPE counts absolute error, but does not reflect a relative popularity variation.

3.7 Detection of Sudden Changes in Ranking

Besides evaluating the accuracy of prediction of general rank order, the efficacy of a system can be measured in terms of its success in 'catching' the instances where a particular hashtag suddenly becomes popular (or suddenly loses popularity). We extracted such instances from the datasets (around 9% hashtags in the test-set), and checked how accurately the competing algorithms identify those instances. Table 3 reports the average precision and recall of jump detection for algorithms across all the datasets. In both precision and recall, LMPP significantly outperforms the other algorithms. Considering the hardness of the problem, we believe the performance of LMPP (both precision and recall are around 70%) is excellent by itself. The only exception being the MTV-Awards dataset, where the reason for the less impressive performance is that the absolute numbers of tweet-chains produced by different ranked hashtags are very close. Note that although in terms of SRCC, the gains of LMPP were modest over baselines, LMPP can correctly predict the abrupt changes much better. The problem with other baselines is not only their inferior performance but also their inconsistency, which results in no clear second ranker across datasets.

4 Conclusion

In this paper, we propose LMPP, a novel point process driven framework that unifies several realistic factors to model hashtag popularity such as hashtag-tweet reinforcement and interhashtag competitions. Such a unified approach does not only efficiently estimate hashtag popularity for which it is designed, but also gives an accurately prediction of the relative ranking of concurrent and competing hashtags. Extensive experiments over seven real-world datasets show that LMPP significantly outperforms state-of-the-art baselines in popularity prediction, additionally offering the accurate prediction of ranking and sudden change in popularity of the hashtags.

Acknowledgments

A. De and A. Chakraborty were supported by Google India PhD Fellowship. A. Chakraborty was also supported by Prime Minister's Fellowship Scheme for Doctoral Research.