Real-time detection and trend tracing of burst topics based on Negative Binomial Distribution on spark

Abstract

Social networks have evolved into a popular information and communication platform, and the vast amount of data it generates are rapidly changing and spreading. Thus, it is essential to detect and trace large events and burst topics in mass social network data based on real-time Big Data parallel computing. In this paper, we propose a model that uses the Negative Binomial Distribution to fit the distribution of Weibo topic words. Then, we introduce the concepts of the ‘hot degree’ and the ‘dispersion degree’ of a topic with their corresponding computing methods. And we validate the efficiency of the model using real data. Furthermore, we design a topic detection and trend-tracing algorithm based on stream data, and implement the algorithm on Spark Streaming which is a streaming processing framework that uses memory computing. Finally, the experiments on real data demonstrate that our proposal is effective and efficient in tracking bursting events.

Keywords

Negative Binomial Distribution stream data topic modelling burst events tracking spark

1. Introduction

Social networking is an emerging information exchange and propagation platform that is attracting more and more users; it has a non-negligible impact on the management and development pattern of society as a whole [1].

At every moment, social networking generates new data that may be directly related to public safety, such as early warnings of hurricanes [2], earthquakes [3] and influenza alerts, some of which is concerned with the development of a nation’s and people’s livelihoods, such as messages regarding oil price increases [4]. Therefore, social networks, such as Twitter and Weibo, are the starting points of various important news and intense events. Unlike traditional news media, interactions among users on social networks significantly increase the speed and depth of the information transmission [5]. However, the arbitrariness of the used language in Weibo often makes valuable information submerged in a flood of data. Therefore, designing effective methods to detect topics in a timely manner in the presence of massive amounts of data is of great significance for useful information extraction and social emergency warnings [6].

Furthermore, the high arrival rates and high exchange rates of social network streams lead to the high data velocity [7, 8], thus, ‘timeliness’ has become a very important factor for burst topics [9, 10, 11, 12]. The data value decreases over time, and the detection of emerging events and topics in real-time has become one of the key issues in on-line social network analysis [13]. In recent years, in order to solve the problems of big-data real-time processing and computing more effectively, the industry has implemented a variety of techniques, such as the Apache Hadoop parallel processing framework, the Apache Storm streaming computing framework, and the Spark memory computing framework. The rational use of these related technologies will further enhance the efficiency and capacity of topic analysis in social networks.

We use Sina Weibo, the most typical social platform in China, as the data source for the typicality and representativeness of its data. Then we propose to use a Negative Binomial Distribution model to fit the distribution of the Weibo topic words. The fitting results are then evaluated. According to this model, we present a method to simulate the ‘hot degree’ and ‘dispersion degree’ of the Weibo topics. Note that the ‘hot degree’ indicates the intensity or frequency of the term used in real time, which indicates the trend of its use. Furthermore, considering the data characteristics in Weibo, we abstract the Weibo data into stream data, and design an algorithm based on time windows to track topics through real-time computing. Compared with traditional trend prediction methods that are simply based on word frequencies, our method reduces randomness and improves accuracy. Through the above three steps, real-time discovery and tracking of bursting topics is achieved by statistical methods.

In addition, considering the problem of timeliness, we apply the popular Spark Streaming, a real-time stream computing framework, to design and implement the real-time topic detection and tracking algorithm. It can help solve the big data computing and analyze these data in real time. This research can be used to applications that aim to increase public awareness of emergencies in real time and timely decision-making over relevant agencies.

This paper includes six sections. Section 1 is the introduction, followed by a detailed review of related word in Section 2. In Section 3, the Negative Binomial Distribution model is introduced and verified to be rational and correct when fitting the trend of the Weibo word frequency. Then the computing method of corresponding parameters combined with Weibo data is proposed, and methods to track the topic trends by tracing the model are described. In Section 4, the proposed topic detection and tracing algorithm is introduced based on stream data, and the overall architecture and real-time implementation in the framework of Spark Streaming are described. In the following section, several experiments are conducted. First, we compare the fitting results between the Negative Binomial Distribution model and the usual Poisson Distribution model. Then, we run the proposed algorithm to track the topic trends and present a discussion. By comparing with real situations, the topic detection and tracing approaches proposed in this paper are proved to be feasible and rational. Finally, our conclusions are presented in Section 6.

2. Related work

Weibo is a social platform that covers massive dynamic information, and an increasing amount of research has been dedicated to data mining, topic propagation prediction, topic detection and related research. In relation to this topic, several applications have been reported.

Traditional topic detection is mostly based on clustering, classification, topic modeling and other methods [1], and most of these approaches are applied in an off-line fashion [11] used an infinite-state automaton to model stream data through obtaining the state transition to signal the changes in the bursts [14] analyzed the characteristics of information dissemination on social networks and proposed an information trend prediction algorithm based on information classification and regression algorithms. Some of the algorithms, such as the Latent Dirichlet Allocation (LDA), improve the accuracy of the topic detection by applying an LDA topic model to extract the hidden topic information [15, 16]. However, much of traditional research is based on static historical data without considering the evolution of topic trends and the timeliness and instantaneity of the topic detection.

