Measuring vertex centrality using the Holevo quantity

Luca Rossi*, Andrea Torsello

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

In recent years, the increasing availability of data describing the dynamics of real-world systems led to a surge of interest in the complex networks of interactions that emerge from such systems. Several measures have been introduced to analyse these networks, and among them one of the most fundamental ones is vertex centrality, which quantifies the importance of a vertex within a graph. In this paper, we propose a novel vertex centrality measure based on the quantum information theoretical concept of Holevo quantity. More specifically, we measure the importance of a vertex in terms of the variation in graph entropy before and after its removal from the graph. More specifically, we find that the centrality of a vertex v can be broken down in two parts: (1) one which is negatively correlated with the degree centrality of v, and (2) one which depends on the emergence of non-trivial structures in the graph when v is disconnected from the rest of the graph. Finally, we evaluate our centrality measure on a number of real-world as well as synthetic networks, and we compare it against a set of commonly used alternative measures.

Original languageEnglish
Title of host publicationGraph-based representations in pattern recognition : 11th IAPR-TC-15 international workshop, GbRPR 2017. Proceedings
EditorsPasquale Foggia, Cheng-Lin Liu, Mario Vento
Place of PublicationCham (CH)
PublisherSpringer
Pages154-164
Number of pages11
ISBN (Electronic)978-3-319-58961-9
ISBN (Print)978-3-319-58960-2
DOIs
Publication statusPublished - 2017
Event11th IAPR-TC-15 International Workshop on Graph-Based Representations in Pattern Recognition, GbRPR 2017 - Anacapri, Italy
Duration: 16 May 201718 May 2017

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume10310
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference11th IAPR-TC-15 International Workshop on Graph-Based Representations in Pattern Recognition, GbRPR 2017
CountryItaly
CityAnacapri
Period16/05/1718/05/17

Fingerprint

Centrality
Complex networks
Entropy
Availability
Graph in graph theory
Vertex of a graph
Quantum Information
Surge
Complex Networks
Quantify
Evaluate
Alternatives
Interaction

Keywords

  • complex networks
  • quantum Information
  • vertex centrality

Cite this

Rossi, L., & Torsello, A. (2017). Measuring vertex centrality using the Holevo quantity. In P. Foggia, C-L. Liu, & M. Vento (Eds.), Graph-based representations in pattern recognition : 11th IAPR-TC-15 international workshop, GbRPR 2017. Proceedings (pp. 154-164). (Lecture Notes in Computer Science; Vol. 10310). Cham (CH): Springer. https://doi.org/10.1007/978-3-319-58961-9_14
Rossi, Luca ; Torsello, Andrea. / Measuring vertex centrality using the Holevo quantity. Graph-based representations in pattern recognition : 11th IAPR-TC-15 international workshop, GbRPR 2017. Proceedings. editor / Pasquale Foggia ; Cheng-Lin Liu ; Mario Vento. Cham (CH) : Springer, 2017. pp. 154-164 (Lecture Notes in Computer Science).
@inproceedings{032c2d0e0dd04c89b0517f801f0ae1f2,
title = "Measuring vertex centrality using the Holevo quantity",
abstract = "In recent years, the increasing availability of data describing the dynamics of real-world systems led to a surge of interest in the complex networks of interactions that emerge from such systems. Several measures have been introduced to analyse these networks, and among them one of the most fundamental ones is vertex centrality, which quantifies the importance of a vertex within a graph. In this paper, we propose a novel vertex centrality measure based on the quantum information theoretical concept of Holevo quantity. More specifically, we measure the importance of a vertex in terms of the variation in graph entropy before and after its removal from the graph. More specifically, we find that the centrality of a vertex v can be broken down in two parts: (1) one which is negatively correlated with the degree centrality of v, and (2) one which depends on the emergence of non-trivial structures in the graph when v is disconnected from the rest of the graph. Finally, we evaluate our centrality measure on a number of real-world as well as synthetic networks, and we compare it against a set of commonly used alternative measures.",
keywords = "complex networks, quantum Information, vertex centrality",
author = "Luca Rossi and Andrea Torsello",
year = "2017",
doi = "10.1007/978-3-319-58961-9_14",
language = "English",
isbn = "978-3-319-58960-2",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "154--164",
editor = "Pasquale Foggia and Cheng-Lin Liu and Mario Vento",
booktitle = "Graph-based representations in pattern recognition : 11th IAPR-TC-15 international workshop, GbRPR 2017. Proceedings",
address = "Germany",

}

