Edge centrality via the Holevo quantity

Lockhart, Joshua, Minello, Giorgia, Rossi, Luca, Severini, Simone and Torsello, Andrea (2016). Edge centrality via the Holevo quantity. IN: Structural, syntactic, and statistical pattern recognition. Robles-Kelly, Antonio; Loog, Marco; Biggio, Battista and et al (eds) Lecture Notes in Computer Science . MEX: Springer.


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.

Publication DOI: https://doi.org/10.1007/978-3-319-49055-7_13
Divisions: Engineering & Applied Sciences
Engineering & Applied Sciences > Systems analytics research institute (SARI)
Additional Information: Funding: Royal Society and EPSRC
Event Title: Joint IAPR International Workshops on Structural and Syntactic Pattern Recognition and Statistical Techniques in Pattern Recognition
Event Type: Other
Event Dates: 2016-11-30 - 2016-12-02
Uncontrolled Keywords: edge centrality,complex networks,holevo quantity,quantum information,Theoretical Computer Science,Computer Science(all)
Full Text Link: http://link.spr ... -319-49055-7_13
Related URLs: http://www.scop ... tnerID=8YFLogxK (Scopus URL)
Published Date: 2016
Published Online Date: 2016-11-05
Authors: Lockhart, Joshua
Minello, Giorgia
Rossi, Luca ( 0000-0002-6116-9761)
Severini, Simone
Torsello, Andrea



Version: Accepted Version

Export / Share Citation


Additional statistics for this record