{'fraction_non_alphanumeric': 0.024499112351001776, 'fraction_numerical': 0.005173725589652549, 'mean_word_length': 4.798823529411765, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Twitter Trend Extraction: A Graph-based Approach for Tweet and Hashtag Ranking, Utilizing No-Hashtag Tweets

Twitter has become a major platform for users to express their opinions on any topic and engage in debates. User debates and interactions usually lead to massive content regarding a specific topic which is called a Trend. Twitter trend extraction aims at finding these relevant groups of content that are generated in a short period. The most straightforward approach for this problem is using Hashtags, however, tweets without hashtags are not considered this way. In order to overcome this issue and extract trends using all tweets, we propose a graph-based approach where graph nodes represent tweets as well as words and hashtags. More specifically, we propose a modified version of RankClus algorithm to extract trends from the constructed tweets graph. The proposed approach is also capable of ranking tweets, words and hashtags in each trend with respect to their importance and relevance to the topic. The proposed algorithm is used to extract trends from several twitter datasets, where it produced consistent and coherent results.


Introduction
Today several platforms are offering users the opportunity to express their opinions on emerging topics related to ongoing events in their lives as well as national and international matters. Among these platforms, Twitter has become a major player, in which users tend to express their opinions on any topics and engage in debates posting millions of tweets every day. User debates and interactions usually lead to massive content regarding a specific topic which is called a Trend. Twitter trends are specifically important due to their influence on public opinion and their ability to affect politicians, governments, organizations, companies and almost any other entities. Twitter trend extraction, as the name suggests, is aimed at detecting ongoing trends among millions of tweets that are posted rapidly. Being able to automatically detect and extract these trends is appealing to anyone interested in analyzing hot topics and ongoing online debates. There are two main approaches for automatic trend extraction: embedding based and graph-based. Embedding based approaches try to find a vector representation of each tweet and detect groups of similar tweets that could indicate trends. On the other hand, in graph-based methods, the goal is to represent tweets as a graph and employ graph clustering algorithms in order to extract similar sub-graphs as trends. Many twitter users tend to use hashtags, which indicate the main topic of their tweets. Hashtags can also be very useful to find similar tweets and follow debates related to specific topics. The issue with this strategy is that not all users tend to use hashtags and this will lead to ignoring all no-hashtag tweets for detecting trends. In this research, tweets are represented as a graph that includes three types of nodes: tweet, word, and hashtag. Tweet nodes are connected to their corresponding words and hashtags with the weight defined as TF-IDF scores.
Word and hashtag nodes have also inter-connections based on their co-occurrence scores. After constructing the graph representation of tweets, a graph clustering algorithm is employed to extract similar tweets based on their neighborhood. This process will lead to finding similar tweets that have some equivalent words and hashtags in common. The proposed method is inspired by the RankClus algorithm which was initially proposed to cluster graph-structured data (Sun et al., 2009). This method is also capable of ranking nodes in each extracted cluster which is especially useful in this research line since it provides the most important tweets, words, and hashtags in each trend. The proposed method is extensively evaluated on two Persian and English sets of tweets, where it produced consistent and coherent trends as they were subjectively assessed. We have demonstrated the extracted trends using top tweets, words, and hashtags in the Results section. Our contributions in this research are as follows: • We used a graph representation employing three types of nodes; namely tweet, word, and hashtag. We also employed TF-IDF and co-occurrence scores to construct the graph edges.
• We employed a graph clustering method inspired by RankClus algorithm which is capable of clustering nodes as well as ranking them in each cluster.
• We also proposed a post-processing step that utilizes cluster scores in order to prune the extracted clusters and keep the consistent ones.
• The proposed method is evaluated on Persian as well as English tweets, in order to demonstrate the language independence property of our approach.
The rest of the paper is organized as follows. Some previous researches and studies on tweet clustering and trend extraction are reviewed in Section 2. Then in section 3, the proposed method is introduced in detail. Section 4, 5 are dedicated to experiments and results of our method. Finally section 6 concludes the paper.

Related Work
Two main approaches have been proposed for tweet clustering and twitter trend extraction. One relies on constructing a graph to represent tweets and then employs graph clustering algorithms for trend extraction. The other approach is based on converting each tweet to an embedding vector and clusters the generated embedding vectors to detect trends. A summarization method was proposed by Duta et. al., which constructs a graph of tweets by generating semantic similarity between tweets utilizing WordNet anthology (Miller, 1995). Community detection algorithms are then employed for tweet clustering and summary generation (Dutta et al., 2015). Co-occurrence score can also be used as weights in the constructed graph. Kim et. al. utilized this approach by constructing a graph using only frequent words as nodes (Kim et al., 2014). Strongly related groups of words are then extracted by applying maximum k-clique algorithms. The generated words represent twitter trends and can be used to generate trend summary. Another method for tweet graph construction is to use cosine similarity for each pair of tweets based on their TF-IDF vector representations. Manaskasemsak et. al. proposed to use this approach for graph construction and then employed markov clustering algorithm for detecting similar tweets (Manaskasemsak et al., 2016). The same methodology was also employed by Kim et. al. where they extracted core topics using graph clustering algorithms (Kim et al., 2012). The introduced papers, so far, only used tweets to construct the graph representation. Another approach is to also include users and their interactions in the final representation. This method was employed by Cataldi et. al. where they proposed to construct a directed graph of twitter users and apply Page Rank (Page et al., 1999) algorithm to calculate the ranking of users (Cataldi et al., 2010). They model the life cycle of words based on users' ranking and utilized this life cycle to temporally analyze the emerging topics and trends. The same ranking policy was also employed on a heterogeneous network of tweets and users, where the interactions between users are utilized for ranking and clustering the tweets (Prangnawarat et al., 2015). A Hashtag Graph-based Topic Model was proposed by Wang et. al., where tweets are projected into a weighted hashtag graph (Wang et al., 2014). In this model, tweets are linked directly to their associated hashtags which also produces an indirect relation to other similar hashtags (that did not appear in tweets). The model then jointly estimates the probability distribution of hashtags over topics and the distribution of topics over words. The final model is then used to detect hot emerging topics from tweets. Wang also suggested a two-stage hierarchical topic modeling for tweet topic extraction (Wang et al., 2017). In this model, Gibbs Sampling algorithm is applied to find the first level clusters. Tweets in each cluster are then merged to form virtual documents, which are then fed to another topic modeling algorithm to find new and meaningful tweet clusters. The same policy is also proposed by Ifrim et. al. which uses dendogram cutting on tweet-by-term matrix to extract clusters (Ifrim et al., 2014). One problem with using hashtags for trend extraction is that users usually tend to use different hashtags regarding the same topic. This phenomenon will lead to several hashtags representing the same trend, which need to be merged in order to produce coherent trends. Muntean et. al. addressed this issue by making virtual documents containing all tweets with the same hashtags (Muntean et al., 2012). K-Means algorithm is then applied to cluster these virtual documents and find semantically similar hashtags. The other issue with hashtags is that several users do not use them in their tweets and this will lead to ignoring all no-hashtag tweets if one is only using hashtags for trend detection. Rosa et. al. proposed a supervised method utilizing hashtags as labels in order to also classify no-hashtag tweets (Rosa et al., 2011). This approach will also designate hashtags to these kinds of tweets addressing the mentioned issue.
Another aspect of trend detection is tweet ranking which is not addressed before. More specifically, one needs to know the most important tweets and hashtags in each trend in order to fully understand and analyze the extracted trends. In this research, we propose a method for trend detection as well as tweet and hashtag ranking. Our proposed approach is also capable of utilizing no-hashtag tweets.

Proposed Approach
In our proposed model, tweets are represented as a heterogeneous graph, in which there are three types of nodes: tweets, words, and hashtags. After representing tweets using a graph structure, a ranking based clustering algorithm is employed for detecting relevant nodes in the graph which are considered as the trends. In this approach, since the graph is constructed using only tweets, there is no need for user data collection. This algorithm finds clusters of tweets that have some words and hashtags in common. We assume that tweets with shared words and hashtags are about a specific trend. Therefore, the algorithm utilizes all tweets: with or without hashtags. Finally, a scoring algorithm evaluates each cluster and finds the most coherent trends.
The proposed model is described in three sections: • Graph Construction: describes the graph nodes and edges.
• Graph Clustering: describes the ranking and clustering algorithm.
• Cluster Scoring: describes the scoring algorithm used for finding the most coherent trends.

Graph Construction
Tweets are represented as a tri-type weighted graph where node types are: tweets, words, and hashtags. As a result, there are six types of edges between nodes: tweet-tweet, tweet-word, tweet-hashtag, word-word, wordhashtag, hashtag-hashtag. In this research, we only consider edges between words and hashtags as well as edges Figure 1: Graph representation of tweets: the graph contains three node types representing tweets, words and hashtags respectively. Graph edges are weighted based on cooccurrence scores.
between tweets and words and tweets and hashtags. A sample graph is illustrated in Figure 1. Weights between tweet nodes and word nodes are calculated using their corresponding Term Frequency-Inverse Document Frequency (TF-IDF) scores. Also, Weights between two words, two hashtags, and a word and a hashtag are calculated by their co-occurrence score which means the number of times they appear in the same tweet. In order to emphasize on hashtags, the weight between a hashtag and its corresponding tweet is set to the maximum value, in this case, 1. This way the algorithm pays more attention to the hashtags in tweets since they carry helpful information about trends. The weighting policy for graph construction is summarized in Equation 1 (where t means tweet, h means hashtag and w means word).

Graph Clustering
In order to cluster nodes in the graph, RankClus, which is a ranking based graph clustering algorithm, is utilized (Sun et al., 2009). RankClus works on heterogeneous graphs and integrates ranking and clustering together. The idea behind this algorithm is that better clustering leads to better ranking and vice versa. The node type that we want to cluster is called the target type and the other ones are attribute types. For each arbitrary cluster, two ranking functions are defined: one is conditional rank which determines how much the attribute type nodes are scored, the other one is within-cluster rank which is calculated by ranking scores of target type nodes in the cluster. The algorithm works as follows: for each cluster, conditional ranks of attribute typed nodes are represented as a rank distribution. Then, K rank distributions can be used to build a mixture model whose goal is to find the best component coefficient score for each target node to be in a certain cluster. Next, each target node will be represented in a K dimensional vector, in which each value shows the component coefficient score of each cluster. Then the distance between all target nodes and clusters will be calculated and each node will be assigned to the nearest cluster. This procedure will be repeated until clusters converge. The readers are referred to the original RankClus paper for an in-depth description of the algorithm (Sun et al., 2009). In this research tweet is the target type, since we are interested in clustering tweets. We also consider words and hashtags as attribute type nodes in the graph. In our model, conditional rank for a given tweet is defined according to Equation 2 (t: given tweet, t : other tweets, w: word in tweet). Within-cluster rank is also calculated using Equation 3 (w: given word, t: tweets which contain tweet, t : other tweets).

Cluster Scoring
After extracting clusters, we need to evaluate them and remove inconsistent trends. In order to evaluate and prune clusters, a scoring algorithm is proposed here. First, all unique words in all tweets are extracted. Then the score for each word in each cluster is calculated. These scores are then normalized and form the score matrix: S. This matrix represents the scores of each word in all clusters as illustrated in Figure 2. Now the intuition behind our proposed algorithm is simple: if a word has a high score in cluster i and low scores in all other clusters, then this particular word is important for cluster i. However, words with high scores in all clusters are not important. This brings up the concept of Entropy. Hence we can calculate the entropy for each word based on its scores on all clusters according to Equation 4. The calculated entropy is then employed as a weight for scoring each cluster based on Equation 5.

Experiments
In order to evaluate the proposed approach, we first need to gather tweets posted in a short period of time. We considered daily tweets as trends usually change each day. We have collected tweets in English as well as Persian to also illustrate the language-independent property of the proposed algorithm.  Tweets are collected using Twitter Firehouse API. For Persian tweets, we provided a list of common keywords to the API to collect any Persian tweets regardless of the topic. This way, tweets can be about somebody's daily life or a certain trend and we expect the model to detect trends and ignore others. For English tweets, on the other hand, we only used crypto-currency related keywords to only collect topic-specific tweets. We aim at testing the model's ability to detect trends in focused datasets in this scenario. The dataset statistics is provided in Table 1. Baselines: We compared our model with a well-known topic modeling algorithm, Latent Dirichlet Allocation (LDA) (Blei et al., 2003). Another approach for comparison is to represent tweets using TF-IDF vectors and employing k-means algorithm for clustering and trend extraction.
The Evaluation Scenario is as follows: 1. Tweets for a certain day are collected.
2. The collected tweets are manually analyzed to extract trends (as ground truth trends).
3. The proposed algorithm is employed to extract trends from tweets.
4. Baseline methods are also employed for trend extraction.
5. Extracted trends are manually investigated to determine how many trends have been successfully extracted by each approach.
Implementation Notes: Some pre-processing steps and hyper-parameters are described here. These specifications are necessary to reproduce the results: • pictures, emojis, mentions, numbers, and URLs are removed.
• Each tweet is normalized and all words are replaced by their stemmed version (using Hazm 1 ).
• Edge Weights are calculated as described in Equation 1.
• The RankClus algorithm is applied by K initial random clusters. The number of Expectation-Maximization iterations and maximum clustering iterations are set to 6 and 11 respectively.

Results and Discussion
Cluster scores on two sample dates on the English and Persian datasets are presented in Table 2. As illustrated in this table, for the first one, the clustering algorithm emitted 2 clusters in its process and our scoring algorithm also assigned 0 scores to two clusters. Hence only two trends are extracted from this date: C 1 and C 3 . The latter has a higher score which indicates a more consistent and coherent trend. Extracted trends and sample tweets from each trend for the first date in Table 2 are illustrated in Table 3. For each trend, top tweets with hashtags, top tweets without hashtags, top hashtags and top words are presented. The proposed algorithm is capable of providing a ranking for all node types in the graph. This feature is very useful for analyzing trends and illustrating trends for users. Also in Table 5, two extracted trends for second date in Persian dataset is demonstrated. Table 4 provides a comparison between our proposed algorithm and baseline models. The comparison is based on the

Conclusion
User debates and interactions on Twitter usually lead to massive content regarding a specific topic which is called a Trend. Twitter trend extraction aims at finding trends in a short time period. In this paper, we introduced a novel approach for twitter trend extraction which utilizes tweets without hashtags and also produces a ranking for tweets in each trend. The proposed model utilizes graph clustering techniques for trend extraction. Moreover, tweets are represented as a graph, in which nodes represent tweets, words, and hashtags. Edges between nodes are constructed using a weighting policy utilizing co-occurrence scores. RankClus algorithm is then employed for ranking and clustering tweet nodes. We also proposed a scoring algorithm to find the most relevant and coherent trends. The proposed approach is capable of utilizing no-hashtag tweets as well as tweets with hashtags. Also, this model can capture multiple hashtags that correspond to the same trend. In order to evaluate the proposed approach, several tweet sets have been collected. These tweets were first manually analyzed to find the trends in each set. Then the proposed algorithm alongside two baseline methods were employed for automatic trend extraction. The extracted trends were then manually compared with true trends. The results suggest a superior performance in our proposed model. In order to improve the model, one can try different ranking functions. Also, the evaluation can be extended to analyze all tweets systematically and produce more reliable results. Emerging topic detection on twitter based on temporal and social terms evaluation. In Proceedings of the