In recent years, more scholars have realized that the value of social network topics decreases as time progresses, especially for events such as natural disasters and health alerts and some related topics, which are important for early warning systems and public security. Some studies on social networks have been conducted on topics such as tornados [2] and earthquakes [3]. Timeliness is considered in increasing numbers of topic detection methods, through which stream data are dynamically processed [17] proposed a real-time analysis framework of Twitter data to detect burst topics in a timely manner and to analyze the corresponding topic trends. However, historical data are still required to determine the optimum parameters for each keyword [18] concerns the identification of the first occurrence of emergencies in such a way that alerts could be issued as early as possible [1] improved the on-line LDA model with a dynamic update model mechanism based on time slicing. To detect new ‘burst’ topics, the evolution of topics will be recalculated each time the data are updated [19] proposed a topic detection algorithm based on a windowing variation technique. Although a burst-word list was obtained with a keyword ranker module, the dynamic trends of the topics were not considered. Overall, algorithms that considered timeliness ignored the dynamic tracing of the topic trends, and these relevant studies were conducted on data mining based on specific small data sets. These studies did not consider the real-time distributed parallel processing of big data. However, the large capacity of social networking data makes the processing efficiency and computing ability two key issues to be considered.

There is much work that takes into account the above issues [20] proposed a sketch-based topic model and achieved real-time detection. But it could not handle streams of data with multiple topic [21] used hierarchical clustering of tweets and rank the clusters to obtained the topics within a long period (e.g., 24 hours), while did not take the timeliness and burst into consideration [22] detected potential topics in real-time by first clustering the tweets and then analyzing whether the clusters meet some characteristics. However, its parameters were not set in a flexible manner to accommodate various type of data, such as Weibo.

In respones to the limitations of the previous researches, we proposed a method to meet all the needs. Our study is not limited to focusing only on the real-time detection of burst topics and dynamic trend tracing based on the Negative Binomial Distribution. We design suitable algorithms for Weibo’s stream data while considering its features and real-time requirements. Moreover, the presented algorithm is applied to the Spark Streaming framework, and a specific parallel plan is advocated to address the problem of real-time analysis and processing on Big Data.

3. Topic trend model

In Section 3.1, the Negative Binomial Distribution model, the chosen model used in our study, is introduced, and the theoretical basis of choosing this model is presented. To provide a theoretical foundation for the subsequent study, the meanings and computing methods of two parameters, m and r, are described. In Section 3.2, the hypothesis that the frequencies of the occurrences of the Weibo words match the Negative Binomial Distribution is examined. The topics consist of several certain keywords, and, thus, it is believed that the selected keywords identify the topics. To explore this assumption, the topic – Nepal earthquake – is taken as an example, and its Weibo data are analyzed. This approach lays the foundation for subsequent research on trend tracing. Finally, the topic trend-tracing method using the Negative Binomial Distribution model is demonstrated in Section 3.3.

3.1 Negative Binomial Distribution model

In some of the literature, the Poisson Regression Model is often adopted to fit the distribution regularity of discrete random events [23]. The Poisson Regression Model demands that the outcome variable is subject to Poisson distribution, and the occurrence of random events is independent. In Poisson distribution, the random variable’s mean value is equal to its variance. However, for many practical applications, such as the distribution of infectious diseases in an area, the biological aggregation distribution, and so on, the count data are more disperse and do not meet Poisson distribution. In addition, there are often correlation factors between the occurrences of events. Therefore, in some cases, the Poisson Distribution Model is difficult to adapt to the actual situation.

The Negative Binomial Distribution is a compound distribution for which the parameter $\lambda$ of the Poisson Distribution is subject to the $\Gamma$ distribution. It is used to fit dispersed data for which variance is greater than the average and is also applicable to situations in which there are correlation factors between the occurrences of events, such as the distribution of snails in soil, the spatial distribution of insects and the simulation of population sizes in birth, or death processes [2, 24].

Weibo burst topics consist of some specific keywords. When a topic appears, the corresponding keywords show a certain state of aggregation over a period of time, and these keywords have their own life cycle. Considering the discreteness and non-independence of microblogging data, we use the Negative Binomial Distribution to simulate the varying pattern of Weibo word frequencies with respect to their life cycles. The related definitions of the Negative Binomial Distribution are as follows:

Definition 1: Negative Binomial Distribution. Suppose that $p$ is the success probability of each trial in Bernoulli trials. When the r-th success occurs, the occurrence number of failures $X$ is subject to the Negative Binomial Distribution with the parameters $r$ and $p$ [25]. Its probability function is referred to as

$\displaystyle P\left({X=k}\right)=\left(\begin{array}[]{c}{r+k-1}\\ k\\ \end{array}\right)(1-p)^{k}p^{r}\left(k=0,1,2,\ldots\right)$ (1)

The expectation and variance of the Negative Binomial Distribution are shown as Eqs (2) and (3):

$\displaystyle\text{E}\left(X\right)=\frac{r\left({1-p}\right)}{p}$ (2) $\displaystyle\textit{Var}\left(X\right)=\frac{r\left({1-p}\right)}{p^{2}}$ (3)

According to Eq. (2), we set the expectation equal to m, and, then, we obtain Eqs (4)–(6), which are the variance and probability mass function of the Negative Binomial Distribution.

$\displaystyle\text{E}\left(X\right)=\frac{r\left({1-p}\right)}{p}=m$ (4) $\displaystyle\textit{Var}\left(X\right)=\frac{r\left({1-p}\right)}{p^{2}}=% \frac{m}{p}=\left({1+\frac{m}{r}}\right)m$ (5) $\displaystyle\text{P}\left(X=k|m,r\right)=\left(1+\frac{m}{r}\right)^{-r}\frac% {\Gamma\left(r+k\right)}{k!\Gamma\left(v\right)}\left(\frac{m}{m+r}\right)^{k}$ (6)

