摘要
针对城市轨道交通网络中关键节点的识别准确度低与执行耗费时间长等问题,文中展开了进一步的算法优化研究。基于复杂网络理论和贪心迭代算法原理的思想,构建了适用于城市轨道交通网络的关键节点识别算法。该算法在分析图的理论基础上,对复杂网络进行定义和分类,改进了经典Page Rank算法中所存在的“均分跳转”缺陷,充分考虑了复杂网络中缺失节点对其他节点所产生的各种综合影响。同时,文中引入了节点之间的相似比、度值比和关键度等多种指标,最终提出基于贪心迭代算法思想的关键节点识别算法。采用成都地铁的实际数据进行仿真计算,结果表明,在相同的攻击条件下,与经典Page Rank算法相比,基于贪心迭代思想的关键节点识别算法具有较高的识别准确度与更少的执行时间消耗。
In allusion to the low recognition accuracy and long execution time⁃consumption of key nodes in the urban rail transit network,the further algorithm optimization research is carried out.A key node identification algorithm suitable for urban rail transit network is constructed on the basis of complex network theory and the greedy iterative algorithm principle.In the algorithm,the complex network is defined and classified on the basis of theory of analyzing graphs,the"equal jump"defect existing in the classic Page Rank algorithm is improved,and the synthetic effects of missing nodes on other nodes in complex networks is fully taken into account.At the same time,multiple indicators such as the similarity ratio,degree value ratio and criticality among nodes are introduced into this paper,so that the key node identification algorithm based on the idea of greedy iterative algorithm is proposed.The actual data of Chengdu metro are used for the simulation calculation,and the results show that under the same attack conditions,the key node identification algorithm based on the greedy iterative idea has higher recognition accuracy and less execution time consumption in comparison with the classic Page Rank algorithm.
作者
李三江
杨昊成
朱光剑
赵云
LI Sanjiang;YANG Haocheng;ZHU Guangjian;ZHAO Yun(State Key Laboratory of Communication Anti-interference Technology,University of Electronic Science and Technology of China,Chengdu 611731,China;Maintenance Branch,Chengdu Metro Operation Co.,Ltd.,Chengdu 610017,China;Chengdu Jiuxin Information Technology Co.,Ltd.,Chengdu 610041,China;Chengdu Huibao High Tech Information Technology Co.,Ltd.,Chengdu 610041,China)
出处
《现代电子技术》
2021年第24期102-106,共5页
Modern Electronics Technique
基金
四川省科学技术厅“软件代码安全检测服务平台示范项目”(2019GFW177)。
关键词
城轨交通
复杂网络
关键节点识别
贪心迭代算法
网络分类
仿真计算
urban rail transit
complex network
key node identification
greedy iterative algorithm
network classification
simulation calculation
