考虑节点相互影响的公交网络节点重要性识别算法

钟志敏, 姜仙童, 田秀珠, 王昌

交通运输研究 ›› 2023, Vol. 9 ›› Issue (4) : 93-103.

交通运输研究 ›› 2023, Vol. 9 ›› Issue (4) : 93-103. DOI: 10.16503/j.cnki.2095-9931.2023.04.009
理论与方法

考虑节点相互影响的公交网络节点重要性识别算法

作者信息 +

Algorithm for Identifying Importance of Public Transportation Network Nodes Considering Mutual Influence of Nodes

  • ZHONG Zhimin 1 ,  
  • JIANG Xiantong 2 ,  
  • TIAN Xiuzhu 1 ,  
  • WANG Chang 1
Author information +
文章历史 +

摘要

为提高公交网络运营稳定性,保障乘客顺利出行,需准确识别公交网络中的重要节点并进行重点保护。鉴于此,考虑公交网络节点相互影响的网络拓扑特性和现实特征,提出了DeB(Degree and edge Betweenness)节点重要性识别算法,以边介数和客流表示节点相互影响力的大小,同时,引入节点n 阶吸引度作为衡量节点重要性的指标。最后,以宁波市公交网络为例,研究比较了在基于DeB算法、度中心性算法、介数中心性算法的模拟蓄意攻击下,网络效率和最大连通子图的变化情况,以验证算法的有效性和精确性。结果显示,基于DeB算法得到的节点1阶吸引度的蓄意攻击对网络效率和最大连通子图的影响最大,即对重要节点识别的精确性越高,且节点吸引度阶数越高,算法精确性越低;与度中心性、介数中心性相比,节点1阶吸引度的精确性更高,表明DeB算法得到的节点1阶吸引度可更准确地衡量节点的重要性。

Abstract

In order to improve the operational stability of public transportation network and ensure the smooth travel of passengers, it is necessary to accurately identify important nodes in the public transportation network and carry out key protection. In view of this, the DeB(Degree and edge Betweenness) node importance recognition algorithm was proposed considering the network topology and practical characteristics of the mutual influence of public transportation network nodes. The DeB algorithm represents the mutual influence of nodes by the edge betweenness and passenger flow. At the same time, n-order attractiveness of node was introduced as an indicator to measure the importance of nodes. Finally, taking Ningbo public transportation network as an example, the changes in network efficiency and largest connected subgraph under simulate deliberate attacks based on DeB algorithm, degree centrality, and betweenness centrality were compared to verify the effectiveness and accuracy of the algorithm. The results show that the deliberate attacks based on the DeB algorithm′s 1-order attractiveness of node has the greatest impact on network efficiency and the largest connected subgraph, which means that, the higher the accuracy of identifying important nodes and the order of node attractiveness are, the lower the accuracy of the algorithm is. Compared with degree centrality and betweenness centrality, the accuracy of node 1-order attractiveness is higher, indicating that the 1-order attractiveness of node obtained by the DeB algorithm can measure the importance of nodes more accurately.

关键词

公交网络 / 复杂网络 / 节点重要性 / 网络效率 / 最大连通子图

Key words

public transportation network / complex network / nodes importance / network efficiency / largest connected subgraph

引用本文

导出引用
钟志敏, 姜仙童, 田秀珠, . 考虑节点相互影响的公交网络节点重要性识别算法[J]. 交通运输研究. 2023, 9(4): 93-103 https://doi.org/10.16503/j.cnki.2095-9931.2023.04.009
ZHONG Zhimin, JIANG Xiantong, TIAN Xiuzhu, et al. Algorithm for Identifying Importance of Public Transportation Network Nodes Considering Mutual Influence of Nodes[J]. Transport Research. 2023, 9(4): 93-103 https://doi.org/10.16503/j.cnki.2095-9931.2023.04.009
中图分类号: U491.1   

参考文献

