Holevo Quantity - Vertex Centrality


This method measures vertex centrality based on the quantum information theoretical concept of Holevo quantity. More specifically, it measures the importance of a vertex in terms of the variation in graph entropy before and after its removal from the graph

HC(v)=x(\{({|E_{\bar v}|\over |E|}, {G_{\bar v})},({|E_{\bar v}|\over |E|},G_v)\})\\
=S(p(G))-({|E_{\bar v}|\over |E|} S(p(G_{\bar v}))+{|E_{v}|\over |E|} S(p(G_{v})))

were $G_v = (V,E_v)$ denote the subgraph with vertex set $V$ and edge set $E_v$ and $G_{\bar v}=V,E_{\bar v}$ is the subgraph with vertex set $V$ and edge set $E_v$. And $S(p(G_{v})$ is the entropy of $ρ(G_v)$.

Considering this method centrality of a vertex $v$ can be broken down in two parts, one which is negatively correlated with the degree centrality of $v$, and one which depends on the emergence of non-trivial structures in the graph when $v$ is disconnected from the rest of the graph


  • Rossi L., Torsello A., 2017. Measuring vertex centrality using the Holevo quantity. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 10310 LNCS, pp.154-164. DOI: 10.1007/978-3-319-58961-9_14 Publisher web site


There are no comment yet.

Add your comment

Sum of    and  

The rendering mode: