An Experimental Evaluation of Multi-objective Evolutionary Algorithms for Detecting Critical Nodes in Complex Networks

Identifying critical nodes in complex networks has become an important task across a variety of application domains. In this paper we propose a multi-objective version of the critical node detection problem, which aims to minimize pairwise connectivity in a graph by removing a subset of K nodes. Interestingly, while it has been recognized that this problem is inherently multi-objective since it was formulated, until now only single-objective algorithms have been proposed. After explicitly stating the new multi-objective problem variant, we then give a brief comparison of six common multi-objective evolutionary algorithms using sixteen common benchmark problem instances. A comparison of the results attained by viewing the algorithm as a single versus multi-objective problem is also conducted. We find that of the examined algorithms, NSGAII generally produces the most desirable approximation fronts. We also demonstrate that while related, the best multi-objective solutions do not translate into the best single-objective solutions.