Node importance based on the weighted K -order propagation number algorithm

The measurement of node importance is significant for analyzing a network structure. To comprehensively reflect the global and local network features, in this paper we abstract the propagating process of epidemic diseases based on the network topology structure, and then respectively sets each node as an infection source. After a certain dissemination time K, the number of infected nodes in the network is defined as the K-order propagation number, and the weighted sum of K-order propagation numbers under different values of K is taken as the important index of nodes. The simulation experiments of Watts-Strogatz small-world networks and a dolphin network show that the weighted K-order propagation number algorithm is more effective than the traditional method in evaluating the importance of nodes. For the Watts-Strogatz small-world networks, it can reflect the influence of long-distance connections on information transmission in detail. For the dolphin network, the weighted K-order propagation number algorithm significantly raises the profile of those nodes which play a key role in the information communication between different dolphin communities. In addition, in this paper we use a deliberate attacking method to analyze the western power grid of the United States, the road transportation network of the Chicago region, the co-authorship network in network science and the axonal tracts’ network between neurons of mouse. According to the specific order of the node importance from high to low, network nodes are attacked in turn, that is, all edges of the attacked nodes are removed. The analysis results of network parameters such as the network efficiency and the node number of the maximum sub-graph changing with the attacking times show that comparing with other evaluation indices of node importance such as degree, Ren method, Chen method, eigenvector method, Katz index, PageRank, CI method and K-shell, the weighted K-order propagation number algorithm focuses much on destroying the major structure, and all of the above four networks will break down if only a small number of important nodes are attacked. For example, after attacking only 100 nodes, the network efficiency of the western power grid of the United States is down by 90%, and after attacking 200 nodes, the network scale of the maximum sub-graph is nearly 3% of the original network.