Finding the most vital node with respect to the number of spanning trees
Yong Chen, Aiqun Hu, Kun-Wah Yip, Jun Hu, Zi-Guo Zhong · 2003
An evaluation method for finding the most vital node with respect to the number of spanning trees in communication networks is proposed. For a given node v in the graph G, G-v is the graph with the node deleted, where the edge denotes a link and the vertex denotes a node respectively. The relative importance of two nodes in the graph can be compared with each other with respect to the number of spanning trees. The most vital node in G is a node whose removal with its incident links most impacts system reliability. Moreover, the concise generalized expression is given. Experimental results show that the method can identify the most vital node in a network efficiently.