Perturbation Analysis of Centrality Measures

Abstract

In recent decades, a large number of centrality measures have been proposed to assess the importance of nodes in complex networks. The choice of the most appropriate centrality index for specific applications is one of the biggest challenges. This paper performs the perturbation analysis of 8 centrality measures. Since most real networks are incomplete and prone to bias, we compare centrality measures in order to evaluate their sensitivity to small changes in a graph structure. Our experiments are performed on 8 classical graph structures ranging from a simple path graph to a Watts-Strogatz graph model. As a result, we provide a sensitivity of centrality measures on different graph structures.