Abstract
Recently, social networks have provided an important platform to detect trends of real-world events. The trends of real-world events are detected by analysing flow of massive bulks of data in continuous time steps over various social media platforms. Today, many researchers have been interested in detecting social network trends, in order to analyse the gathered information for enabling users and organisations to satisfy their information need. This article is aimed at complete surveying the recent text-based trend detection approaches, which have been studied from three perspectives (algorithms, dimension and diversity of events). The advantages and disadvantages of the considered approaches have also been paraphrased separately to illustrate a comprehensive view of the previous works and open problems.
1. Introduction
Nowadays, with the expansion of social communications and ease of access to Internet, public use of social networks is increasing dramatically. Every day, people create content (text, photos, video, etc.) in social networks about various social events which happen in real-world society. In other words, these networks represent a reflection of daily real-world short- or long-term events that researchers, by analysing these events and their developments, can extract useful information and provide to individuals and organisations to improve their performance or adopt a particular policy.
The trend of event is a sequence of related events over a specific period of time [1–3]. Trend detection consists of three steps of event detection, event tracking and trend interpretation that several studies have been held on. Trend detection is able to automatically understand, extract, track and interpret the occurrence of various events.
The most important step of event tracking is event detection step that faces these following challenges: domain dependent, time constraint, detection accuracy, diversified data resources, voluminous data, authenticity and missing data, handling anomalous behaviours and so on [1,4–9].
Information types (i.e. text, video, image) processed during event detection algorithms are very important [1]. Due to the importance and usefulness of text resources, the article is just focused on text resources which provided by Internet in five forms as follows [1]:
Newswire. It comes from news services to provide the latest news on Internet, for example, Facebook News and Telegram channels [1].
Web Forum. It comes from web services whose content is created by users’ posts and comments [10].
Blog. It comes from web sites to show public and private posts, and users can share comment with other people [11].
Email. It comes from mail services to hold email exchanges by a graph, in which every node represents a user and every edge represents email passing between two users [12].
Microblog. It comes from web data stream, in which every user can describe their current status and experiences in a short post thereby cell phone, email and web, like Twitter [13].
Three classes of the most seen events in popular social networks are presented as follows [1]:
Natural or manmade disaster events.
Emerging events.
Public opinion event.
Moreover, events are divided into two distinct categories regarding the presence and absence of basic information, that is, unspecified and specified events [14]. The unspecified events usually include emerging events, general topics and news, which periodically attract users’ attentions. Since no information is available about these events, pattern recognition techniques are commonly used to detect them [14–16]. The specified events contain well-known or scheduled social events. These events can be partially or totally distinguished through information about content, time, location and performance. The methods used to detect these sorts of events are machine learning, data mining and text mining techniques [14].
Events are studied in four dimensions: thematic, temporal, spatial and network structure. In the thematic dimension, event detection algorithms make use of textual features to represent the conceptual content of documents. In the temporal dimension, event detection algorithms make use of temporal features to identify the certain time of text content. In the spatial dimension, event detection algorithms make use of spatial features, for example, latitude and longitude to find the location information. In the network structure dimension, event detection algorithms make use of the current pattern among a user and other users connected to him or her in an online social network [1,17–19].
Machine learning methods are the most commonly used methods for the event detection problem [1]. The linear classification method is a supervised approach that uses labelled data, whereas accessing labelled data is generally very expensive. However, the unsupervised approaches do not need labelled data. Moreover, statistical methods as supervised approaches require a lot of learning data. These methods usually have good accuracy, whereas they consume lots of time and memory. The event detection algorithms are classified into the following six categories:
Graph-based clustering (unsupervised methods);
Spectral clustering (unsupervised methods);
Linear classification (supervised methods);
Statistical (supervised methods);
Indexing (supervised methods);
Other (supervised methods).
According to five forms of text resources, four dimensions of online social network events and six categories of event detection algorithms, trend detection–related works are classified as shown in Figure 1.
A taxonomy of trend detection researches in terms of event dimensions, methods, and data platforms.
In Figure 1, large circles represent event dimensions. The top-left symbols show event detection algorithm. The bottom-left symbols represent dataset types that experiments have been conducted on. The numbers represent the year of publication of the article (e.g. 17 indicates 2017). As shown in Figure 1, the research works analyse events in the thematic, temporal and structural dimensions; however, in recent years, most of the works have put their focuses on structural analysis of networks. Looking closer at Figure 1, it is observed that a few numbers of works have put their focus on using the spatial dimension in analysing trend events. This is due to the difficulties in precise estimation of users’ locations. Moreover, Figure 1 shows that a few works have been run in emails and blogs data resources, and there has been a greater trend to work on newswires and microblogs, such as Twitter; this might be due to the more availability of Twitter and other microblogs data. Linear classification and clustering are used more than other algorithms, and in particular papers published in recent years, the clustering algorithms have been used more frequently. Furthermore, clustering-based approaches have been more evaluated over microblogs data of existing more unspecified events in microblogs.
Until now, the pervious taxonomies are based on dimensions and data forms. In this article, attention has been paid to previous works from another perspective. Trend detection algorithms are generally divided into two general groups: supervised and unsupervised, both are divided into distinct subgroups.
2. Trend detection in social networks
As mentioned before, trend detection process consists of three important steps: event detection, event tracking and trend interpretation, where the challenges of event detection, as the first and most important step, were considered further.
In trend detection, first, domain-specific time intervals are determined for event detection. Depending on the temporal importance of events, the duration of the time step can be extended from a few hours to several months. Then, all related events are detected in each time step; the connection of events at time step t with detected events of the previous time step t – 1 is specified. Then, the event changes and evolutions can be tracked and an interpretation of that event can be introduced. Based on event connection type shown in Figure 2 in consecutive time steps, six key changes occur, which are described as follows:
Birth. The presence of an event in a time step and its absence in any of the previous steps means the birth of that event. For example, in Figure 2, E21 represents a birth at the second time step [20].
Death. In the case of absence of an event at the current time step and its presence at previous time steps, then a death occurs and all trends associated with that event either stop or combine with other trends. In Figure 2, the death of the event E34 occurs between the third and fourth time steps, and the related trend is stopped [20].
Merging. Merging occurs when two or more events that were totally independent and separate at the time step t – 1 are combined to create a new event at the time step t. In Figure 2, the events E11 and E12 are merged at the first time step to create the event E22 at the second time step [20].
Splitting. Splitting occurs when an event at time t – 1 is divided into two or more completely independent events at time step t. For example, in Figure 2, at the third time step, the event E33 is divided into two events E43 and E44 at the fourth time step [20].
Expansion. The trend of events does not change in two successive time steps (like E31 and E41 in Figure 2), but the number of elements (users, posts and so on) has increased with respect to the previous time step. In other words, expansion implies the importance of the corresponding event has increased over time [20].
Contraction. The trend of events does not change in two successive time steps (like E31 and E41 in Figure 2), but the number of elements has decreased with respect to the previous time step. In other words, contraction implies the importance of the corresponding event has decreased over time [20].
Key changes in trend detection.
Figure 3 demonstrates an example of events evolutions in the Enron Email dataset. The graph has been provided by four consecutive months from September to December 1999. Each node represents the email address of a user. If node i sends an email to node j, there is a directed edge from i to j. Coloured nodes represent events. In Figure 3, the key changes of events are well illustrated in consecutive time steps. As observed from September to November, the orange event is merged with the red event, the black event is removed and reborn in November. The purple event has expanded from October to November.
An example of trend detection problem in the Enron Dataset.
Regarding event changes, event detection algorithms follow two scenarios:
Scenario 1. An event detection algorithm is performed at each time step in order to detect events and events changes are tracked in consecutive time step by the help of similarity criteria [20–28]. Due to iterating event detection algorithm at each time step, this scenario is time-consuming [29].
Scenario 2. Algorithms utilises history of changes for all events through consecutive time steps [29–36].
After detecting the trend of an event, it is necessary to provide a comprehensive interpretation, which can be done by either a human expert or a machine by automatically abstracting the content of each event.
Depending on data form, the supervised or unsupervised algorithms are used to track events, which are described in the following section.
2.1. Trend detection algorithm classification
Trend detection algorithms are divided into the supervised and unsupervised methods (Figure 4). The supervised methods are often used for well-known events because they require labelled data; however, the unsupervised methods have become more interesting in recent years for detecting unknown events as well as real-world problems due to the lack of labelled data [14]. Here, the supervised methods are classified into four groups: linear methods, statistical methods, indexing methods and other methods, which are fully reviewed in section 3. The unsupervised methods are divided into two general groups: graph-based clustering and spectral clustering, where the graph-based clustering is also divided into three subgroups: objective function optimisation methods and randomised algorithm and other methods. This category is fully investigated in section 4.
A taxonomy of the trend detection algorithms.
As reported in Table 1, the researches reviewed in this article have been classified in terms of the event dimensions and trend detection methods. Due to the conceptual relationship between trend detection and time, the temporal dimension of the event has been used in trend detection in most researches. Limited use of spatial dimension is due to limited access to the exact location of users. In the unsupervised methods, the structural dimension of the event is often considered, and trend detection method has used these methods in recent years because of existing labelled data. The thematic dimension is often used in the supervised methods because keywords can be used as an event label in natural events.
A taxonomy of reviewed researches in terms of trend detection methods and event dimensions.
3. Supervised methods for trend detection
In many trend detection problems for events such as natural disasters and elections, there are many labelled data (Figure 5). For example, on Twitter, a tweet, depending on the text and hashtag, specifies a specific event. Consequently, supervised methods can be used for such events.
A taxonomy of trend detection researches in terms of event dimensions, data platforms and supervised methods.
3.1. Linear methods
Zubiaga et al. [38] have focused on Twitter features instead of content features. They, first, divided events into four groups: news events, ongoing events, memes and commemoratives, and then learned a model for each group based on Twitter features. During every time step, the input features and keywords have been extracted and a support vector machine is employed to model each group.
Sakaki et al. [2] have introduced an online method to detect earthquake events in 2013, which apply a linear support vector machine classifier to semantically analyse the tweets and express a spatiotemporal model for earthquake detection. The support vector machine classifies posts by content, statistical and Twitter features. In this work, each user is considered as a sensor and every tweet as information which is received from this sensor, which specifies its location.
3.2. Statistical methods
Zhao et al. [39] have identified blogging events in 2014 in the following three categories:
Specified events that focus on a disaster such as a flood or an event that is characterised by keywords.
Personal-related events with a specific person, which is based on name of an important person or celebrity.
General events that are recognised through keywords with high attention in the blog.
This work introduces an event detection method including three main sections: microblog searching and filtering, event detection and event prediction. Microblog searching task is done with the pre-defined interface. Filtering is done by the content quality, through some criteria such as post date, part of speech. Events are detected by object-oriented approach, in which each event is modelled by statistical features.
3.3. Indexing methods
Nunes et al. [40] have proposed a topic modelling method in 2014 to facilitate a searching method for students and faculty members and to suggest important and blog-related discussions in online forums. This work uses thematic tools to identify specific names and topic. These tools compute TF-IDF score through statistical methods in order to select and rank user posts. The output is high rank topic on the online web forum.
Jurgens and Stevens [43] introduced an event detection algorithm in 2009 that tracks semantic changes during time intervals. Distribution of words is built and the temporal random indexing algorithm is employed to detect event.
Note that the two above-mentioned works investigate the event from the viewpoints of thematic and temporal dimensions.
3.4. Other methods
Li et al. [41] have presented a method for online bursty event detection in 2014, which has attracted a lot of attention from users. In this work, incremental time models are used to track topics that change over time.
Xie et al. [37] have employed the dimension reduction method in 2016 to identify co-occurring bursty keywords and introduced a TopicSketch framework on Twitter.
Hennig et al. [42] have focused in 2014 on extracting, analysing and visualising events whose information are found in a lot of documents in blogs. This work detects all events on a set of documents obtained during a given time interval. Each document is identified by an identifier code, text content and release time. Extraction of keywords is done through TF-IDF and name entity recognition. Finally, the criteria of co-occurrence and conditional co-occurrence of keywords are used for event detection.
These works have investigated event’s thematic and temporal dimensions.
Zhao and Mitra [44] have used three time steps for event extraction from the Enron email dataset in 2007: text-based clustering, temporal segmentation and grouping graph. In this work, they use multidimensional analysis tools to extract connections among events. They also consider the temporal, thematic and structure dimensions of event.
4. Unsupervised methods for trend detection
In practice, in many trend detection problems, events are unknown, or there is not enough labelled data to use supervised methods (Figure 6). For this reason, most works utilise unsupervised approaches. In many of these works, the concept of event is assumed to be the same as the community; therefore, the problem of event detection has been reduced to the problem of community detection and also trend detection problem has also been reduced to the problem of dynamic community detection. Theoretically, there are differences between the concept of event and community, but there is a close connection in practice. Here, the concepts of trend detection and dynamic community detection are assumed to be the same. Unsupervised methods are divided into graph-based clustering and spectral clustering, which are described in the following section.
A taxonomy of trend detection works in terms of event dimension, data platform, and unsupervised methods.
4.1. Graph-based clustering
The event dimensions are used to build a graph and then the graph is clustered to detect events. In most works, either the content of an event is used to construct a word graph or network structure is used to build a graph of individuals’ communications.
Graph-based clustering algorithms are divided into two general categories; algorithms that try to optimise objective function on the graph and algorithms that only use the graph without optimisation.
4.1.1. Objective function optimisation methods
The modularity criterion is used as an objective function. The modularity criterion is one of the graph structure criteria that represents the ability to divide the graph into smaller sub-graphs (called clusters or communities). The graph modulus represents the sub-graph density.
Greene et al. [20] have developed a general model for the dynamic community detection problem in 2010, which is adaptable to any community-based detection algorithm. In this model, at first time step, the communities representing the trends are detected using a community detection algorithm. Then, in the next time steps after finding the communities, according to Jaccard index, the algorithm maps each community to the last detected communities. This work specifically uses the Louvain algorithm [47]. The main disadvantage to run community detection algorithm at each time step is spending a lot of time in order to detect events.
Kauffman et al. [28] have developed a plugin for the Gephi software to detect dynamic communities. In this work, communities are detected at each time step using the Louvain algorithm, and Jaccard index is used to detect the trend of these communities. This method is very costly because of the use of Jaccard’s similarity criterion on common nodes.
He et al. [29] have used hierarchical clustering to optimise graph modularity criterion at time step t based on the detected communities at previous time step. Based on the temporal and network structure dimensions of event, they formed a graph at different time intervals and detected events at time t = 0 using the Louvain algorithm. Then, in order to detect the event, in the next step, an algorithm that contains two stages of division and aggregation is introduced. At the division stage, the value of the tendency of each node towards its neighbour nodes is calculated, and if two nodes have a large tendency but are not in same community at time step t – 1, they leave their communities and thus the graph is divided into sub-graphs and separated nodes, and the communities of time step t – 1 that are in the graph of time step t are known as hyper nodes, and each hyper node is divided into modules based on the Louvain algorithm. At the agglomeration stage, the Louvain algorithm is applied to the given graph of the division stage. To investigate the changes between events detected in two consecutive time steps, the intersection of the modules is used; since the number of modules is very much less than the number of nodes, the speed of trend detection algorithm is reasonable.
Cordeiro et al. [30] changed the Louvain algorithm to adapt to dynamic graph environment in 2016. As mentioned in the previous researches, they apply the Louvain algorithm at initial time t = 0 and calculate graph changes at time t with respect to time t – 1, and they only apply the modified Louvain algorithm for communities that have changed over time. This modified algorithm includes heuristic operations on nodes and edges that have changed in the community. This work has improved the evaluation criteria of time and modularity in large graphs.
Nguyen et al. [31] have also proposed an algorithm based on the Louvain algorithm in 2014. It obtains the current events using heuristic methods based on the communities detected at previous time steps. As mentioned in the previous works, the Louvain algorithm is also used here to obtain events at time step t = 0. Then, at next time step, graph changes between t and t – 1 are considered. The changes are divided into four categories: adding a node, adding an edge, removing a node and removing an edge.
One of the reasons for the wide use of Louvain algorithm, which is a hierarchical clustering, is its logarithmic complexity order. The clustering algorithm is usually based on modularity criterion optimisation.
Nguyen et al. [32] have introduced AFOCS algorithm to detect overlapping dynamic community in 2011. This algorithm that attempts to minimise an objective function based on graph density finds the communities in the first step using objective function optimisation and combines the overlapping communities. In next time steps, it extracts graph changes at time t and t – 1 and attempts to adapt the changes to the communities detected in the previous step using heuristic methods. The main advantage of this algorithm in comparison with the previous similar works is considering overlaps in communities, which is closer to real-world problems; however, the input of this algorithm is a threshold to determine the overlap of two communities, which is hard to determine in different domains.
Folino and Pizzuti [27] have formulated the community detection problem in the form of a multi-objective optimisation problem and introduced the DYNMOGA algorithm in 2014. The optimal solution is a collection of Pareto optimal solutions. DYNMOGA uses a non-dominated sort to balance the quality over time steps. It also uses a genetic algorithm to automatically find the number of communities in each time step using an optimal solution. The main problem with this algorithm is the lack of scalability in large networks.
Niu et al. [33] have introduced a method for dynamic community detection and attempted to optimise it using a genetic algorithm in 2017. The algorithm defines an objective function including cluster quality criteria and computational cost. The algorithm is the L-DMGA algorithm that detects graph communities in first time step using the label propagation algorithm; then, in next time steps, it considers each node as a gene and the initial population is a particular set of communities and identifies the optimal grouping at each time step using the selection, mutation and crossover operations. A modularity criterion is used to measure cluster quality, and the normalised mutual information is used for the computational cost. Comparing to the DYNMOGA [27] and FacetNet [23] algorithms, the results have been remarkably improved in terms of the time and cluster quality in large networks. Its time complexity is linear.
Alvari et al. [26] have tried to solve the dynamic community detection problem using the game’s theory. In the proposed D-GT algorithm, each node in the graph is considered as an agent, and for each agent, four operations – join, switch, leave and no action – are considered. The algorithm randomly selects an agent at each time step, considers an operation and calculates benefits based on modularity criterion. This process continues until reaching the Nash equilibrium; then, the information of this step is transferred to the next time step. The main disadvantage of this algorithm is the lack of proper convergence rate in the large real-world networks.
The papers reviewed in this section have investigated all events in terms of network structure and temporal dimensions and formed a graph based on the given dimensions. In the following, other methods are further examined.
4.1.2. Randomised algorithm
Xin et al. [34] have introduced ANRW algorithm to detect overlapped dynamic communities. This algorithm, which is based on non-homogeneous random walk algorithm, at each time interval, first calculates graph changes with considering time t and time t – 1 and then utilises a heuristic method–based graph changes. Because each node works as an independent computing unit, this method is very suitable for parallel computing in large datasets; however, due to having a large number of parameters, it is very difficult to obtain optimal value for each parameter.
Xin et al. [35] introduced the ARWS algorithm in 2016, in which random walk sampling is used instead of focusing on the whole graph to detect overlapping communities. This work is a follow-up to earlier works. In this work, at time t = 0, the RWS algorithm is used to detect the closest nodes to each node in the same community, and in next time steps, it obtains the graph changes in two consecutive time intervals and updates the community which nodes have changed. Its computational cost is much lower than the traditional algorithms of dynamic community detection because it examines information locally. The ARWS algorithm has a large number of parameters that must be set manually, and finding the optimal value of the parameters is very difficult in different domains. In addition, the algorithm is a random process and does not use network properties, which is considered to be a disadvantage of this method.
Xie et al. [25] have presented a label propagation algorithm called LabelRankT in 2013 to solve the dynamic community detection problem. This algorithm is based on Lin et al. [23], where each node only needs its own local information. At each time step, the modified nodes are tracked and their information is updated. This algorithm is an online algorithm that operates well on a variety of directed, undirected, weighted and unweighted graphs.
4.1.3. Other methods
Cazabet et al. [36] introduced an online graph-based algorithm with low computational cost in 2010. Each community in the graph is considered to be an actor that can accept or reject a node. Similar communities are combined with each other, and if communities have nodes with many edges, they would be born, and if they have nodes with few edges, they will be removed. This algorithm does not check the network in separate time steps but sees the network as a set of graph changes. The basic weakness of this research is to manage the nature of network dynamics, especially when a node is removed.
Cazabet et al. [46] have detected the trends of events in the Nico Nico Douga social network in 2012. In this work, which investigates events based on thematic and temporal dimensions, tags of each node are extracted, then are mapped into the graph and the iLCD dynamic community detection algorithm [32,36] is applied. Here, the communities that are a set of words are introduced as an event. The algorithm is capable of correctly detecting short-term and long-term events. The main disadvantage is the lack of proper performance on large online networks.
Sayyadi et al. [24] used a new approach in forming graphs to detect the trend of events according to both temporal and thematic dimensions in 2009. In this approach, the name entities and keywords of the document are extracted, and a graph of words is formed based on document frequency and word co-occurrence in the given documents. Then, using the betweenness centrality benefit, the graph communities are extracted, and each community is considered as a key event. In the next steps, any input document is compared to the built key graph using the cosine similarity and placed in one of the communities. The main weakness of this work is the lack of extensive analysis and experiments on large networks.
4.2. Spectral clustering
Spectral clustering maps the data from graph space to matrix space and then tries to solve the problem in lower dimension space. The main disadvantage of this method is identifying the number of clusters as an input of the problem, while in practice, we do not know about the number of events in the trend detection problem; therefore, the use of these algorithms is very limited and impractical in this problem.
Tang et al. [45] introduced an evolutionary clustering algorithm based on spectral clustering for community detection in multimode networks. This network contains a variety of non-homogeneous actors and different interactions among them. Community detection in multimode networks helps to understand the structure of network characteristics. This algorithm manages the changes of nodes and edges. This method requires specifying the number of communities and the weight of the edges by users, which is one of its main disadvantages.
Lin et al. [23] introduced the FacetNet framework in 2008, which models dynamic communities using hidden Markov chain and tries to maximise the post-probability of the chain using the expectation maximisation algorithm. This algorithm, unlike traditional algorithms, tracks the communities and their changes in a unified way work very well for noisy data and has low computational cost. The low convergence rate and receiving the number of communities as an input is of the main disadvantages.
Aggarwal et al. [22] introduced a new evolutionary clustering method in 2012 based on thematic, network structure and temporal dimensions of the event. The data are clustered according to the defined similarity criterion, which is based on a coefficient of structural similarity and content similarity. In large networks, because a long time is taken to calculate the similarity function, a sketch-based method for storing nodes is used for increasing the computational speed. After detecting the clusters, events are divided according to the events in the previous steps into emerging and evolving events. Experiments show that the use of structural similarity only works better in comparison with the combination of structural similarity and content similarity. The main disadvantage is the determination of fixed clusters by users, which is not desirable for real problems.
Zhou and Chen [21] used four event dimensions for trend detection in Twitter data in 2014. The reason for using four dimensions is 140-character limit in Twitter. For each message, an LTT model identifies the similarity for location, time and content dimensions, and a link similarity model identifies structural similarity, and then these two criteria are combined with a coefficient and the resulting criterion is used for clustering. To increase clustering speed, an index-based approach is used, and ultimately this approach was tested based on flood data in Australia, which shows improvements in this approach with respect to previous methods.
5. Conclusion
Because of the ever-increasing use of social networks, real-world events are quickly reflected in social networks, and individuals create content about various aspects of events that contain a wealth of valuable information. Trend detection by tracking events analyzes and investigates the changes that occur for them over time, and the results of the interpretation of these changes can provide individuals and organisations with useful information from the political, economic and social aspects. In this article, we first divided the events into specified and unspecified categories and considered four dimensions of content, time, location and network structure. Then, we investigated the developments in the trend of events over time including birth, death, expansion, contraction, splitting and merging. We generally categorised trend detection algorithms into two categories of supervised and unsupervised learning methods. In section 3, we reviewed the papers in the supervised learning category, and in section 4, we discussed papers in the unsupervised learning category. As seen in this survey, the graph-based clustering algorithms have been very much taken into consideration in the unsupervised learning category due to the lack of need for labelled data. Moreover, the use of the structural dimension of events in modelling the problem has created dramatic changes in the efficiency of trend detection problem.
Footnotes
Declaration of conflicting interests
The author(s) declared no potential conflicts of interest with respect to the research, authorship and/or publication of this article.
Funding
The author(s) received no financial support for the research, authorship and/or publication of this article.