From the probability mass function, we can see that there are two parameters, $m$ and $r$ , which, respectively, represent the mean value and the dispersion degree of the distribution. The smaller the $r$ value, the smaller the variance and the dispersion of the distribution. In contrast, the greater the r value, the greater the variance and the dispersion of the distribution.

Suppose that $X_{1},X_{2},\ldots,X_{n}$ is a sample from the population that represents the obtained word frequency during a continuous period of time in Weibo. Equations (7) and (8) are the calculation methods for $m$ and $r$ . Several calculation methods, such as zero frequency estimation, maximum likelihood estimation, and moment estimation, can be used to estimate the $r$ value. Here, we adopt the moment estimation method to calculate the $r$ value.

$\displaystyle\hat{m}=\bar{X}=\frac{\sum^{n}_{i=1}X_{i}}{n}$ (7) $\displaystyle\hat{r}=\frac{\bar{X}^{2}}{\hat{\sigma}^{2}-\bar{X}}$ (8) $\displaystyle\widehat{\sigma^{2}}=\frac{\sum_{i=1}^{n}(X_{i}-\bar{X})^{2}}{n-1}$ (9)

In the formulas above, $\bar{X}$ is the sample average value, and $\widehat{\sigma^{2}}$ is the sample variance. In the next section, we use Negative Binomial Distribution to model the Weibo topics, and we estimate the model parameters based on the actual count data to further trace the topic trends.

3.2 Building the model for word frequencies

Suppose that in the time series, for any time interval $\Delta t$ , a word’s frequency in Weibo, which is $N_{t_{k}}$ , obeys the Negative Binomial Distribution, where $\{t_{k}=t_{0}+k\ast\Delta t|k=0,1,2,\ldots\}$ .

To verify the assumption above, we obtain the actual Weibo data, which is the latest 50 minutes of public Weibo data from Sina Weibo API after the Nepal earthquake occurred, to analyze the goodness of fit of the Negative Binomial Distribution. The data crawling program accesses the API interface once every 30 seconds, and, each time, it obtains the latest 200 microblog data. After the word-segmentation and word-frequency counting steps, we obtain 100 frequency data points for each word we choose to test, and, here, we choose the words ‘Nepal’ and ‘Earthquake’ to test the goodness of fit.

Figure 1.

The arrival rate of “Nepal”.

The word frequency variations of these two words over time within 50 minutes are shown in Figs 1 and 2. Then, we use the 10-minute data (20 data points), 20-minute data (40 data points), 30-minute data (60 data points), 40-minute data (80 data points) and 50-minute data (100 data points) of these two words to validate the assumption that the word-occurrence frequencies in Weibo match the Negative Binomial Distribution (NB distribution). In this experiment, the Pearson Chi-Square test is adopted, and the fitting results are shown in Tables 1 and 2.

Table 1

Fitting results of the NB distribution model for the word ‘Nepal’

Time sequence	Periods of time	Number of sample points	Goodness-of-fit test for nbinomial distribution
			X^ 2	df	$p$ -value
T ${}_{1}$	10 min	20	2.985633	2	0.2247387
T ${}_{2}$	20 min	40	5.299191	3	0.1511549
T ${}_{3}$	30 min	60	5.984393	5	0.3077405
T ${}_{4}$	40 min	80	8.755862	5	0.1192073
T ${}_{5}$	50 min	100	4.833318	5	0.4365592

Table 2

Fitting results of the NB distribution model for the word ‘Earthquake’

Time sequence	Periods of time	Number of sample points	Goodness-of-fit test for nbinomial distribution
			X^ 2	df	$p$ -value
T ${}_{1}$	10 min	20	2.985633	2	0.9808047
T ${}_{2}$	20 min	40	5.299191	3	0.728657
T ${}_{3}$	30 min	60	5.984393	5	0.2681777
T ${}_{4}$	40 min	80	8.755862	5	0.4229769
T ${}_{5}$	50 min	100	4.833318	5	0.05220264

Figure 2.

The arrival rate of the word ‘Earthquake’.

The null hypothesis of the Pearson Chi-Square test is that the test data are consistent with the theoretical distribution. From the fitting results, we can find that the p-values are all greater than the significance level (0.05). Thus, the assumption that the word occurrence frequency in Weibo matches the Negative Binomial Distribution model, regardless of whether there is a short time or long time, is validated. Therefore, the Negative Binomial Distribution model can be employed to simulate the word frequencies in Weibo at different times. Furthermore, in Section 5.1, we compare the fitting degree between the Negative Binomial Distribution model and the frequently used Poisson Distribution model, which further validates the rationality of using the Negative Binomial Distribution to fit the Weibo data.

Thus far, the model’s performance has been tested. In the next section, the word trend tracing method is introduced based on this model.

3.3 The method of word trend tracing

As mentioned above, if a discrete random variable is consistent with the Negative Binomial Distribution, then the two arguments can be calculated as Eqs (7) and (8).

From a mathematical perspective, $m$ represents the mean value of the distribution and $r$ represents the degree of aggregation.

Burst events often occur with an abnormal frequency growth of related Weibo words over a period of time. Changes in word frequency lead to variations in the model’s arguments. Thus, tracking the variations in $c$ and $r$ over time assists in tracking the trend changes of a topic.

