We introduce a novel method for predicting trending keywords on Twitter. This new method exploits topology of the studied parts of the social network. It is based on a combination of graphlet spectra and so-called time features. We show experimentally that using graphlets and time features is bene cial for the accuracy of prediction.
In this paper, we present a method which exploits information about graph structure of sub-networks of the social network Twitter for making better predictions about which topics will get among the top k. We show experimentally that with information about the graph structure we are able to obtain better predictive accuracies than with a model trained on the same data which does not use information about the graph structure. Importantly, the presented method does not need access to the entire graph structure as it works only with certain sets of derived attributes, which makes it potentially possible to combine the method with sampling strategies and also to make it able to work in differentially private settings.
As the network structure has been proved to play an important role in
spreading social trends [
Now, we de ne the prediction problem that we will be dealing with in this paper, namely the problem of predicting the top-k trends. Unlike original Twitter engine, we consider trending topics clearly by measuring the frequency of occurrence of corresponding hashtag in the network. If the relative frequency of hashtag in a particular timeframe is among the top-k, we declare it a trend. One can imagine a web page which gives its users a list of k hashtags which are predicted to get among the hottest topics in his subnetwork in the near future.
Learning is performed on data as a time series, where each hashtag occurrence
information goes into a prepared time-fold according to its time of creation. The
task is to predict which hashtags will be trending in the future target time-folds
(determined to day intervals). Unlike in the case of the basic supervised learning
task, there is an additional constraint on the output of the classi er. On every
single day, the classi er must mark as trending exactly k hashtags. To satisfy
this constraint, the classi er takes the probability distribution of classi cation
given by the learned Random Forest [
In order to assess the contribution of graphlets and time features to accuracy of prediction, we created two models which we call simple model and baseline model and which serve as a baseline in this paper. In these approaches we wittingly ignore the social graph structure and take the problem as a time series prediction, which is the case of most methods found in literature. The simple model method represents the common sense approach to the statistics measured. It builds on basic average occurrence of the hashtags, calculated over all timefolds in the training part of the time-window, and treats them as if they were to o # # o o o
o
#
#
#
o
o
continue constantly with that occurrence in the target part. The baseline learner
represents a classical time-series prediction method, with the use of a model to
predict future values based on previously observed values in data with natural
temporal ordering. To make a clear comparison of the models used, we turn the
time series forecasting task into a standard classi cation problem, using a sliding
window technique [
The term graphlet, as used in this paper, refers to a small directed graph (with up to 3 nodes) which contains at least one node labelled by \#". Examples of graphlets are shown in Figure 1. For every day D and every hashtag H, the snapshot of the sub-network is a directed labelled graph constructed as follows. There is one node for every user. There is a directed edge between two users Ui and Uj if and only if the user Ui follows the user Uj . A node is labelled by \#" if and only if the user corresponding to this node used the hashtag H on the day D in at least one tweet. Given a list of graphlets Lg and a snapshot S of the sub-network we can construct a so-called frequency-feature vector as follows. For every graphlet gi 2 Lg, we count the number of homomorphisms of gi to the snapshot graph S (respecting the labels \#") and store the number in the i-th element of the frequency-feature vector. Clearly, frequency-feature vectors are not very suitable for prediction of top-k trends because their values are sensitive to the overall activity of the users on the given day. Therefore we need socalled rank-feature vectors which can be constructed from the frequency-feature vectors. Given a set of frequency-feature vectors for all hashtags of interest on a given day, the i-th element of a rank-feature vector Vrank for a hashtag H is the rank (i.e. order) of the respective i-th element of the frequency-feature vector Vfreq corresponding to the same H among all i-th elements of the other frequency-feature vectors corresponding to the same hashtag H. Given a time window consisting of several days, one can easily create a graphlet representation by concatenating the rank-feature vectors corresponding to these days.
The rationale behind the graphlet model is that graphlets can capture how
natural user to user connections in Twitters network affect the topics discussed.
They consist of nodes and edges representing occurrence of hashtag on users
time-line in context of his neighbors, e.g. his followers and friends. A somewhat
similar representation was used in the work of Natasa Przulj for computing
a network structure similarity measure using so called graphlet degree
distribution [
Time(A) #
Time(A) < Time(B) causality relation Time(B) # Time(A) #
Time(A) > Time(B) causality relation
Time(B) #
Besides graphlets we use also so-called time features. The main purpose of time features is to add a measure of some time properties of the underlying networks relations. The motivation for this comes from a natural intuition of trends spread in social networks. In a directed network like Twitter, if the information is being spread through the network, the fashion of the spreading should correspond to the network structure. By that we mean that the directed relations between the users should actually represent the causality links in the trend spread dynamics. If it is not the case, the information is probably not coming from the network and is being spread by other channels. Now how to measure this networks causality correspondence? For a snapshot corresponding to a hashtag H, we label all the directed edges e = (Ui; Uj ) which connect two nodes Ui and Uj both of which are labelled by \#", by the time between the instant when Ui posted the tweet with the hashtag H and the instant when Uj posted a tweet with the same hashtag. Since the difference is measured against the direction of the underlying relation, it can in general be negative as depicted in Figure 2. The time features can then be computed as averages and standard deviations of these time differences by which the edges are labelled.
core learners performance comparison 0.84 0.82 0.8 0.78 -][ k%0.76 p o t 0.74 0.72 0.7 0.68 simple baseline graph For the testing of our graph-based approach we needed to download a suitable dataset of tweets from Twitter. We implemented a simple crawler using the Twitter API. The sampling strategy, i.e. the choice of the set of users that should be downloaded was driven by a simple heuristic. Starting from a random seed, the heuristic orders the nodes (corresponding to users) whose neighbours should be added to the database in a greedy way so that the crawled subnetwork would be as compact as possible { it picks preferentially those nodes which share most edges with nodes already stored in the database. The network subsets that were eventually crawled consist of approx. 8 thousand users with 3 million internal connections, and millions of public tweet (hashtag containing) records from December 2012, March and April 2013.
We measured the performance of our novel method and the simple and baseline methods on the largest dataset from March 2013, with windows consisting of 4 days of training and 1 day for prediction. We set k to 20 and performed multiple runs of the classi er with varying seed. We tested our features with two classi ers, namely SVM and Random Forest, both giving similar results, yet the later proved more suitable for tuning and time complexity reasons. The choice of parameters was tuned as to avoid over tting of the classi er, i.e. by extending the training timescope to at least 4 days, and to have a clear threshold to cut between trending and non-trending hashtags, i.e. higher k such as 20 helped to avoid the situation of constant classi cation con dence for all the trending hashtags.
The improvement on the top-k% metric achieved by our method, as displayed in Figure 3, might in reality correspond to early detection of a couple more upcoming trends that wouldn't be otherwise discovered without taking the structure of the network into account.
We also performed other experiments with the novel method which we do
not report in detail here due to lack of space but which can be found in [
In this paper, we presented an approach for prediction of trends spread within a local Twitter subnetwork, utilizing topology structure information, based on representation, inspired by methods from the area of biological networks. The results prove the value of knowledge on the network structure and the contribution of the approach itself. One of the appealing properties of the method is that it exploits information about structure of the network but at the same time it does not need the entire structure nor it does need to construct models of individual users.
Acknowledgements This work was supported by the Czech Science Foundation grant no. P202/12/2032 and the Czech Technical University internal grant SGS11/155/OHK3/3T/13.