A centrality notion for graphs based on Tukey depth

Centrality on graphs aims at ranking vertices in terms of their contribution to facilitate the communication flow in the network. Tukey depth is one of most widely used statistical measures to assess the centrality of a point within a cloud of points in the multidimensional space. In this paper we propose and discuss how to adapt Tukey depth to develop a novel centrality index for vertices of a graph. We present some properties of the indices on several classes of graphs, show that computing the indices is NP-hard, extend the indices to assess the centrality of group of vertices and give 0/1 linear formulations to calculate them. (C) 2021 Elsevier Inc. All rights reserved.

Automated summary

This paper discusses the adaptation of Tukey depth to create a novel centrality index for vertices of a graph, showcasing some properties and the computational complexity of the indices. The research also extends these indices to assess the centrality of group of vertices and provides 0/1 linear formulations for calculation.