Using the model to fit the distribution of a certain Weibo word and capturing its word frequency in a time sequence, these two arguments can be calculated. In the model, $m$ represents the hot degree. The greater the value of $m$ , the higher the hot degree. Conversely, $r$ represents the dispersion degree of the topics, and the smaller the value of $r$ , the smaller the dispersion and the greater the aggregation, which indicates that a topic is concentrated in an interval of time, and it has a growing transmission trend.

4. Algorithm design of real-time topic tracing and implementation based on Spark Streaming

This part consists of four sections. First, the overall computing process framework of topic discovery and trend tracing based on the Weibo stream data is introduced in Section 4.1. Next, the methods of obtaining the data streams and data preprocessing are presented in Section 4.2. In the subsequent section, the topic discovery and tracing algorithm based on sliding windows are demonstrated. Finally, the design of the implementation process of the real-time tracing algorithm using the current popular real-time processing framework Spark Streaming is shown.

4.1 The architecture of the calculation process

Weibo produces large amounts of data every moment, and the value of the data decreases over time. The timeliness of topic discovery has become a key issue to be considered. Thus, we abstract Weibo data into stream data according to its characteristics, and the computing framework based on stream data is brought up in such a way that the data can be processed as long as the data continue to arrive, which is exactly the real-time data analysis.

Figure 3 shows the overall computing process framework of the topic discovery and tracing based on the stream data. The following algorithm describes above procedure in detail. Lines 1–5 show the data preprocessing algorithm.

Step 1:
Obtain data through the Weibo API and set the program to access the API once every 30 seconds. The data stream can be acquired once every 30 seconds, and, every time, the raw data sets are sent to the message-oriented middleware.
Step 2:
Preprocess the raw data, including word segmentation, stop word filtering and word-frequency counting.
Step 3:
Use the algorithm proposed in Section 4.3 to compute the hot degree and the dispersion degree of each word based on the Negative Binomial Distribution model to further describe the word’s trends.
Step 4:
Repeat Steps 1–3 to obtain the hot degree and the dispersion degree in an interval of time. By analyzing the variances of the above two factors, every word’s growth trend and popular level can be estimated to generate a final data set of hot words. Thus, the trends in the hot words can be tracked continuously, and their life cycles can be indicated.

Figure 3.
Calculation process of topic detection and trend tracing.

4.2 Stream data pre-processing

Sina Weibo, the largest microblogging service platform in China, provides developers with an open API service, including hundreds of API interfaces and mainstream SDK. Through the corresponding API interface, the latest Weibo data can be obtained. The data accessing and preprocessing steps are as follows:

Step 1:
Through the official API, the latest microblog data are acquired in JSON format. To facilitate the computation and analysis of the model arguments in real time, we accomplish the secondary development on the basis of the official API, in which the latest 200 microblog data can be obtained for every $\Delta t=$ 30 s. Therefore, suppose that $t_{0}$ is the start time and the data sets can be obtained for the following time points: $\{t_{k}=t_{0}+k\ast\Delta t|k=0,1,2,\ldots\}$ . Therefore, the created time and text content of the latest microblog are collected in real time.
Step 2:
For preprocessing the raw data, the open-source word segmentation tool, IK Analyzer,1
¹
https://github.com/wks/ik-analyzer.

is utilized to parse the Weibo text. In this step, a stop-word dictionary is applied to filter the meaningless words, for example, the pronouns, prepositions, adverbs, conjunctions, particles, interjections, and onomatopoeia. Thus, the text noise is greatly reduced, and only meaningful words can be retained for subsequent analysis, which will further improve the efficiency and accuracy of the data analysis.
Step 3:
After the word segmentation, the microblog text is divided into a number of meaningful words. In this step, the word frequencies are counted to continue following the processes of topic discovery and trend tracing. Each piece of data from Step 2 becomes an ordered triple (word, $t_{k}$ , $\textit{frq}(t_{k}))$ , where $\textit{frq}(t_{k})$ represents the word frequency of a certain word at the time point $t_{k}$ . Due to the instantaneity of the obtained Weibo data, the statistics of the word frequencies are instantaneous.

4.3 Algorithm design for real-time burst topic detection and trend tracing

The method used for topic detection and trend computing, based on the Negative Binomial Distribution, has been introduced in Section 3.3. To achieve real-time topic analysis, we focus on the latest data and discard the old data [19, 17]. Considering the randomness of the word frequencies over some intervals of time, we propose a trend computing algorithm based on a sliding time window.

The main idea of the algorithm is to design a time window and wait for the word frequency to fill this window. When the window is full, the trend for this word is computed, and the sliding window moves forward one unit to wait for the next data. Therefore, the multiple sets of $m$ and $r$ values are calculated in real time. At the same time, adopting multiple data to calculate the parameters will reduce the influence of the data randomness on the results.

As Fig. 4 demonstrates, suppose that the size of the time window is $L$ (here, the window is enclosed with a dashed box, and the value of $L$ is 10). When the window is fully filled with the word-frequency data at the time point of L, the frequency set $\{\textit{frq}(t_{1}),\textit{frq}(t_{2}),\ldots,\textit{frq}(t_{L})\}$ is obtained, and Eqs (7) and (8) are used to compute $(m_{1},r_{1})$ . After the first calculation, the time window moves forward one unit to wait for the next set of frequency data. When new frequency data arrive, the calculation continues and obtains the corresponding $(m_{2},r_{2})$ using $\{\textit{frq}(t_{2}),\textit{frq}(t_{3}),\ldots,\textit{frq}(t_{L+1})\}$ . In this loop, new stream data flow into the window continuously, and the values of $\hat{m}$ and $\hat{r}$ are calculated continuously, which ensures the timeliness of the results.

