More Web Proxy on the site http://driver.im/

research-article

Two-stage anomaly detection algorithm via dynamic community evolution in temporal graph

Authors:

Guannan LiuAuthors Info & Claims

Applied Intelligence, Volume 52, Issue 11

Pages 12222 - 12240

https://doi.org/10.1007/s10489-021-03109-4

Published: 01 September 2022 Publication History

Abstract

Detecting anomalies from a massive amount of user behavioral data is often liken to finding a needle in a haystack. While tremendous efforts have been devoted to anomaly detection from temporal graphs, existing studies rarely consider community evolution and evolutionary paths simultaneously, and analyze those characteristics for the purpose of anomaly detection. Therefore, we propose a two-stage anomaly detection (TSAD) framework to detect anomalies. In this study, we suggest detecting the community evolution events from a sequence of snapshot graphs by constructing an evolution bipartite graph and designing community similarity scores. We then propose a novel anomaly detection method combining community evolution-based anomaly detection and evolutionary path-based anomaly detection. An anomalous score is designed to detect anomalous community evolution events by extracting the characteristics of evolution communities in the community evolution-based anomaly detection method. Moreover, to reduce the false alarm rate, we propose evolutionary path-based anomaly detection to further detect the abnormality of the identified normal evolutionary paths by extracting the characteristics of the identified anomalous evolutionary paths based on community evolution-based anomaly detection. We conduct extensive experiments on real-world datasets and demonstrate that TSAD consistently outperforms competitive baseline methods in anomaly detection.

References

[1]

Bródka P and Saganowski S Ged: the method for group evolution discovery in social networks Soc Netw Anal Min 2013 3 1 1-14

[2]

Kioucheab AE, Lagraac S, Amroucheb K, Seba H (2020) A simple graph embedding for anomaly detection in a stream of heterogeneous labeled graphs. Pattern Recognition

[3]

Cazabet R, Amblard F (2014) Dynamic Community Detection. Springer, New York, pp 404–414

[4]

Chelmis C, Dani R (2017) Assist: Automatic summarization of significant structural changes in large temporal graphs. In: Proceedings of the 2017 ACM on web science conference, WebSci ’17. Association for computing machinery, New York, pp 201–205

[5]

Coscia M, Giannotti F, Pedreschi D (2011) A classification for community discovery methods in complex networks. Stat Anal Data Min ASA Data Sci J:4

[6]

Eswaran D, Faloutsos C (2018) Sedanspot: Detecting anomalies in edge streams. In: 2018 IEEE International conference on data mining (ICDM), pp 953–958

[7]

Eswaran D, Faloutsos C, Guha S, Mishra N (2018) Spotlight: Detecting anomalies in streaming graphs. In: Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery and data mining, KDD ’18. Association for computing machinery, New York, pp 1378–1386

[8]

Christos F, Neil S, Danai K, Joshua V, Gallagher T (2016) Deltacon: Principled massive-graph similarity function with attribution. ACM Trans Knowl Discov Data 10(3):28.1

[9]

Fortunato S (2009) Community detection in graphs. Phys Rep 486(3-5)

[10]

Holme P, Saram?ki J (2012) Temporal networks. Phys Rep 519(3):97–125

[11]

Hooi B, Shin K, Song HA, Beutel A, Shah N, Faloutsos C (2017) Graph-based fraud detection in the face of camouflage. ACM Trans Knowl Discov Data 11(4)

[12]

Hooi B, Song HA, Beutel A, Shah N, Shin K, Faloutsos C (2016) Fraudar: Bounding graph fraud in the face of camouflage. In: Proceedings of the 22Nd ACM SIGKDD international conference on knowledge discovery and data mining, KDD ’16. ACM, New York, pp 895–904

[13]

Hu M, Xu G, Ma C, Daneshmand M (2019) Detecting review spammer groups in dynamic review networks. In: Proceedings of the ACM turing celebration conference - China, ACM TURC ’19. Association for computing machinery

[14]

Hu Y, Yang B, and Lv C A local dynamic method for tracking communities and their evolution in dynamic networks Knowl-Based Syst 2016 110 176-190

[15]

