关键词: 道路交通网络, 关键节点识别, 贪心算法, 度中心性算法, PageRank算法

Abstract:

In real world, a large number of complex systems can be characterized by abstract nodes and networks of connected edges. As an important part of the urban transportation system, the road transportation network is a typical complex system, which is closely related to people's lives. The key nodes identification problem in road traffic networks is a classic problem in complex networks. The traditional degreecentric algorithm and PageRank algorithm are extensively in use for the identification of key nodes of complex networks. Considering the particularity and correlation of key nodes in the road traffic network, we introduce the idea of the greedy algorithm into the degreecentric algorithm, and propose a key nodes identification method.  We also introduce the idea of the greedy algorithm into the PageRank algorithm, and propose a key node identification method. The results of identifying key nodes in the road traffic network by the proposed methods are more reasonable, which means they have important application value in the fields of traffic road maintenance, planning and design, and prevention of criminals' escape. Experiments on public datasets verify the effectiveness of the two proposed algorithms in comparison with classic key node identification methods.

Key words: road traffic network, key node identification, greedy algorithm, degree centrality algorithm, PageRank algorithm