[1]
国务院综合规划司. 国务院关于印发“十四五”现代综合交通运输体系发展规划的通知 (国发 〔2021〕27号) [EB/OL]. [2022-01-19](2023-03-10). https://xxgk.mot.gov.cn/2020/jigou/zhghs/202201/t20220119_3637245.html.
[2]
BONACICH P. Factoring and weighting approaches to status scores and clique identification[J]. The Journal of Mathematical Sociology, 1972, 2(1): 113-120.
[3]
CHEN D B, L Y, SHANG M S, et al. Identifying influential nodes in complex networks[J]. Physica A: Statistical Mechanics & Its Applications, 2012(4): 1777-1787.
[4]
FREEMAN L C. A set of measures of centrality based on betweenness[J]. Sociometry, 1977, 40(1): 35-41.
[5]
FREEMAN L C. Centrality in social networks: Conceptual clarification[J]. Social Networks, 1978, 1(3): 215-239.
[6]
KITSAK M, GALLOS L K, HAVLIN S, et al. Identification of influential spreaders in complex networks[J]. Nature Physics, 2010, 6(11): 888-893.
[7]
王清晨. 基于网络局部信息的重要节点排序算法研究[D]. 新乡: 河南师范大学, 2019.
[8]
任卓明, 邵凤, 刘建国, 等. 基于度与集聚系数的网络节点重要性度量方法研究[J]. 物理学报, 2013, 62(12):522-526.
[9]
阮逸润, 老松杨, 王竣德, 等. 基于领域相似度的复杂网络节点重要度评估算法[J]. 物理学报, 2017, 66(3):371-379.
[10]
胡钢, 徐翔, 高浩, 等. 基于邻接信息熵的网络节点重要性识别算法[J]. 系统工程理论与实践, 2020, 40(3):714-725.
[11]
XU X, ZHU C, WANG Q Y, et al. Identifying vital nodes in complex networks by adjacency information entropy[J]. Scientific Reports, 2020, 10(1): 2691.
[12]
朱敬成, 王伦文, 吴涛. 一种基于局部特征的节点重要性排序方法[J]. 计算机仿真, 2022, 39(11):416-421.
[13]
YANG X, XIAO F. An improved gravity model to identify influential nodes in complex networks based on k-shell method[J]. Knowledge-Based Systems, 2021, 227(5): 107198.
[14]
LI Z, HUANG X. Identifying influential spreaders in complex networks by an improved gravity model[J]. Scientific Reports, 2021, 11(1): 1-10.
[15]
卢鹏丽, 郭旭东, 董璊, 等. 基于介度熵的复杂网络节点重要度识别方法[J]. 兰州理工大学学报, 2020, 46(2):111-115.
[16]
ULLAH A, WANG B, SHENG J, et al. Identification of nodes influence based on global structure model in complex networks[J]. Scientific Reports, 2021, 11(1): 6173.
[17]
刘书磊, 杜家乐, 邵增珍. 一种基于邻居节点和边的复杂网络节点排序方法——NL中心性算法[J]. 山东科学, 2019, 32(2):130-136.
[18]
周漩, 张晋武. 一种复杂加权网络节点重要度评估方法[J]. 兵工学报, 2015, 36(S2):268-273.
[19]
济南市城市交通研究中心, 交通运输部科学研究院, 北京交通发展研究院, 等. 公共汽电车线网设置和调整规则:GB/T 37114—2018[S]. 北京: 中国标准出版社, 2018.
[20]
LATORA V, MARCHIORI M. Efficient behavior of small-world networks[J]. Physical Review Letters, 2001, 87(19): 198701.
[21]
党育卓, 陈子墨, 郭昱普, 等. 网络节点重要度排序及效能评价[C]// 第十届中国指挥控制大会论文集(下册). 北京: 兵器工业出版社, 2022:306-311.
[22]
刘寅, 马继辉, 任广建. 基于多层空中交通网络的抗毁性分析[C]// 2022世界交通运输大会(WTC2022)论文集(运输规划与交叉学科篇). 北京: 人民交通出版社股份有限公司, 2022:363-371.

Accesses

Citation

Detail

段落导航
相关文章

/