Figure 4.

The trend computing algorithm based on sliding time window.

As shown in Section 3.3, by computing the hot degree $\hat{m}$ and the dispersion degree $\hat{r}$ of each word and analyzing their variances over a period of time, the hot degree of a word and its growth trend can be determined. Thus, these two arguments can be combined to produce an analysis. When $\hat{m}$ increase and $\hat{r}$ decrease, the topic word is becoming more popular, and the topic is showing a spreading trend, which determines that this word can be added into the burst-word set. In contrast, when $\hat{m}$ decrease and $\hat{r}$ increase, the topic word is becoming less popular. The thresholds $\sigma$ and $\omega$ can be set according to the actual situation; when $\hat{m}<\sigma$ and $\hat{r}>\omega$ over a continuous period of time, the topic word will no longer be regarded as a hot word, and its trend will not be tracked as well.

The following algorithm describes the topic discovery and tracking process based on the time window. Lines 1–5 show the data preprocessing algorithm. First, the Weibo data, such as the Weibo contents and corresponding time stamps, are extracted. Second, the Weibo contents are segmented into words through the Map function. At the same time, the stop-word dictionary is employed to filter the meaningless words, such as demonstrative pronouns, conjunctions, auxiliary and punctuation, to reduce the computing cost in the subsequent analysis. Finally, the Reduce function is used to count the word frequencies in the Weibo content and to generate the tuple ([word, timestamp], freq).

Lines 6–12 demonstrate the process of topic discovery and trend tracing. First, it is determined whether the time window is filled. If not, a new arrival word frequency is added to fill the window; then, the values of $\hat{m}$ and $\hat{r}$ are computed using Eqs (7) and (8) in Section 3.3. Finally, the argument values are recorded, and the time window moves forward for a distance of sliding interval to conduct the next computation. As the time window moves, the topic arguments are obtained continuously. When the number of times that the values of $\hat{m}$ and $\hat{r}$ deviate from the threshold is greater than $n$ , this particular topic word will be removed from the burst-word topic list.

Data preprocessing:

1 ObtainData (InputStream s) {

2 ParseWeibo(s)

\to

Tuple(content,timestamp)

3 SplitTuple(content,timestamp)

\to

Tuple(word[ ], timestamp)

4 Tuple(word[ ],timestamp)

\to

Tuple([word,timestamp], freq)

5 }

Topic detection and trend tracing:

6 For every word in Tuple([word,timestamp],freq) {

7 ReduceByKeyAndWindow (WindowLength, SlidingInterval) {

8 While the word’s timewindow is not full then do

9 AddToFreqList(freq)

\to

timewindow[ ]

10 ComputeHotDegree(timewindow[ ])

\to

\hat{\bm{m}}

11 ComputeAggreDegree(timewindow[ ])

\to

\hat{\bm{r}}

12 Record the values for

\hat{m}

and

\hat{r}

13 If ((

\hat{m}>\sigma

\hat{r}<\omega

) or Count(

\hat{m}<\sigma

\hat{r}>\omega

)

<=n

)

14 then do {AddToTopicList (word) }

15 Else do {RemoveFromTopicList (word); goto 17}

16 The window slides forward for the distance of SlidingInterval.

17 End while

18 }

19 End For

20 }

4.4 Implementation of the algorithm based on Spark Streaming

Spark Streaming, a scalable, high-throughput and fault-tolerant real-time stream data-processing framework based on Spark Core, was created to address the demands of the real-time responses and the increasing amount of data. Spark Streaming divides the stream computing into a series of short batch jobs, and each piece of data is converted to a Spark RDD (Resilient Distributed Dataset). Spark can convert these RDDs into intermediate results and store them in files or output them to an external device according to the business’s needs. At the same time, the Spark framework provides a distributed, scalable computing platform that can better resolve the performance bottleneck of the massive amount of data being processed.

Because the proposed algorithm is based on real-time stream data and the Weibo platform processes a large volume of data, the Spark Streaming computing framework is adopted to achieve the dynamic discovery and real-time tracing of topics. According to this framework, the batch-processing time interval, window length and sliding time interval are set to determine the processing time intervals of the Weibo data. These indicators can be adjusted depending on the actual situation.

The implementation logic of the topic discovery and tracing algorithm of the burst topics in Spark Streaming is designed based on the basic principle of Spark Streaming. The computing process has been introduced in Section 4.1, and the implementation architecture based on Spark Streaming is shown in Fig. 5.

Kafka, a distributed message queue that performs better in terms of the throughput, reliability, and scalability, is employed here as data transfer middleware. It receives stream data from the Weibo platform via Weibo API while accepting a Spark Streaming request and sends the corresponding data to the Spark Streaming cluster.

DStream (Discrete Stream) is an abstract of the stream data in Spark Streaming. It can be obtained either from an external input source or by conversion of the input stream. Each DStream contains the stream data in a specific time interval. With good expansion capability provided by Spark, this series of implementation logic can be extended according to the amount of data size in the Spark cluster, which will ensure the data processing capacity. As shown in Fig. 5, the entire implementation logic processes and converts Weibo data many times. The functions of each node are listed in Table 3.

Table 3
Logical implementation of the algorithm based on Spark Streaming

