Title :
Finding the most vital node with respect to the number of spanning trees
Author :
Chen, Yong ; Hu, Ai-qun ; Kun-Wah Yip ; Hu, Jun ; Zhong, Zi-guo
Author_Institution :
Dept. of Radio Eng., Southeast Univ., Nanjing, China
Abstract :
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.
Keywords :
directed graphs; telecommunication network reliability; trees (mathematics); communication networks; evaluation method; graph edge; graph vertex; spanning trees; system reliability; vital node; Communication networks; Educational programs; Genetic expression; Research and development; Telecommunication network reliability; Topology; Tree graphs;
Conference_Titel :
Neural Networks and Signal Processing, 2003. Proceedings of the 2003 International Conference on
Conference_Location :
Nanjing
Print_ISBN :
0-7803-7702-8
DOI :
10.1109/ICNNSP.2003.1281204