Rossi, L & Torsello, A 2017, Measuring vertex centrality using the Holevo quantity. in P Foggia, C-L Liu & M Vento (eds), Graph-based representations in pattern recognition : 11th IAPR-TC-15 international workshop, GbRPR 2017. Proceedings. Lecture Notes in Computer Science, vol. 10310, Springer, Cham (CH), pp. 154-164, 11th IAPR-TC-15 International Workshop on Graph-Based Representations in Pattern Recognition, GbRPR 2017 , Anacapri, Italy, 16/05/17. https://doi.org/10.1007/978-3-319-58961-9_14

Measuring vertex centrality using the Holevo quantity. / Rossi, Luca; Torsello, Andrea.

Graph-based representations in pattern recognition : 11th IAPR-TC-15 international workshop, GbRPR 2017. Proceedings. ed. / Pasquale Foggia; Cheng-Lin Liu; Mario Vento. Cham (CH) : Springer, 2017. p. 154-164 (Lecture Notes in Computer Science; Vol. 10310).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - Measuring vertex centrality using the Holevo quantity

AU - Rossi, Luca

AU - Torsello, Andrea

PY - 2017

Y1 - 2017

N2 - In recent years, the increasing availability of data describing the dynamics of real-world systems led to a surge of interest in the complex networks of interactions that emerge from such systems. Several measures have been introduced to analyse these networks, and among them one of the most fundamental ones is vertex centrality, which quantifies the importance of a vertex within a graph. In this paper, we propose a novel vertex centrality measure based on the quantum information theoretical concept of Holevo quantity. More specifically, we measure the importance of a vertex in terms of the variation in graph entropy before and after its removal from the graph. More specifically, we find that the centrality of a vertex v can be broken down in two parts: (1) one which is negatively correlated with the degree centrality of v, and (2) one which depends on the emergence of non-trivial structures in the graph when v is disconnected from the rest of the graph. Finally, we evaluate our centrality measure on a number of real-world as well as synthetic networks, and we compare it against a set of commonly used alternative measures.

AB - In recent years, the increasing availability of data describing the dynamics of real-world systems led to a surge of interest in the complex networks of interactions that emerge from such systems. Several measures have been introduced to analyse these networks, and among them one of the most fundamental ones is vertex centrality, which quantifies the importance of a vertex within a graph. In this paper, we propose a novel vertex centrality measure based on the quantum information theoretical concept of Holevo quantity. More specifically, we measure the importance of a vertex in terms of the variation in graph entropy before and after its removal from the graph. More specifically, we find that the centrality of a vertex v can be broken down in two parts: (1) one which is negatively correlated with the degree centrality of v, and (2) one which depends on the emergence of non-trivial structures in the graph when v is disconnected from the rest of the graph. Finally, we evaluate our centrality measure on a number of real-world as well as synthetic networks, and we compare it against a set of commonly used alternative measures.

KW - complex networks

KW - quantum Information

KW - vertex centrality

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

UR - https://link.springer.com/chapter/10.1007%2F978-3-319-58961-9_14

U2 - 10.1007/978-3-319-58961-9_14

DO - 10.1007/978-3-319-58961-9_14

M3 - Conference contribution

AN - SCOPUS:85019596244

SN - 978-3-319-58960-2

T3 - Lecture Notes in Computer Science

SP - 154

EP - 164

BT - Graph-based representations in pattern recognition : 11th IAPR-TC-15 international workshop, GbRPR 2017. Proceedings

A2 - Foggia, Pasquale

A2 - Liu, Cheng-Lin

A2 - Vento, Mario

PB - Springer

CY - Cham (CH)

ER -

Rossi L, Torsello A. Measuring vertex centrality using the Holevo quantity. In Foggia P, Liu C-L, Vento M, editors, Graph-based representations in pattern recognition : 11th IAPR-TC-15 international workshop, GbRPR 2017. Proceedings. Cham (CH): Springer. 2017. p. 154-164. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-319-58961-9_14