Abstract
In this paper, we investigate the popular centrality-based approaches to find a set of critical nodes whose deletion causes the most disconnectivity in the network. Demonstrating the weak points of these approaches which only consider a ranking factor, we propose an Enhanced Critical Node Detection (ECND) method which can work with any kind of ranking score by considering the structure of a network. We have designed a set of experiments using 24 different artificial and real-world networks, varying in the number of vertices and number of edges. Using two different objective functions including the number of connected components and the weighted average size of the connected components, experimental results show outperformance of ECND in comparison to all 8 other methods.
Keywords
MSC
91D30, 91C20, 62H30
Cite this article
@article{cai-5219,
author = {Leila Ajam and Seyed Naghi Seyedaghaee},
title = {Enhanced Critical Node Detection in Social Networks},
journal = {Computing and Informatics},
volume = {40},
number = {6},
pages = {1422--1443},
year = {2021},
issn = {1335-9150},
doi = {10.31577/cai_2021_6_1422}
}
TY - JOUR AU - Leila Ajam AU - Seyed Naghi Seyedaghaee TI - Enhanced Critical Node Detection in Social Networks JO - Computing and Informatics VL - 40 IS - 6 SP - 1422 EP - 1443 PY - 2021 SN - 1335-9150 DO - 10.31577/cai_2021_6_1422 UR - https://doi.org/10.31577/cai_2021_6_1422 KW - Social network analysis KW - critical node detection KW - disconnectivity KW - centrality KW - social networks ER -
Ajam, L., & Seyedaghaee, S. N. (2021). Enhanced Critical Node Detection in Social Networks. Computing and Informatics, 40(6), 1422–1443. https://doi.org/10.31577/cai_2021_6_1422