Jiang M, Cui P, Beutel A, Faloutsos C, Yang S (2014) Inferring strange behavior from connectivity pattern in social networks. In: Advances in knowledge discovery and data mining. Springer International Publishing, Cham, pp 126–138

[16]

Jiang M, Cui P, Beutel A, Faloutsos C, Yang S (2016) Catching synchronized behaviors in large networks: A graph mining approach. ACM Trans Knowl Discov Data 10(4)

[17]

Jurgovsky J, Granitzer M, Ziegler K, Calabretto S, Portier PE, He-Guelton L, and Caelen O Sequence classification for credit-card fraud detection Expert Syst Appl 2018 100 234-245

[18]

Liu S, Hooi B, Faloutsos C (2017) Holoscope: Topology-and-spike aware fraud detection. In: Proceedings of the 2017 ACM on conference on information and knowledge management, CIKM ’17. ACM, New York, pp 1539–1548

[19]

Liu S, Hooi B, Faloutsos C (2018) A contrast metric for fraud detection in rich graphs. IEEE Trans Knowl Data Eng:1–1

[20]

Lu Z, Johan W, and Arye N Community detection in complex networks via clique conductance Sci Rep 2018 8 1 5982

[21]

Macha M and Akoglu L Explaining anomalies in groups with characterizing subspace rules Data Min Knowl Discov 2018 32 5 1444-1480

[22]

Manzoor E, Milajerdi SM, Akoglu L (2016) Fast memory-efficient anomaly detection in streaming heterogeneous graphs. In: Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining, KDD ’16. Association for computing machinery, New York, pp 1035–1044

[23]

Meng J, Beutel A, Peng C, Hooi B, Yang S, and Faloutsos C Spotting suspicious behaviors in multimodal data: a general metric and algorithms IEEE Trans Knowl Data Eng 2016 28 8 2187-2200

[24]

Mohammadmosaferi KK, Naderi H (2020) Evolution of communities in dynamic social networks: An efficient map-based approach. Expert Syst Appl 147:113221–

[25]

Palla G, Barabasi AL, and Vicsek T Quantifying social group evolution Nature 2007 446 664-7

[26]

Peixoto T, Rosvall M (2017) Modeling sequences and temporal networks with dynamic community structures. Nat Commun:8

[27]

Perozzi B, Akoglu L (2018) Discovering communities and anomalies in attributed graphs: interactive visual exploration and summarization. ACM Trans Knowl Discov Data 12(2)

[28]

Ranshous S, Harenberg S, Sharma K, Samatova NF (2016) A scalable approach for outlier detection in edge streams using sketch-based approximations. In: Proceedings of the 2016 SIAM international conference on data mining

[29]

Rayana S, Akoglu L (2015) Collective opinion spam detection: Bridging review networks and metadata. In: Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining, KDD ’15. Association for Computing Machinery, New York, pp 985–994

[30]

Rodrigues J Copycatch: stopping group attacks by spotting lockstep behavior in social networks Comput Rev 2014 55 8 509-509

[31]

Rossetti G, Cazabet R (2018) Community discovery in dynamic networks: a survey. ACM Comput Surv 51(2)

[32]

Sachpenderis N, Koloniari G (2018) Determining interesting communities in evolving social networks, pp 249–254

[33]

Shah N, Beutel A, Gallagher B, Faloutsos C (2014) Spotting suspicious link behavior with fbox: an adversarial perspective. In: 2014 IEEE International conference on data mining, pp 959–964

[34]

Shah N, Beutel A, Hooi B, Akoglu L, Gunnemann S, Makhija D, Kumar M, Faloutsos C (2015) Edgecentric: Anomaly detection in edge-attributed networks. In: 2016 IEEE 16Th international conference on data mining workshops (ICDMW)

[35]

Shin K, Eliassi-Rad T, and Faloutsos C Patterns and anomalies in k-cores of real-world graphs with applications Knowl Inf Syst 2018 54 3 677-710

[36]

Shin K, Hooi B, Faloutsos C (2016) M-zoom: Fast dense-block detection in tensors with quality guarantees. In: Joint european conference on machine learning and knowledge discovery in databases

[37]

