Finding the Most Vital Node by Node Contraction in Communication Networks

摘要

In an undirected graph G = (V, E), let G*v_i denote the graph obtained from contracting v_i, viz.v_i and nodes jointed with v_i are replaced by a new node. In this paper, the networks agglomeration is defined firstly. A method of evaluating nodes importance by node contraction in communication networks is proposed based on networks agglomeration. The most vital node is the one whose contraction results in the largest increase of the networks agglomeration. Both degree and position of node are considered with this method. The node contribution is evaluated directly and the result is consistent with our intuitive judgments. Final examples verify its efficiency.