Centrality in complex networks under incomplete data

The concept of centrality is one of the essential tools for analyzing complex systems. Over the years, a large number of centrality indices have been proposed that account for different aspects of a network. Unfortunately, most real networks are substantially incomplete, which affects the results of the centrality measures. This article aims to evaluate the sensitivity of 16 centrality measures to the presence of errors or incomplete information about the structure of a complex network. Our experiments are performed across 113 empirical networks. As a result, we identify centrality indices that are highly vulnerable to incomplete data.Author summary: The robustness of centrality measures is a fundamental problem for the correct identification of important nodes in many real networks, which are partially observed in most cases. Existing studies do not fully address this issue because they are usually limited to a small number of both centrality measures and graphs, while the graph perturbations are performed at random. Our work investigates the robustness of 16 centrality measures by analyzing the variation in the relative ranking of nodes under a set of appropriately defined network perturbations. To draw meaningful and robust conclusions about the average sensitivity of a specific centrality measure, we perform our experiments on a large set of networks. Our findings demonstrate that certain centrality measures may be misinterpreted or misapplied when used on specific classes of networks, while the results of these measures require a cautious interpretation in the presence of missing or incorrect data.