Call for Paper - November 2022 Edition
IJCA solicits original research papers for the November 2022 Edition. Last date of manuscript submission is October 20, 2022. Read More

A Comprehensive Survey of Time Series Anomaly Detection in Online Social Network Data

Print
PDF
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Year of Publication: 2017
Authors:
Md Rafiqul Islam, Naznin Sultana, Mohammad Ali Moni, Prohollad Chandra Sarkar, Bushra Rahman
10.5120/ijca2017915989

Md Rafiqul Islam, Naznin Sultana, Mohammad Ali Moni, Prohollad Chandra Sarkar and Bushra Rahman. A Comprehensive Survey of Time Series Anomaly Detection in Online Social Network Data. International Journal of Computer Applications 180(3):13-22, December 2017. BibTeX

@article{10.5120/ijca2017915989,
	author = {Md Rafiqul Islam and Naznin Sultana and Mohammad Ali Moni and Prohollad Chandra Sarkar and Bushra Rahman},
	title = {A Comprehensive Survey of Time Series Anomaly Detection in Online Social Network Data},
	journal = {International Journal of Computer Applications},
	issue_date = {December 2017},
	volume = {180},
	number = {3},
	month = {Dec},
	year = {2017},
	issn = {0975-8887},
	pages = {13-22},
	numpages = {10},
	url = {http://www.ijcaonline.org/archives/volume180/number3/28780-2017915989},
	doi = {10.5120/ijca2017915989},
	publisher = {Foundation of Computer Science (FCS), NY, USA},
	address = {New York, USA}
}

Abstract

In the field of data mining, the social network is one of the complex systems that poses significant challenges in this area. Time series anomaly detection is one of the critical applications. Recent developments in the quantitative analysis of social networks, based largely on graph theory, have been successfully used in various types of time series data. In this paper, we review the studies on graph theory to investigate and analyze time series social networks data including different efficient and scalable experimental modalities. We provide some applications, challenging issues and existing methods for time series anomaly detection.

References

  1. S. Asur and B. A. Huberman, "Predicting the future with social media," in Web Intelligence and Intelligent Agent Technology (WI-IAT), 2010 IEEE/WIC/ACM International Conference on, 2010, pp. 492-499.
  2. V. Chandola, A. Banerjee, and V. Kumar, "Anomaly detection: A survey," ACM computing surveys (CSUR), vol. 41, p. 15, 2009.
  3. B. A. Huberman, D. M. Romero, and F. Wu, "Social networks that matter: Twitter under the microscope," 2008.
  4. J. M. J. M. Gottman, Time-series analysisa comprehensive introduction for social scientists, 1981.
  5. A. Beveridge and J. Shan, "Network of thrones," Math Horizons, vol. 23, pp. 18-22, 2016.
  6. X. Zhang, W. Li, H. Huang, C.-T. Nguyen, X. Chen, X. Wang, et al., "Predicting Happiness State Based on Emotion Representative Mining in Online Social Networks," in Pacific-Asia Conference on Knowledge Discovery and Data Mining, 2017, pp. 381-394.
  7. T. Nguyen, D. Phung, B. Dao, S. Venkatesh, and M. Berk, "Affective and content analysis of online depression communities," IEEE Transactions on Affective Computing, vol. 5, pp. 217-226, 2014.
  8. M. De Choudhury, S. Counts, and E. Horvitz, "Social media as a measurement tool of depression in populations," in Proceedings of the 5th Annual ACM Web Science Conference, 2013, pp. 47-56.
  9. O. L. Haimson, N. Andalibi, M. De Choudhury, and G. R. Hayes, "Relationship breakup disclosures and media ideologies on Facebook," New Media & Society, p. 1461444817711402, 2017.
  10. K. Saha, I. Weber, M. L. Birnbaum, and M. De Choudhury, "Characterizing Awareness of Schizophrenia Among Facebook Users by Leveraging Facebook Advertisement Estimates," Journal of medical Internet research, vol. 19, 2017.
  11. K. Garimella, I. Weber, and M. De Choudhury, "Quote RTs on Twitter: usage of the new feature for political discourse," in Proceedings of the 8th ACM Conference on Web Science, 2016, pp. 200-204.
  12. G. Kitagawa, "Introducing to Time Series Modeling, Chapman & Hall," ed: USA, CRC Press, 2010.
  13. R. H. Shumway and D. S. Stoffer, Time series analysis and its applications: with R examples: Springer Science & Business Media, 2010.
  14. V. Hodge and J. Austin, "A survey of outlier detection methodologies," Artificial intelligence review, vol. 22, pp. 85-126, 2004.
  15. E. Keogh, J. Lin, S.-H. Lee, and H. Van Herle, "Finding the most unusual time series subsequence: algorithms and applications," Knowledge and Information Systems, vol. 11, pp. 1-27, 2007.
  16. R. Hassanzadeh, "Anomaly detection in online social networks: using data-mining techniques and fuzzy logic," Queensland University of Technology, 2014.
  17. G. Blanchard, G. Lee, and C. Scott, "Semi-supervised novelty detection," Journal of Machine Learning Research, vol. 11, pp. 2973-3009, 2010.
  18. W. Chimphlee, A. H. Abdullah, M. N. M. Sap, S. Chimphlee, and S. Srinoy, "Unsupervised clustering methods for identifying rare events in anomaly detection," a a, vol. 2, p. 1, 2005.
  19. L. Tang, "Online Friendship," Encyclopedia of Cyber Behavior, pp. 412-421, 2012.
  20. D. Centola, "The spread of behavior in an online social network experiment," science, vol. 329, pp. 1194-1197, 2010.
  21. A. Gupta, K. P. Sycara, G. J. Gordon, and A. Hefny, "Exploring friend's influence in cultures in Twitter," in Proceedings of the 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, 2013, pp. 584-591.
  22. R. Kumar, J. Novak, and A. Tomkins, "Structure and evolution of online social networks," in Link mining: models, algorithms, and applications, ed: Springer, 2010, pp. 337-357.
  23. K. N. Hampton, L. S. Goulet, C. Marlow, and L. Rainie, "Why most Facebook users get more than they give," Pew Internet & American Life Project, vol. 3, pp. 1-40, 2012.
  24. S. Aral and D. Walker, "Identifying influential and susceptible members of social networks," Science, vol. 337, pp. 337-341, 2012.
  25. K.-K. R. Choo and A. I. o. Criminology, Online child grooming: a literature review on the misuse of social networking sites for grooming children for sexual offences vol. 103: Australian Institute of Criminology Canberra, 2009.
  26. J. Hitchcock, "Cyberbullies, online predators, and what to do about them," Multimedia and Internet@ Schools, vol. 14, p. 13, 2007.
  27. J. Wolak, D. Finkelhor, K. J. Mitchell, and M. L. Ybarra, "Online “predators” and their victims: Myths, realities, and implications for prevention and treatment," 2010.
  28. I. R. Berson, "Grooming cybervictims: The psychosocial effects of online exploitation for youth," Journal of School Violence, vol. 2, pp. 5-18, 2003.
  29. R. Bapna, "When snipers become predators: can mechanism design save online auctions?," Communications of the ACM, vol. 46, pp. 152-158, 2003.
  30. L. Akoglu, M. McGlohon, and C. Faloutsos, "Oddball: Spotting anomalies in weighted graphs," Advances in Knowledge Discovery and Data Mining, pp. 410-421, 2010.
  31. C. Faloutsos, "Large graph mining: patterns, cascades, fraud detection, and algorithms," in Proceedings of the 23rd international conference on World wide web, 2014, pp. 1-2.
  32. M. Gjoka, M. Kurant, C. T. Butts, and A. Markopoulou, "Walking in facebook: A case study of unbiased sampling of osns," in Infocom, 2010 Proceedings IEEE, 2010, pp. 1-9.
  33. R. Gross and A. Acquisti, "Information revelation and privacy in online social networks," in Proceedings of the 2005 ACM workshop on Privacy in the electronic society, 2005, pp. 71-80.
  34. M. E. Newman, D. J. Watts, and S. H. Strogatz, "Random graph models of social networks," Proceedings of the National Academy of Sciences, vol. 99, pp. 2566-2572, 2002.
  35. S. Wasserman and K. Faust, Social network analysis: Methods and applications vol. 8: Cambridge university press, 1994.
  36. R. Diestel, "Graph theory, ser," Graduate Texts in Mathematics. Springer-Verlag, Heidelberg, vol. 173, 2005.
  37. M. E. Newman, "The structure and function of complex networks," SIAM review, vol. 45, pp. 167-256, 2003.
  38. H. Kwak, C. Lee, H. Park, and S. Moon, "What is Twitter, a social network or a news media?," in Proceedings of the 19th international conference on World wide web, 2010, pp. 591-600.
  39. J. O. Rawlings, S. G. Pantula, and D. A. Dickey, Applied regression analysis: a research tool: Springer Science & Business Media, 2001.
  40. A. F. Hayes, "A primer on multilevel modeling," Human communication research, vol. 32, pp. 385-410, 2006.
  41. Z. Pan and J. M. McLeod, "Multilevel analysis in mass communication research," Communication research, vol. 18, pp. 140-173, 1991.
  42. L. D. Ritchie and V. Price, "Of matters micro and macro: Special issues for communication research," Communication Research, vol. 18, pp. 133-139, 1991.
  43. S. Wang and P. Groth, "Measuring the dynamic bi-directional influence between content and social networks," The Semantic Web–ISWC 2010, pp. 814-829, 2010.
  44. M. C. Chuah and F. Fu, "ECG anomaly detection via time series analysis," in International Symposium on Parallel and Distributed Processing and Applications, 2007, pp. 123-135.
  45. S. Akhavan and G. Calva, "‘Automatic Anomaly Detection in ECG Signal by Fuzzy Decision Making," in Proceedings of 6th International Conference on Fuzzy Theory and Technology, 1998, pp. 96-98.
  46. N. A. Heard, D. J. Weston, K. Platanioti, and D. J. Hand, "Bayesian anomaly detection methods for social networks," The Annals of Applied Statistics, vol. 4, pp. 645-662, 2010.
  47. D. Savage, X. Zhang, X. Yu, P. Chou, and Q. Wang, "Anomaly detection in online social networks," Social Networks, vol. 39, pp. 62-70, 2014.
  48. V. Rajagopalan and A. Ray, "Symbolic time series analysis via wavelet-based partitioning," Signal Processing, vol. 86, pp. 3309-3320, 2006.
  49. D. K. Tolani, M. Yasar, A. Ray, and V. Yang, "Anomaly Detection in Aircraft Gas Turbine Engines," JACIC, vol. 3, pp. 44-51, 2006.
  50. M. Bicego and V. Murino, "Investigating hidden Markov models' capabilities in 2D shape classification," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 26, pp. 281-286, 2004.
  51. Z. Liu, J. X. Yu, L. Chen, and D. Wu, "Detection of shape anomalies: A probabilistic approach using hidden markov models," in Data Engineering, 2008. ICDE 2008. IEEE 24th International Conference on, 2008, pp. 1325-1327.
  52. L. Wei, E. Keogh, and X. Xi, "Saxually explicit images: Finding unusual shapes," in Data Mining, 2006. ICDM'06. Sixth International Conference on, 2006, pp. 711-720.
  53. P. Malhotra, L. Vig, G. Shroff, and P. Agarwal, "Long short term memory networks for anomaly detection in time series," in Proceedings, 2015, p. 89.
  54. E. Bullmore and O. Sporns, "Complex brain networks: graph theoretical analysis of structural and functional systems," Nature reviews. Neuroscience, vol. 10, p. 186, 2009.
  55. P. Protopapas, J. Giammarco, L. Faccioli, M. Struble, R. Dave, and C. Alcock, "Finding outlier light curves in catalogues of periodic variable stars," Monthly Notices of the Royal Astronomical Society, vol. 369, pp. 677-696, 2006.
  56. U. Rebbapragada, P. Protopapas, C. E. Brodley, and C. Alcock, "Finding anomalous periodic time series," Machine learning, vol. 74, pp. 281-313, 2009.
  57. H. Cheng, P.-N. Tan, C. Potter, and S. Klooster, "Detection and characterization of anomalies in multivariate time series," in Proceedings of the 2009 SIAM International Conference on Data Mining, 2009, pp. 413-424.
  58. S. Zhang, A. Chakrabarti, J. Ford, and F. Makedon, "Attack detection in time series for recommender systems," in Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, 2006, pp. 809-814.
  59. R. J. Hyndman, E. Wang, and N. Laptev, "Large-scale unusual time series detection," in Data Mining Workshop (ICDMW), 2015 IEEE International Conference on, 2015, pp. 1616-1619.
  60. C. Huang, G. Min, Y. Wu, Y. Ying, K. Pei, and Z. Xiang, "Time Series Anomaly Detection for Trustworthy Services in Cloud Computing Systems," IEEE Transactions on Big Data, 2017.
  61. J. Krumm and E. Horvitz, "Eyewitness: Identifying local events via space-time signals in twitter feeds," in Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems, 2015, p. 20.
  62. J. Chae, D. Thom, H. Bosch, Y. Jang, R. Maciejewski, D. S. Ebert, et al., "Spatiotemporal social media analytics for abnormal event detection and examination using seasonal-trend decomposition," in Visual Analytics Science and Technology (VAST), 2012 IEEE Conference on, 2012, pp. 143-152.
  63. J. A. Iglesias, A. García-Cuerva, A. Ledezma, and A. Sanchis, "Social network analysis: Evolving Twitter mining," in Systems, Man, and Cybernetics (SMC), 2016 IEEE International Conference on, 2016, pp. 001809-001814.
  64. K. Ikeda, G. Hattori, C. Ono, H. Asoh, and T. Higashino, "Early detection method of service quality reduction based on linguistic and time series analysis of twitter," in Advanced Information Networking and Applications Workshops (WAINA), 2013 27th International Conference on, 2013, pp. 825-830.
  65. C. Biernacki, G. Celeux, and G. Govaert, "Assessing a mixture model for clustering with the integrated completed likelihood," IEEE transactions on pattern analysis and machine intelligence, vol. 22, pp. 719-725, 2000.
  66. M. Corduas and D. Piccolo, "Time series clustering and classification by the autoregressive metric," Computational Statistics & Data Analysis, vol. 52, pp. 1860-1872, 2008.
  67. M. Ramoni, P. Sebastiani, and P. Cohen, "Multivariate clustering by dynamics," in AAAI/IAAI, 2000, pp. 633-638.
  68. M. Bicego, V. Murino, and M. A. Figueiredo, "Similarity-based clustering of sequences using hidden Markov models," in International Workshop on Machine Learning and Data Mining in Pattern Recognition, 2003, pp. 86-95.

Keywords

Social networks, Time Series Analysis, Anomaly Detection