Adaptive Community Detection And System Implementation Towards Finding Emerging Event In Microblogs

With the rapid expansion of social media, microblog-like services have turned into an important source of information in addition to traditional media. How to discover the emerging events in streaming tweets without delay, has become one of the hot topics in data mining area. In order to extract sparse signals of event from data with huge amounts of noise, lots of approaches have been raised in academia to model and detect burst features, which were clustered to gain the complete information of events. Nevertheless, in the real-time updating streaming domain, limited time and space cost is allowed to generate events, which makes traditional static clustering unfit for our need. The main purpose of this thesis is to reduce the cost of finding emerging event in real-time and increase the precision of generated events, by treating community structure in burst feature network as events and producing new event info on the basis of historical events. The main research work and contributions are as follows:Firstly, an adaptive community detection algorithm based on weighted network is proposed. The algorithm is based on the QCA algorithm for unweighted network, which applies the modularity optimization approach. When dynamic changes occur, the algorithm would adaptively adjust the former community structure. Based on the concept of inner and outer force, global effects on movement of node could be determined, which avoids much unnecessary cost to modify the network. Based on that and the goal of optimizing modularity, local adjustments to unstable communities would be made.Secondly, weighted network model is used to model the importance and cooccurrence of bursty words, while the community structure in word network is used for describing the events. Besides, the concept of weight strength is proposed with those weights to evaluate the significance of a local sub-graph, which helps to deduce the modularity quantification on weighted network.Thirdly, a scheme for implementing an online system to discovery emerging events in microblog is proposed. The scheme is based on the feature-pivot approach, builds weighted word graph model with the results of preprocessing and burst estimator, applies adaptive community detection algorithm to find event info. Experiments have shown that bursty events could be efficiently and accurately detected with this system.