A centrality notion for graphs based on Tukey depth

Jorge Orestes Cerdeira; Pedro C. Silva

doi:10.1016/j.amc.2021.126409

A centrality notion for graphs based on Tukey depth

Research output: Contribution to journal › Article › peer-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 language	English
Article number	126409
Journal	Applied Mathematics and Computation
Volume	409
DOIs	https://doi.org/10.1016/j.amc.2021.126409
Publication status	Published - 15 Nov 2021

Keywords

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

Access to Document

10.1016/j.amc.2021.126409

Cite this

@article{cb064b65eddc4c28913020de8d661cfd,

title = "A centrality notion for graphs based on Tukey depth",

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.",

keywords = "Centrality measures, Computational complexity, Convexity, Median points, Quasi-concave function, Social networks, Unimodal distribution",

author = "Cerdeira, {Jorge Orestes} and Silva, {Pedro C.}",

note = "Funding Information: This research was funded by NOVA MATH and by the Forest Research Centre, research units funded by the Funda{\c c}{\~a}o para a Ci{\^e}ncia e a Tecnologia, I.P. (FCT), Portugal (UIDB/00297/2020 (NOVA MATH) and UIDB/00239/2020 (CEF)). ",

year = "2021",

month = nov,

day = "15",

doi = "10.1016/j.amc.2021.126409",

language = "English",

volume = "409",

journal = "Applied Mathematics and Computation",

issn = "0096-3003",

publisher = "Elsevier",

}

TY - JOUR

T1 - A centrality notion for graphs based on Tukey depth

AU - Cerdeira, Jorge Orestes

AU - Silva, Pedro C.

N1 - Funding Information: This research was funded by NOVA MATH and by the Forest Research Centre, research units funded by the Fundação para a Ciência e a Tecnologia, I.P. (FCT), Portugal (UIDB/00297/2020 (NOVA MATH) and UIDB/00239/2020 (CEF)).

PY - 2021/11/15

Y1 - 2021/11/15

N2 - 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.

AB - 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.

KW - Centrality measures

KW - Computational complexity

KW - Convexity

KW - Median points

KW - Quasi-concave function

KW - Social networks

KW - Unimodal distribution

UR - http://www.scopus.com/inward/record.url?scp=85108693261&partnerID=8YFLogxK

U2 - 10.1016/j.amc.2021.126409

DO - 10.1016/j.amc.2021.126409

M3 - Article

AN - SCOPUS:85108693261

VL - 409

JO - Applied Mathematics and Computation

JF - Applied Mathematics and Computation

SN - 0096-3003

M1 - 126409

ER -

A centrality notion for graphs based on Tukey depth

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this