eCite Digital Repository

Change point detection for burst analysis from an observed information diffusion sequence of tweets


Saito, K and Ohara, K and Kimura, M and Motoda, H, Change point detection for burst analysis from an observed information diffusion sequence of tweets, Journal of Intelligent Information Systems, 44, (2) pp. 243-269. ISSN 0925-9902 (2015) [Refereed Article]

Copyright Statement

Copyright 2013 Springer Science+Business Media New York

DOI: doi:10.1007/s10844-013-0283-2


We propose a method of detecting the period in which a burst of information diffusion took place from an observed diffusion sequence data over a social network and report the results obtained by applying it to the real Twitter data. We assume a generic information diffusion model in which time delay associated with the diffusion follows the exponential distribution and the burst is directly reflected to the changes in the time delay parameter of the distribution. The shape of the parameter's change is approximated by a step function and the problem of detecting the change points and finding the values of the parameter is formulated as an optimization problem of maximizing the likelihood of generating the observed diffusion sequence. Time complexity of the search is almost proportional to the number of observed data points and has been shown to be very efficient. We first demonstrated that the proposed method can detect the burst using a synthetic data and showed that it performs better than one of the representative state-of-the-art methods, confirming that the proposed method covers a wider range of change patterns. Then, we extended our evaluation on synthetic data to show that it is efficient and effective comparing it with a naive exhaustive search and a simple greedy method. We then apply the method to the real Twitter data of the 2011 To-hoku earthquake and tsunami, and reconfirmed its efficiency and effectiveness. Two interesting discoveries are that a burst period detected by the proposed method tends to contain massive homogeneous tweets on a specific topic even if the observed diffusion sequence consists of heterogeneous tweets on various topics, and that assuming the information diffusion path to be a line shape tree can give a good approximation of the maximum likelihood estimator when the actual diffusion path is not known.

Item Details

Item Type:Refereed Article
Keywords:social networks, information diffusion, change point detection, burst detection
Research Division:Information and Computing Sciences
Research Group:Artificial intelligence
Research Field:Artificial intelligence not elsewhere classified
Objective Division:Information and Communication Services
Objective Group:Information systems, technologies and services
Objective Field:Information systems, technologies and services not elsewhere classified
UTAS Author:Motoda, H (Dr Hiroshi Motoda)
ID Code:88998
Year Published:2015 (online first 2013)
Web of Science® Times Cited:3
Deposited By:Information and Communication Technology
Deposited On:2014-02-22
Last Modified:2018-01-23

Repository Staff Only: item control page