Holevo Quantity - Vertex Centrality
Definition
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
$$\begin{align*}
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})))
\end{align*}$$
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
$$\begin{align*}
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})))
\end{align*}$$
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
References
- 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