Dynamical Spanning Tree (DST) centrality is a node importance measure that identifies the most critical nodes in a network based on their impact on the network's structural reliability [2, 3]. Specifically, the node whose removal results in the largest reduction in the number of spanning trees is considered the most vital. The relative importance of nodes can thus be quantified according to the decrease in the total number of spanning trees after their removal.
The DST centrality of a node \(i\) is defined as
\begin{equation*}
c_{\mathrm{DST}}(i) = 1 - \frac{t_{G_i}}{t_G},
\end{equation*}
where \(t_G\) is the total number of spanning trees in the original graph \(G\), and \(t_{G_i}\) is the number of spanning trees in the subgraph \(G_i\) obtained by removing node \(i\) from \(G\). The total number of spanning trees can be computed using Kirchhoff’s Matrix-Tree Theorem:
\begin{equation*}
t_G = \frac{1}{N} \prod_{k=2}^{N} λ_k,
\end{equation*}
where \(0 = λ_1 < λ_2 \leq \dots \leq λ_N\) are the eigenvalues of the Laplacian matrix \(L\) of the graph \(G\), and \(N\) is the number of nodes. For undirected networks, the Laplacian matrix is symmetric, and all eigenvalues are real and non-negative.
A higher value of \(c_{\mathrm{DST}}(i)\) indicates that node \(i\) plays a more significant role in maintaining the network’s structural connectivity.

References

[1] Shvydun, S. (2025). Zoo of Centralities: Encyclopedia of Node Metrics in Complex Networks. arXiv: 2511.05122 https://doi.org/10.48550/arXiv.2511.05122
[2] Chen, Y., Hu, A. Q., Yip, K. W., Hu, J., & Zhong, Z. G. (2003). Finding the most vital node with respect to the number of spanning trees. In International Conference on Neural Networks and Signal Processing, 2003. Proceedings of the 2003 (Vol. 2, pp. 1670-1673). IEEE. doi: 10.1109/ICNNSP.2003.1281204.
[3] Lü, L., Chen, D., Ren, X. L., Zhang, Q. M., Zhang, Y. C., & Zhou, T. (2016). Vital nodes identification in complex networks. Physics reports, 650, 1-63. doi: 10.1016/j.physrep.2016.06.007.