Abstract
Many real world networks evolve over time indicating their dynamic nature to cope up with the changing real life scenarios. Detection of various categories of anomalies, also known as outliers, in graph representation of such network data is essential for discovering different irregular connectivity patterns with potential adverse effects such as intrusions into a computer network. Characterizing the behavior of such anomalies (outliers) during the evolution of the network over time is critical for their mitigation. In this context, a novel method for an effective characterization of network anomalies is proposed here by defining various categories of graph outliers depending on their temporal behavior noticeable across multiple instances of a network during its evolution. The efficacy of the proposed method is demonstrated through an experimental evaluation using various benchmark graph data sets.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Akoglu, L., McGlohon, M., Faloutsos, C.: Oddball: Spotting anomalies in weighted graphs. In: Zaki, M.J., Yu, J.X., Ravindran, B., Pudi, V. (eds.) PAKDD 2010. LNCS, vol. 6119, pp. 410–421. Springer, Heidelberg (2010)
Anagnostopoulos, A., Kumar, R., Mahdian, M., Upfal, E., Vandin, F.: Algorithms on evolving graphs. In: ACM ITCS, Cambridge, Massachussets, USA, pp. 149–160 (2012)
Chakrabarti, D.: AutoPart: Parameter-free graph partitioning and outlier detection. In: Boulicaut, J.-F., Esposito, F., Giannotti, F., Pedreschi, D. (eds.) PKDD 2004. LNCS (LNAI), vol. 3202, pp. 112–124. Springer, Heidelberg (2004)
Chandola, V., Banerjee, A., Kumar, V.: Anomaly detection: A survey. ACM Computing Surveys 41(3) (2009)
Ge, Y., Xiong, H., Zhou, Z.H., Ozdemir, H., Yu, J., Lee, K.C.: TOP-EYE: Top-k evolving trajectory outlier detection. In: ACM CIKM, Toronto, Canada, pp. 1733–1736 (2010)
He, W., Hu, G., Zhou, Y.: Large-scale ip network behavior anomaly detection and identification using substructure-based approach and multivariate time series mining. Telecommunication Systems 50(1), 1–13 (2012)
Kim, M., Leskovec, J.: Latent multi-group memebership graph model. In: ICML, Edinburgh, Scotland, UK (2012)
Leskovec, J.: Stanford large network dataset collection (2013), http://snap.stanford.edu/data/index.html
Ley, M.: Dblp - some lessons learned. PVLDB 2(2), 1493–1500 (2009)
Li, X., Bian, F., Crovella, M., Diot, C., Govindan, R., Iannaccone, G., Lakhina, A.: Detection and identification of network anomalies using sketch subspaces. In: ACM IMC, Rio de Janeiro, Brazil (2006)
Mongiovi, M., Bogdanov, P., Ranca, R., Singh, A.K., Papalexakis, E.E., Faloutsos, C.: Netspot: Spotting significant anomalous regions on dynamic networks. In: SDM, Austin, Texas, pp. 28–36 (2013)
Noble, C.C., Cook, D.J.: Graph-based anomaly detection. In: Proc. SIGKDD, Washington, DC, USA, pp. 631–636 (2003)
Papalexakis, E.E., Akoglu, L., Ienco, D.: Do more views of a graph help? community detection and clustering in multi-graphs. In: Fusion, Istanbul, Turkey, pp. 899–905 (2013)
Rossi, R.A., Neville, J., Gallagher, B., Henderson, K.: Modeling dynamic behavior in large evolving graphs. In: WSDM, Rome, Italy, pp. 667–676 (2013)
Thottan, M., Ji, C.: Anomaly detection in ip networks. IEEE Trans. on Signal Processing 51(8), 2191–2204 (2003)
Wu, L., Wu, X., Lu, A., Zhou, Z.: A spectral approach to detecting subtle anomalies in graphs. Journal of Intelligent Information Systems 41, 313–337 (2013)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Suri, N.N.R.R., Murty, M.N., Athithan, G. (2014). Characterizing Temporal Anomalies in Evolving Networks. In: Tseng, V.S., Ho, T.B., Zhou, ZH., Chen, A.L.P., Kao, HY. (eds) Advances in Knowledge Discovery and Data Mining. PAKDD 2014. Lecture Notes in Computer Science(), vol 8443. Springer, Cham. https://doi.org/10.1007/978-3-319-06608-0_35
Download citation
DOI: https://doi.org/10.1007/978-3-319-06608-0_35
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-06607-3
Online ISBN: 978-3-319-06608-0
eBook Packages: Computer ScienceComputer Science (R0)