A centrality notion for graphs based on Tukey depth

Jorge Orestes Cerdeira, Pedro C. Silva

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish
Article number126409
JournalApplied Mathematics and Computation
Volume409
DOIs
Publication statusPublished - 15 Nov 2021

Keywords

  • Centrality measures
  • Computational complexity
  • Convexity
  • Median points
  • Quasi-concave function
  • Social networks
  • Unimodal distribution

Fingerprint

Dive into the research topics of 'A centrality notion for graphs based on Tukey depth'. Together they form a unique fingerprint.

Cite this