A Deviation-Based Framework for Unified Community and Anomaly Detection in Social Networks
Received: 28 September 2025 | Revised: 21 October 2025 and 30 October 2025 | Accepted: 3 November 2025 | Online: 29 November 2025
Corresponding author: Hedia Zardi
Abstract
Community detection and anomaly detection are fundamental tasks in social network analysis. While communities represent cohesive groups of users with similar interaction patterns, anomalies are nodes whose behavior deviates from established norms. Traditional methods often address these tasks separately or rely on similarity- and embedding-based measures, which can limit both interpretability and scalability. This work proposes a Deviation-Based model that unifies community and anomaly detection within a single framework. Communities are initialized from high-degree seed nodes and expanded iteratively, whereas anomalies naturally emerge as statistical outliers that deviate from structural and attribute distributions. Experiments on benchmark citation networks, real-world social platforms, and synthetic graphs demonstrate that the proposed model outperforms both classical structural and deep learning-based baselines in terms of community detection (Normalized Mutual Information (NMI), Adjusted Rand Index (ARI), modularity) and anomaly detection (precision, recall, F1-score, Area Under the Curve (AUC)). The model is lightweight, scalable, and interpretable, offering a practical solution for large-scale social networks and applications in security, fraud detection, and information management.
Keywords:
social network analysis, community detection, anomaly detection, deviation-based model, attributed graphsDownloads
References
S. Fortunato and D. Hric, "Community detection in networks: A user guide," Physics Reports, vol. 659, pp. 1–44, Nov. 2016. DOI: https://doi.org/10.1016/j.physrep.2016.09.002
L. Akoglu, H. Tong, and D. Koutra, "Graph based anomaly detection and description: a survey," Data Mining and Knowledge Discovery, vol. 29, no. 3, pp. 626–688, May 2015. DOI: https://doi.org/10.1007/s10618-014-0365-y
X. Ma et al., "A Comprehensive Survey on Graph Anomaly Detection With Deep Learning," IEEE Transactions on Knowledge and Data Engineering, vol. 35, no. 12, pp. 12012–12038, Dec. 2023. DOI: https://doi.org/10.1109/TKDE.2021.3118815
M. E. J. Newman, "Modularity and community structure in networks," Proceedings of the National Academy of Sciences, vol. 103, no. 23, pp. 8577–8582, June 2006. DOI: https://doi.org/10.1073/pnas.0601602103
U. von Luxburg, "A tutorial on spectral clustering," Statistics and Computing, vol. 17, no. 4, pp. 395–416, Dec. 2007. DOI: https://doi.org/10.1007/s11222-007-9033-z
M. Rosvall and C. T. Bergstrom, "Maps of random walks on complex networks reveal community structure," Proceedings of the National Academy of Sciences, vol. 105, no. 4, pp. 1118–1123, Jan. 2008. DOI: https://doi.org/10.1073/pnas.0706851105
H. Safdari and C. De Bacco, "Community detection and anomaly prediction in dynamic networks," Communications Physics, vol. 7, no. 1, Dec. 2024, Art. no. 397. DOI: https://doi.org/10.1038/s42005-024-01889-y
F. Tang, J. Li, X. Liu, C. Chang, and L. Teng, "GATFELPA integrates graph attention networks and enhanced label propagation for robust community detection," Scientific Reports, vol. 15, no. 1, Jan. 2025, Art. no. 3952. DOI: https://doi.org/10.1038/s41598-024-84962-4
B. Perozzi and L. Akoglu, "Discovering Communities and Anomalies in Attributed Graphs: Interactive Visual Exploration and Summarization," ACM Transactions on Knowledge Discovery from Data, vol. 12, no. 2, Jan. 2018, Art. no. 24. DOI: https://doi.org/10.1145/3139241
B. Perozzi, L. Akoglu, P. Iglesias Sánchez, and E. Müller, "Focused clustering and outlier detection in large attributed graphs," in Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, New York, NY, USA, 2014, pp. 1346–1355. DOI: https://doi.org/10.1145/2623330.2623682
Z. Wu, S. Pan, F. Chen, G. Long, C. Zhang, and P. S. Yu, "A Comprehensive Survey on Graph Neural Networks," IEEE Transactions on Neural Networks and Learning Systems, vol. 32, no. 1, pp. 4–24, Jan. 2021. DOI: https://doi.org/10.1109/TNNLS.2020.2978386
J. He, Q. Xu, Y. Jiang, Z. Wang, and Q. Huang, "ADA-GAD: Anomaly-Denoised Autoencoders for Graph Anomaly Detection," Proceedings of the AAAI Conference on Artificial Intelligence, vol. 38, no. 8, pp. 8481–8489, Mar. 2024. DOI: https://doi.org/10.1609/aaai.v38i8.28691
A. Roy et al., "GAD-NR: Graph Anomaly Detection via Neighborhood Reconstruction," in Proceedings of the 17th ACM International Conference on Web Search and Data Mining, Merida, Mexico, 2024, pp. 576–585. DOI: https://doi.org/10.1145/3616855.3635767
A. Chen, J. Wu, and H. Zhang, "FIAD: Graph anomaly detection framework based feature injection," Expert Systems with Applications, vol. 259, Jan. 2025, Art. no. 125216. DOI: https://doi.org/10.1016/j.eswa.2024.125216
M. I. H. Okfie and S. Mishra, "Anomaly Detection in IIoT Transactions using Machine Learning: A Lightweight Blockchain-based Approach," Engineering, Technology & Applied Science Research, vol. 14, no. 3, pp. 14645–14653, June 2024. DOI: https://doi.org/10.48084/etasr.7384
A. Bojchevski and S. Günnemann, "Bayesian Robust Attributed Graph Clustering: Joint Learning of Partial Anomalies and Group Structure," Proceedings of the AAAI Conference on Artificial Intelligence, vol. 32, no. 1, pp. 2738–2745, Apr. 2018. DOI: https://doi.org/10.1609/aaai.v32i1.11642
A. Sankar, Y. Wu, L. Gou, W. Zhang, and H. Yang, "DySAT: Deep Neural Representation Learning on Dynamic Graphs via Self-Attention Networks," in Proceedings of the 13th International Conference on Web Search and Data Mining, Houston, TX, USA, 2020, pp. 519–527. DOI: https://doi.org/10.1145/3336191.3371845
Y. Liu et al., "Anomaly Detection in Dynamic Graphs via Transformer," IEEE Transactions on Knowledge and Data Engineering, vol. 35, no. 12, pp. 12081–12094, Dec. 2023. DOI: https://doi.org/10.1109/TKDE.2021.3124061
S. Guan, B. Zhao, Z. Dong, M. Gao, and Z. He, "GTAD: Graph and Temporal Neural Network for Multivariate Time Series Anomaly Detection," Entropy, vol. 24, no. 6, June 2022, Art. no. 759. DOI: https://doi.org/10.3390/e24060759
A. K. McCallum, K. Nigam, J. Rennie, and K. Seymore, "Automating the Construction of Internet Portals with Machine Learning," Information Retrieval, vol. 3, no. 2, pp. 127–163, July 2000. DOI: https://doi.org/10.1023/A:1009953814988
P. Sen, G. Namata, M. Bilgic, L. Getoor, B. Galligher, and T. Eliassi-Rad, "Collective Classification in Network Data," AI Magazine, vol. 29, no. 3, pp. 93–93, Sept. 2008. DOI: https://doi.org/10.1609/aimag.v29i3.2157
G. Namata, B. London, L. Getoor, and B. Huang, "Query-driven Active Surveying for Collective Classification," in Proceedings of the Workshop on Mining and Learning with Graphs, Edinburgh, UK, 2012.
W. Hamilton, Z. Ying, and J. Leskovec, "Inductive Representation Learning on Large Graphs," in 31st Conference on Neural Information Processing Systems, Long Beach, CA, USA, 2017, pp. 1024–1034.
A. Grover and J. Leskovec, "node2vec: Scalable Feature Learning for Networks," in Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco, CA, USA, 2016, pp. 855–864. DOI: https://doi.org/10.1145/2939672.2939754
T. N. Kipf and M. Welling, "Semi-Supervised Classification with Graph Convolutional Networks," in Proceedings of the 5th International Conference on Learning Representations, Toulon, France, 2017, pp. 1–14.
Downloads
How to Cite
License
Copyright (c) 2025 Hedia Zardi, Sarah Alharbi
This work is licensed under a Creative Commons Attribution 4.0 International License.
Authors who publish with this journal agree to the following terms:
- Authors retain the copyright and grant the journal the right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) after its publication in ETASR with an acknowledgement of its initial publication in this journal.