Shin K, Hooi B, Faloutsos C (2018) Fast, accurate, and flexible algorithms for dense subtensor mining. ACM Trans Knowl Discov Data 12(3)

[38]

Shin K, Hooi B, Kim J, Faloutsos C (2017) D-cube: Dense-block detection in terabyte-scale tensors. In: Proceedings of the tenth ACM international conference on web search and data mining, WSDM ’17, pp 681–689

[39]

Shin K, Hooi B, Kim J, Faloutsos C (2017) Densealert: Incremental dense-subtensor detection in tensor streams. In: Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining, KDD ’17. Association for computing machinery, New York, pp 1057–1066

[40]

Teng W, Fang C, Lin D, Felix S (2015) Localizing temporal anomalies in large evolving graphs. In: SDM, pp 927–935

[41]

Traag VA, Waltman L, Eck NV (2019) From louvain to leiden: guaranteeing well-connected communities. Sci Rep 9(1)

[42]

Van Vlasselaer V, Eliassi-Rad T, Akoglu L, Snoeck M, and Baesens B Gotcha! network-based fraud detection for social security fraud Manag Sci 2017 63 9 3090-3110

[43]

Wagenseller P, Wang F, and Wu W Size matters: a comparative analysis of community detection algorithms IEEE Trans Comput Soc Syst 2018 5 4 951-960

[44]

Wang H, Qiao C (2019) A nodes’ evolution diversity inspired method to detect anomalies in dynamic social networks. IEEE Trans Knowl Data Eng:1–1

[45]

Yang Z, Algesheimer R, Tessone C (2016) A comparative analysis of community detection algorithms on artificial networks. Sci Rep:6

[46]

Yoon M, Hooi B, Shin K, Faloutsos C (2020) Fast and accurate anomaly detection in dynamic graphs with a two-pronged approach

Cited By

Bautista EBrisson LBothorel CSmits GAngélica LLattanzi SMuñoz Medina AAkoglu LGionis AVassilvitskii S(2024)MAD: Multi-Scale Anomaly Detection in Link StreamsProceedings of the 17th ACM International Conference on Web Search and Data Mining10.1145/3616855.3635834(38-46)Online publication date: 4-Mar-2024
https://dl.acm.org/doi/10.1145/3616855.3635834
Shadrooh SNørvåg K(2024)SMoTeF: Smurf money laundering detection using temporal order and flow analysisApplied Intelligence10.1007/s10489-024-05545-454:15-16(7461-7478)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1007/s10489-024-05545-4

Recommendations

Graph-based anomaly detection
KDD '03: Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining

Anomaly detection is an area that has received much attention in recent years. It has a wide variety of applications, including fraud detection and network intrusion detection. A good deal of research has been performed in this area, often using strings ...
Community-based anomaly detection in evolutionary networks

Networks of dynamic systems, including social networks, the World Wide Web, climate networks, and biological networks, can be highly clustered. Detecting clusters, or communities, in such dynamic networks is an emerging area of research; however, less ...
Community-based anomaly detection using spectral graph filtering
Abstract
Several applications have a community structure where the nodes of the same community share similar attributes. Anomaly or outlier detection in networks is a relevant and widely studied research topic with applications in various ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Applied Intelligence

Applied Intelligence Volume 52, Issue 11

Sep 2022

1249 pages

ISSN:0924-669X

Issue’s Table of Contents

© The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature 2022.

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 September 2022

Accepted: 10 December 2021

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 19 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Bautista EBrisson LBothorel CSmits GAngélica LLattanzi SMuñoz Medina AAkoglu LGionis AVassilvitskii S(2024)MAD: Multi-Scale Anomaly Detection in Link StreamsProceedings of the 17th ACM International Conference on Web Search and Data Mining10.1145/3616855.3635834(38-46)Online publication date: 4-Mar-2024
https://dl.acm.org/doi/10.1145/3616855.3635834
Shadrooh SNørvåg K(2024)SMoTeF: Smurf money laundering detection using temporal order and flow analysisApplied Intelligence10.1007/s10489-024-05545-454:15-16(7461-7478)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1007/s10489-024-05545-4

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents