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

Volume

2

fYear

2003

fDate

14-17 Dec. 2003

Firstpage

1670

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;

fLanguage

English

Publisher

ieee

Conference_Titel

Neural Networks and Signal Processing, 2003. Proceedings of the 2003 International Conference on

Conference_Location

Nanjing

Print_ISBN

0-7803-7702-8

Type

conf

DOI

10.1109/ICNNSP.2003.1281204

Filename

1281204