Component	Function
Kafka	Obtain Weibo data from external data sources and sequentially transmit the data to the Spark Streaming cluster.
DStream I	Preprocess Weibo data, including word segmentation, stop words filtering and other steps. Send different words to different processing nodes using Hash function.
DStream II	Receive data from DStream I and statistic the word frequency using HashMap to get (word, $t_{k}$ , $\text{frq}(t_{k}))$ triples.
DStream III	Set sliding time window to process the word trend computing and tracking logic, and send burst words to the downstream nodes.
DStream IV	Track burst words that matches the tracking condition, otherwise remove it from the burst word set.

Figure 5.

Architecture of the topic detection and trend tracing algorithm based on Spark Streaming.

5. Experiment results

In this section, firstly, the feasibility of the Negative Binomial Distribution model is validated by comparing it against the frequently used Poisson Distribution model. Then, the algorithm proposed in this paper is applied to show the results of burst Weibo topic detection and trend tracing.

5.1 The comparison of the fitting results between the Negative Binomial Distribution and Poisson Distribution

As described in Section 3.1, the Poisson Distribution is often used to simulate the probability distribution of the occurrence frequencies of the random events in a large number of tests. However, the Poisson Distribution cannot adapt to the actual situation in some cases with respect to its variance and mean being equal. For example, if the distribution of the actual data is more divergent and its variance is greater than its mean, then using the Poisson Distribution will not be suitable. Therefore, considering the Weibo data’s dispersion, Negative Binomial Distribution is adopted to fit the distribution of the Weibo topics.

To verify that the Negative Binomial Distribution fits the Weibo topic data more accurately, we use the Weibo data after the Nepal earthquake, as mentioned in Section 3.2, as samples, and we compare the fitting results of the Negative Binomial Distribution and Poisson Distribution with the words ‘Nepal’ and ‘Earthquake’. Here, we adopt the Pearson chi-square test to verify the fitting degree, and we implement the test by using the R language. The comparison results are shown in Tables 4 and 5.

Table 4
Comparison of the fitting results between NB and Poisson with the word ‘Nepal’

Time	Periods	Number	Comparison of Goodness-of-fit test
sequence	of time	of sample	X^ 2		$p$ -value
		points	NB	Poisson	NB	Poisson
T ${}_{1}$	10 min	20	2.985633	4.984345	0.2247387	0.1729471
T ${}_{2}$	20 min	40	5.299191	12.52159	0.1511549	0.01386612
T ${}_{3}$	30 min	60	5.984393	37.23531	0.3077405	N/A
T ${}_{4}$	40 min	80	8.755862	55.80766	0.1192073	N/A
T ${}_{5}$	50 min	100	4.833318	47.75577	0.4365592	N/A

Table 5

Comparison of fitting results between NB and Poisson with the word ‘Earthquake’

Time	Periods	Number	Comparison of Goodness-of-fit test
sequence	of time	of sample	X^ 2		$p$ -value
		points	NB	Poisson	NB	Poisson
T ${}_{1}$	10 min	20	2.985633	4.984345	0.9808047	0.94381
T ${}_{2}$	20 min	40	5.299191	12.52159	0.728657	0.250714
T ${}_{3}$	30 min	60	5.984393	37.23531	0.2681777	N/A
T ${}_{4}$	40 min	80	8.755862	55.80766	0.4229769	N/A
T ${}_{5}$	50 min	100	4.833318	47.75577	0.05220264	N/A

To enhance the credibility of our experiments, we analyzed the Weibo data after the big explosion at TangGu Tianjin China on 12 Aug 2015 in the same way as above. The Results are shown in Table 6 and 7.

Table 6

Comparison of fitting results between NB and Poisson with the word ‘Tianjin’

Time	Periods	Number	Comparison of Goodness-of-fit test
sequence	of time	of sample	X^ 2		$p$ -value
		points	NB	Poisson	NB	Poisson
T ${}_{1}$	10 min	20	1.774139	5.371821	0.700575	0.674150
T ${}_{2}$	20 min	40	5.938544	18.938862	0.520469	0.179081
T ${}_{3}$	30 min	60	7.171907	63.423558	0.191556	0.026336
T ${}_{4}$	40 min	80	6.760552	46.453788	0.302126	N/A
T ${}_{5}$	50 min	100	3.299972	31.960386	0.037288	N/A

Table 7

Comparison of fitting results between NB and Poisson with the word ‘explosion’

Time	Periods	Number	Comparison of Goodness-of-fit test
sequence	of time	of sample	X^ 2		$p$ -value
		points	NB	Poisson	NB	Poisson
T ${}_{1}$	10 min	20	1.774139	5.371821	0.160528	0.123534
T ${}_{2}$	20 min	40	5.938544	18.938862	0.107968	0.099054
T ${}_{3}$	30 min	60	7.171907	63.423558	0.219815	0.010463
T ${}_{4}$	40 min	80	6.760552	46.453788	0.085148	N/A
T ${}_{5}$	50 min	100	3.299972	31.960386	0.311828	N/A

As shown in the tables, the Poisson distribution marginally succeeds at fitting the data over the short time periods but fails over the long term. Nevertheless, even though the Poisson Distribution can fit the occurrence frequency over a short time period, its p-value is smaller than that of the Negative Binomial Distribution. This finding indicates that the Negative Binomial Distribution performs better than the Poisson Distribution at fitting the Weibo data.

5.2 Result of topic detection and trend tracing

As previously mentioned, after the Nepal earthquake occurred, the Weibo data were obtained from the Weibo API as a data source. In the computing topology, the program is set to access the API once every 30 seconds to obtain the most recent 200 pieces of Weibo data.

The changes in the obtained topic word sets obtained by running our proposed algorithm are shown in Table 8. Here, we set the time-window size to be 20 minutes and update the results every 2 minutes.

Table 8
The results of the topic word detection

Time sequence	The set of topic words
T ${}_{1}=$ 20 min	{Earthquake, Nepal, rescue, Everest, News, red packets, constellation, weather}
T ${}_{2}=$ 22 min	{Earthquake, Nepal, rescue, urgency, injured, News, red packets, hurt, constellation, weather}
T ${}_{3}=$ 24 min	{Earthquake, Nepal, rescue, urgency, injured, disaster, constellation, weather}
T ${}_{4}=$ 26 min	{Earthquake, Nepal, injured, disaster, News, constellation, weather}
T ${}_{5}=$ 28 min	{Earthquake, Nepal, urgency, disaster, News, constellation, weather}
T ${}_{6}=$ 30 min	{Earthquake, Nepal, rescue, disaster, taking a taxi, News, coupon, constellation, weather}
T ${}_{7}=$ 32 min	{Earthquake, Nepal, rescue, News, taking a taxi, constellation, weather}
T ${}_{8}=$ 34 min	{Earthquake, Nepal, injured, disaster, News, constellation, weather}

From Table 8, we can find that some topic words, such as ‘Earthquake,’ and ‘Nepal,’ are persistently maintained in the word sets. This finding is consistent with the real situation. Some of the words, such as ‘rescue’, ‘urgency’ and ‘disaster’ also occurred frequently. These words are closely related to the Nepal earthquake. Furthermore, the words ‘constellation’ and ‘weather’ are popular words in Weibo at any time, while they do not represent any meaningful burst events. This type of word can be filtered in the step of data preprocessing. In addition, advertising words, such as ‘red packets’, ‘taking a taxi’ and ‘coupon’, occur occasionally. The reason that these words are detected is that advertising topics can occur frequently during a specific time period, but the lifecycles of these topic words will never end.

Above all, for the real burst topics and emergencies, the keywords occur continuously in the word set for a long time. However, for the advertising topics, their lifecycles do not last very long.

Here, we choose the topic word ‘Nepal’ as an example, and we trace its trends and discuss the impact of the time window size on the results. Figure 6 shows the variations in the hot degree $\hat{m}$ when the time window size is 10 minutes and 20 minutes. Because the time window exists, the computing will not be initiated until the time window is filled by data. Thus, there are no computing results in the first 10 or 20 minutes.

Figure 6.

Trend tracking results of a topic’s Hot Degree.

Figure 6 shows that the overall hot degree trends of the topic are similar even though the time window sizes are different. The value of the hot degree rises rapidly at the beginning, followed by smooth fluctuations over a period of time, and then, it declines at approximately 35 min and, finally, climbs back. During the total 50 minutes, two periods of obvious increase occur, from 10 min to 20 min and from 35 min to 45 min.

What’s more, the curve with larger time window of 20 minutes is smoother than the curve with a time window of 10 minutes. That is, when the time window is larger, the curve is smoother. This relationship arises because a larger time window has smoothing effects on the random data. Furthermore, when the time window size is 20 minutes, the appearances of the peaks are delayed compared with those with the time window of 10 minutes.

Figure 7 displays the changes in the dispersion degree $\hat{r}$ on the topic ‘Nepal’ when the time window size is 10 minutes and 20 minutes.

Figure 7.

Tracking results of the topic’s Dispersion Degree.

As previously mentioned, there is a negative correlation relationship between the value of $\hat{r}$ and the aggregation degree. A smaller $\hat{r}$ predicts a greater aggregation degree. The figure indicates that the overall trends in the dispersion degree are similar between two time-window sizes. The value of $\hat{r}$ first rapidly increases and then decreases over an interval of 40 min; then, it climbs back up again. When the size of the time window is 10 minutes, the value of $\hat{r}$ reaches the bottom at approximately 30 min, which is earlier than the time $\hat{r}$ reaches the bottom when the time window size is 20 min; thus, there is a delay in the computing when the time window size is greater.

At the same time, during the period in which the hot degree obviously increases, the dispersion degree also has an apparent downward trend. During the period in which the hot degree is continuously fluctuate, the dispersion degree decreases, and finally, it retains stable. This finding illustrates that when the topic’s hot degree changes significantly, the dispersion degree $\hat{r}$ also changes; therefore, the value of the dispersion degree is sensitive to the situation in which the topic is obviously fluctuate.

Combined with Figs 6 and 7, when the time window size is small, $\hat{r}$ shows a obvious rising trends at the beginning while $\hat{m}$ remains small. It indicates that the frequency of a topic will be abnormal when the topic begins to burst. It is helpful to detect the moment at which the topic begins. When the size of the time window is extended to 20 minutes, the whole curve is smoother, which shows the overall development of the topic but no longer catches the moment at which the topic begins because of the time delay. However, many topics in Weibo are related to advertisements, and they often burst during a specific short period of time. In that case, a larger size of the time window will help filter this type of short-term topic. Therefore, the size of the time window can be dynamically adjusted to fit the different demands of the topic detection.

6. Conclusions

In this study, research on the occurrence regularity of Weibo words is conducted based on social platforms, and the idea of using the Negative Binomial Distribution model to fit the word distribution is innovatively proposed; in addition, the Weibo topic trend is simulated by tracking the model arguments. Meanwhile, a topic detection and trend-tracing method based on the time window is designed, which can eliminate the randomness of the data and improve the accuracy of the results, further allowing a better fit for analyzing the Weibo stream data. Furthermore, according to the Spark Streaming real-time stream computing framework, the architectures of Weibo topic discovery and real-time tracing are designed to implement the relevant algorithm in real time. Experiments prove the effectiveness of the proposed method, and we further discuss the influence of the time window size on the results. The research in this paper can be used for applications designed to inform the public of emergencies in a timely manner and to applications used to assist related agencies in making important decisions in time.

