Holevo Quantity - Edge Centrality


This method is a novel edge centrality measure based on the quantum information theoretical concept of Holevo quantity. This is a measure of the difference in Von Neumann entropy between the original graph and the graph where $e$ has been removed. In other words, it can be seen as a measure of the contribution of $e$ to the Von Neumann entropy of $G$

For a graph $G = (V,E)$, the Holevo edge centrality of $e \in E$ is:

$$HC(c)=x (\{ ( {m-1\over m} ,H_{\bar e}),({1\over m} , H_e)\})$$

were $m=|E|$, $H_{\bar e}$ and $H_e$ are the subgraphs over edge sets $\{e\}$ and $E \{e\}$, respectively. $(m− 1)/m$ is constant for all the edges and thus can be safely ignored.


  • Lockhart J., Minello G., Rossi L., Severini S., Torsello A., 2016. Edge centrality via the Holevo quantity. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 10029 LNCS, pp.143-152. DOI: 10.1007/978-3-319-49055-7_13 Publisher web site


There are no comment yet.

Add your comment

Sum of    and  

The rendering mode: