Edge centrality via the Holevo quantity

Joshua Lockhart, Giorgia Minello, Luca Rossi*, Simone Severini, Andrea Torsello

*Corresponding author for this work

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

Abstract

In the study of complex networks, vertex centrality measures are used to identify the most important vertices within a graph. A related problem is that of measuring the centrality of an edge. In this paper, we propose a novel edge centrality index rooted in quantum information. More specifically, we measure the importance of an edge in terms of the contribution that it gives to the Von Neumann entropy of the graph. We show that this can be computed in terms of the Holevo quantity, a well known quantum information theoretical measure. While computing the Von Neumann entropy and hence the Holevo quantity requires computing the spectrum of the graph Laplacian, we show how to obtain a simplified measure through a quadratic approximation of the Shannon entropy. This in turns shows that the proposed centrality measure is strongly correlated with the negative degree centrality on the line graph. We evaluate our centrality measure through an extensive set of experiments on real-world as well as synthetic networks, and we compare it against commonly used alternative measures.
Original languageEnglish
Title of host publicationStructural, syntactic, and statistical pattern recognition
Subtitle of host publicationJoint IAPR International Workshop, S+SSPR 2016, Mérida, Mexico, November 29 - December 2, 2016, Proceedings
EditorsAntonio Robles-Kelly, Marco Loog, Battista Biggio, et al
Place of PublicationCham (CH)
PublisherSpringer
Pages143-152
Number of pages10
ISBN (Electronic)978-3-319-49055-7
ISBN (Print)978-3-319-49054-0
DOIs
Publication statusE-pub ahead of print - 5 Nov 2016
EventJoint IAPR International Workshops on Structural and Syntactic Pattern Recognition and Statistical Techniques in Pattern Recognition - Mérida, Mexico
Duration: 30 Nov 20162 Dec 2016

Publication series

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

Workshop

WorkshopJoint IAPR International Workshops on Structural and Syntactic Pattern Recognition and Statistical Techniques in Pattern Recognition
Abbreviated titleS-SSSPR 2016
CountryMexico
CityMérida
Period30/11/162/12/16

Bibliographical note

Funding: Royal Society and EPSRC

Keywords

  • edge centrality
  • complex networks
  • holevo quantity
  • quantum information

Fingerprint Dive into the research topics of 'Edge centrality via the Holevo quantity'. Together they form a unique fingerprint.

  • Research Output

    • 1 Conference contribution

    The average mixing matrix signature

    Rossi, L., Severini, S. & Torsello, A., 5 Nov 2016, Structural, syntactic, and statistical pattern recognition: Joint IAPR International Workshop, S+SSPR 2016, Mérida, Mexico, November 29 - December 2, 2016, Proceedings. Robles-Kelly, A., Loog, M., Baggio, B. & et al (eds.). Cham (CH): Springer, p. 474-484 11 p. (Image Processing, Computer Vision, Pattern Recognition, and Graphics (Lecture Notes in Computer Science); vol. 10029).

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

    Open Access
    File
  • Cite this

    Lockhart, J., Minello, G., Rossi, L., Severini, S., & Torsello, A. (2016). Edge centrality via the Holevo quantity. In A. Robles-Kelly, M. Loog, B. Biggio, & et al (Eds.), Structural, syntactic, and statistical pattern recognition: Joint IAPR International Workshop, S+SSPR 2016, Mérida, Mexico, November 29 - December 2, 2016, Proceedings (pp. 143-152). (Lecture Notes in Computer Science; Vol. 10029). Springer. https://doi.org/10.1007/978-3-319-49055-7_13