• 中国计算机学会会刊
  • 中国科技核心期刊
  • 中文核心期刊

计算机工程与科学

• 计算机网络与信息安全 • 上一篇    下一篇

道路交通网络中的关键节点识别方法研究

严开1,2,李玲1,2,秦永彬1,2   

  1. (1.贵州大学贵州省公共大数据重点实验室,贵州 贵阳 550025;2.贵州大学计算机科学与技术学院,贵州 贵阳 550025)
  • 收稿日期:2018-06-16 修回日期:2018-08-13 出版日期:2018-11-25 发布日期:2018-11-25
  • 基金资助:

    国家自然科学基金重大研究计划(91746116);贵州省重大应用基础研究项目(黔科合JZ字[2014]2001);贵州省科技重大专项计划(黔科合重大专项字[2017]3002)

Key node identification methods based on road traffic networks

YAN Kai1,2,LI Ling1,2,QIN Yongbin1,2   

  1. (1.Guizhou Provincial Key Laboratory of Public Big Data,Guizhou University,Guiyang 550025;
    2.College of Computer Science and Technology,Guizhou University,Guiyang 550025,China)
     
  • Received:2018-06-16 Revised:2018-08-13 Online:2018-11-25 Published:2018-11-25

摘要:

在现实世界中,大量复杂系统都可以通过抽象的节点和连边构成的网络来加以刻画。作为城市交通系统的重要组成部分,道路交通网络是一个典型的复杂系统,与人们的生活密切相关。道路交通网络中的关键节点识别问题是复杂网络领域研究中的一个经典难题。传统的度中心性算法和PageRank算法在复杂网络的关键节点的识别中具有较好的应用,考虑到道路交通网络中关键节点的特殊性和彼此关联性,在度中心性算法的基础上引入贪心算法的思想,提出了一个基于贪心策略的度中心性关键节点识别方法;同时,在PageRank算法的基础上引入贪心算法的思想,提出了一种基于贪心策略的PageRank关键节点识别方法,从而使道路交通网络中关键节点识别的结果更合理,在交通道路维护保养、规划设计,以及犯罪分子潜逃阻断等领域都有重要的应用价值。通过公开数据集与经典的关键节点识别方法做比较,验证了算法的有效性。
 

关键词: 道路交通网络, 关键节点识别, 贪心算法, 度中心性算法, 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