Enhanced Critical Node Detection in Social Networks

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.