Node Importance And Its Application In Urban Public Transport Network

Node plays an important role in networks and has special significance. Node importance evaluation that uses the differences between the nodes has become one of the hotspots. In terms of the current study situation, classic node importance evaluation algorithms have several problems such as inaccuracy evaluation on bridge nodes and huge time consumption and space consumption. In this paper, we evaluate the importance of the node by both-degree,and propose both-degree evaluation algorithm and both-degree evaluation algorithm based on nodes deleting. We verify the validity and rationality of the improved algorithm in classic datasets. At last, we apply the algorithms in survivability analysis of Shijiazhuang public transport network and provide evidence on optimization of the bus lines and bus stations.This paper focuses on the following aspects:(1) Improvements on node importance evaluation algorithm. We propose both-degree evaluation algorithm and both-degree evaluation algorithm based on node deleting to make up for classical algorithms’ shortcomings. Based on the traditional concepts, we put forward several notions such as node adjacent-degree, node both-degree, network adaptation-degree and network surplus-degree. Both-degree evaluation algorithm evaluates node by both-degree index. A larger both-degree a node has, the more important the node will be. The second algorithm calculates the both-degree repeatedly while deleting the nodes one by one in the new network. We evaluate nodes by difference of both-degree before and after. The larger the difference of both-degree, the higher influence the deleted node has, the greater influence the more important the node will be. Experiments show that improved algorithms can make up the shortcomings of classical algorithm, but also make node importance evaluation more effective.(2) Study improved node importance evaluation algorithm application in the urban public transport network survivability analysis. This study construct bus line network and bus station network model of Shijiazhuang city transport network using the software of Matlab and Pajek. Through analysis of static characteristics of the network shows that the bus line network has small world network features, and both networks have scale-free networkfeatures. To test survivability of both networks, we expand deliberate attacks according to both-degree evaluation algorithm result and the network becomes easily paralyzed if we attack the important node in the network. According to the result of both-degree evaluation algorithm based on nodes deleting, we divide the nodes into two groups, the important group and the unimportant group. Experiments show that when we attack randomly nodes in the important group, the network becomes easily paralyzed. In contrast the network displays strong robustness when we attack randomly nodes in the unimportant group.