Footnotes

Acknowledgments

This paper is supported by the National Natural Science Foundation of China under Grant No. 60940032, No. 61073034, and No. 61370064; the Program for New Century Excellent Talents in University of Ministry of Education of China under Grant No. NCET-10–0239; the Science Foundation of Ministry of Education of China and China Mobile Communications Corporation under Grant No. MCM20130371; and the Open Project Sponsor of Beijing Key Laboratory of Intelligent Communication Software and Multimedia under Grant ITSM201503; The National Social Science Foundation of China under Grant No. BCA150050.

References

Lau

J.H.

Collier

and Baldwin

, On-line trend analysis with topic models: #twitter Trends detection topic model online, Proceedings of COLING 2012, pp. 1519–1534.

Huang

Liu

and Dang

, Burst topic discovery and trend tracing based on Storm, Physica A: Statistical Mechanics and its Applications 416 (2014), 331–339.

Sakaki

Okazaki

and Matsuo

, Earthquake shakes Twitter users: real-time event detection by social sensors, Proceedings of the 19th international conference on World wide web, 2010, pp. 851–860.

Guzman

and Poblete

, On-line relevant anomaly detection in the Twitter stream, Proceedings of the ACM SIGKDD workshop on outlier detection and description, 2013, pp. 31–39.

Yin

Karimi

Robinson

et al., ESA: emergency situation awareness via microbloggers, Proceedings of the 21st ACM international conference on Information and knowledge management, 2012, pp. 2701–2703.

Blei

D.M.

A.Y.

and Jordan

M.I.

, Latent dirichlet allocation, Journal of Machine Learning Research (3 Jan 2003), 3993–1022.

Andreas

and Samu

, Using the Negative Binomial Distribution to model overdispersion in ecological count data, Ecology 92(7) (2011), 1414–1421.

Cameron

M.A.

Power

Robinson

et al., Emergency situation awareness from twitter for crisis management, Proceedings of the 21st International Conference on World Wide Web, 2012, pp. 695–698.

Chardonnens

Cudre-Mauroux

Grund

et al., Big data analytics on high Velocity streams: A case study, 2013 IEEE International Conference on Big Data, 2013, pp. 784–787.

10.

Chen

C.P.

and Zhang

C.Y.

, Data-intensive applications, challenges, techniques and technologies: A survey on Big Data, Information Sciences 275 (2014), 314–347.

11.

Kleinberg

, Bursty and hierarchical structure in streams, Data Mining and Knowledge Discovery 7(4) (2003), 373–397.

12.

Papalexakis

E.E.

Beutel

and Steenkiste

, Network Anomaly Detection Using Co-clustering, 2012 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, 2012, pp. 403–410.

13.

Guha

Kim

and Shim

, XWAVE: optimal and approximate extended wavelets, Proceedings of the Thirtieth international conference on Very large data bases-Volume 30, 2004, pp. 288–299.

14.

Jamali

and Rangwala

, Digging Digg: Comment Mining, Popularity Prediction, and Social Network Analysis, 2009 International Conference on Web Information Systems and Mining, 2009, pp. 32–38.

15.

Bennett

Giles

Halevy

et al., Channeling the deluge: research challenges for big data and information systems, Proceedings of the 22nd ACM international conference on Information & Knowledge Management, 2013, pp. 2537–2538.

16.

Haidar

Kulkarni

and Pan

, Forecasting model for crude oil prices based on artificial neural networks, 2008 International Conference on Intelligent Sensors, Sensor Networks and Information Processing, 2008, pp. 103–108.

17.

Mathioudakis

and Koudas

, TwitterMonitor: trend detection over the twitter stream, Proceedings of the 2010 ACM SIGMOD International Conference on Management of data, 2010, pp. 1155–1158.

18.

Osborne

Petrovi

Mccreadie

et al., Bieber no more: First Story Detection using Twitter and Wikipedia, Sigir 2012 workshop on time-aware information access, 2012.

19.

Gomez

Kaltenbrunner

and Lopez

, Statistical Analysis of the Social Network and Discussion Threads in Slashdot, Proceedings of the 17th international conference on World Wide Web, 2008, pp. 645–654.

20.

Xie

Zhu

Jiang

et al., TopicSketch: Real-time bursty topic detection from twitter, IEEE Transactions on Knowledge and Data Engineering 28(8) (2016), 2216–2229.

21.

Ifrim

Shi

and Brigadir

, Event Detection in Twitter using Aggressive Filtering and Hierarchical Tweet Clustering, Second Workshop on Social News on the Web (SNOW), 2014.

22.

Nguyen

D.T.

and Jung

, Real-time event detection for online behavioral analysis of big social data, Future Generation Computer Systems 66 (2017), 137–145.

23.

Huang

Yang

Mahmood

et al., Microblog Topic Detection Based on LDA Model and Single-Pass Clustering, International Conference on Rough Sets and Current Trends in Computing, 2012, pp. 166–171.

24.

Rice

, Mathematical statistics and data analysis (Third edition), Cengage Learning, 2006.

25.

Tripathi

R.C.

, Negative Binomial Distribution, Betascript Publishing, 2010.