STC - Spanning Tree Centrality
Definition
A new centrality measurement,called spanning tree centrality ($STC$ for short),is introduced for weighted networks. The $STC$ score of avertex $v$ in $G$ is defined as the number of spanning trees with the vertex $v$ as a cut vertex. It will takes all the spanning trees of a network into consideration. As we know,for a vertex v in a tree,it acts either as a leaf (whose removal does not damage the connectivity of the tree) or as a cut vertex (whose removal disconnects the tree). For this new centrality method if a vertex $v$ is central in the whole network,the likelihood that it acts as cut vertices in spanning trees are high.So the importance of a vertex $v$ can be reflected by the number of spanning trees of $G$ with $v$ as a cut vertex. So $STC$ is defined by the following relation:
Let $G=(V,E,w)$ be a weighted network,the spanning tree centrality of one vertex $v$ is defined as:
$$C^{sp}(V)=Kir(G)- d_v . Kir(G-v)$$
where the Kirchhoff polynomial of $G$, denoted by $Kir(G)$, and $Kir(G)$ calculates as follows:
$$Kir(G)={\underset{T\in \Im (G)}{\sum}} \chi T =|det (\bar l_i(G))|$$
for any $i$ (independent of the choice of $i$), where $\bar l_i(G))$ is the $i$th reduced Laplacian matrix of $G$. $T$ is a spanning tree with weight $W_e$ for each edge and, $\chi T$ is the weight of $T$. Also, $d$ is the sum weight of a vertex $v$.
This new centrality methode valuates the importance of a vertex from very different structural aspects. It considers the effect on the rest of the graph with the removal of a given node, and gets the system-contribution of a particular node.
Let $G=(V,E,w)$ be a weighted network,the spanning tree centrality of one vertex $v$ is defined as:
$$C^{sp}(V)=Kir(G)- d_v . Kir(G-v)$$
where the Kirchhoff polynomial of $G$, denoted by $Kir(G)$, and $Kir(G)$ calculates as follows:
$$Kir(G)={\underset{T\in \Im (G)}{\sum}} \chi T =|det (\bar l_i(G))|$$
for any $i$ (independent of the choice of $i$), where $\bar l_i(G))$ is the $i$th reduced Laplacian matrix of $G$. $T$ is a spanning tree with weight $W_e$ for each edge and, $\chi T$ is the weight of $T$. Also, $d$ is the sum weight of a vertex $v$.
This new centrality methode valuates the importance of a vertex from very different structural aspects. It considers the effect on the rest of the graph with the removal of a given node, and gets the system-contribution of a particular node.
References
- Qi X., Fuller E., Luo R., Zhang C.Q., 2015. A novel centrality method for weighted networks based on the Kirchhoff polynomial. Pattern Recognition Letters, 58, pp.51-60.
DOI: 10.1016/j.patrec.2015.02.007
