摘要
在现实世界中,大量复杂系统都可以通过抽象的节点和连边构成的网络来加以刻画。作为城市交通系统的重要组成部分,道路交通网络是一个典型的复杂系统,与人们的生活密切相关。道路交通网络中的关键节点识别问题是复杂网络领域研究中的一个经典难题。传统的度中心性算法和PageRank算法在复杂网络的关键节点的识别中具有较好的应用,考虑到道路交通网络中关键节点的特殊性和彼此关联性,在度中心性算法的基础上引入贪心算法的思想,提出了一个基于贪心策略的度中心性关键节点识别方法;同时,在PageRank算法的基础上引入贪心算法的思想,提出了一种基于贪心策略的PageRank关键节点识别方法,从而使道路交通网络中关键节点识别的结果更合理,在交通道路维护保养、规划设计,以及犯罪分子潜逃阻断等领域都有重要的应用价值。通过公开数据集与经典的关键节点识别方法做比较,验证了算法的有效性。
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 tra ditional 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 impor tant 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.
作者
严开
李玲
秦永彬
YAN Kai;LI Ling;QIN Yong-bin(Guizhou Provincial Key Laboratory of Public Big Data,Guizhou University,Guiyang 550025;College of Computer Science and Technology,Guizhou University,Guiyang 550025,China)
出处
《计算机工程与科学》
CSCD
北大核心
2018年第11期1983-1990,共8页
Computer Engineering & Science
基金
国家自然科学基金重大研究计划(91746116)
贵州省重大应用基础研究项目(黔科合JZ字[2014]2001)
贵州省科技重大专项计划(黔科合重大专项字[2017]3002)
