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

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

doi:10.16503/j.cnki.2095-9931.2023.04.009

交通运输研究 >

2023 , Vol. 9 >Issue 4: 93 - 103

DOI: https://doi.org/10.16503/j.cnki.2095-9931.2023.04.009

理论与方法

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

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

展开

¹ 交科院技术咨询（北京）有限公司，北京 100029
² 交通运输部科学研究院，北京 100029

姜仙童（1986—），女，辽宁丹东人，硕士，助理研究员，研究方向为交通运输规划与管理。E-mail: xiantong86@126.com

钟志敏（1993—），男，江西赣州人，硕士，工程师，研究方向为交通运输规划与管理。E-mail: 1594758957@qq.com

收稿日期: 2023-03-20

网络出版日期: 2023-09-22

收起

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

ZHONG Zhimin ^,¹ ,
JIANG Xiantong ^,² ,
TIAN Xiuzhu ¹ ,
WANG Chang ¹

Expand

¹ CATS Technical Consulting (Beijing) Co., Ltd., Beijing 100029, China
² China Academy of Transportation Sciences, Beijing 100029, China

Received date: 2023-03-20

Online published: 2023-09-22

Fold

摘要

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

关键词： 公交网络; 复杂网络; 节点重要性; 网络效率; 最大连通子图

本文引用格式

钟志敏 , 姜仙童 , 田秀珠 , 王昌 . 考虑节点相互影响的公交网络节点重要性识别算法[J]. 交通运输研究, 2023 , 9(4) : 93 -103 . DOI: 10.16503/j.cnki.2095-9931.2023.04.009

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

0 引言

《国务院关于印发“十四五”现代综合交通运输体系发展规划的通知》（国发〔2021〕27号）^[1]指出，要提高交通网络抗风险能力，增强交通运输网络韧性。其中，城市公交网络的抗风险性、可靠性是两个重要方面。在城市公交网络中，重要公交站点对维持网络的结构完善和功能正常运转有着重要的作用，因此准确识别公交网络的重要站点，进而采取适当的管控措施优化站点的通行条件和服务能力，对增强城市公交网络稳定性，保障公交安全高效运营具有重要意义。

重要节点是指对网络结构或功能具有较大影响的节点，识别复杂网络重要节点是当前的研究热点。经典的节点重要性算法有度中心性^[2]、半局部中心性^[3]、介数中心性^[4]、紧密度中心性^[5]、k-壳分解法^[6]等。有些学者在此基础上进行了优化，如王清晨^[7]、任卓明等^[8]、阮逸润等^[9]、胡钢等^[10]、Xu等^[11]、朱敬成等^[12]用度、集聚系数、拓扑重合度等拓扑特性描述节点和邻居节点间的联系，提出各自的节点重要性算法，但只考虑了网络的局部结构。部分学者提出的算法综合考虑了网络的局部结构和全局结构，对重要节点的识别具有不错的效果，如Yang等^[13]、Li等^[14]结合邻居节点信息和路径信息，分别提出基于重力中心性的k壳算法（K-shell Based on Gravity Centrality, KSGC）、基于度和k壳的重力模型算法（DK-Based Gravity Model, DKGM）算法；卢鹏丽等^[15]结合节点的介数中心性和邻居节点的度中心性，提出用介度熵来衡量节点重要性；Ullah等^[16]提出考虑节点自身影响和全局影响的全局结构模型（Global Structure Model, GSM）算法；刘书磊等^[17]和周漩等^[18]考虑了边对节点的影响，但仅关注边的局部信息，未考虑边对网络全局的影响。

当前，对节点与邻居节点互相影响的节点重要性算法研究中，更多地关注网络的局部结构，较少研究节点连边对两端节点的影响，也忽视了网络的全局特征。同时，研究也更多聚焦在使用SIS/SIR（Susceptible-Infectious-Susceptible/Susceptible-Infectious-Recovered）等网络模型对各种算法进行效果评估，较少使用真实复杂系统验证算法有效性，易忽略不同真实复杂系统之间的差异。因此，在考虑网络局部特征、全局特征和节点间相互影响的节点重要性算法的基础上，为准确识别公交网络中的重要站点，以增强网络的连通性和可靠性，保障乘客顺利出行，本文提出一种基于复杂网络的节点度、邻居节点度、边介数和节点间客流的算法——DeB（Degree and edge Betweenness），并以真实的公交网络为例进行仿真分析，验证算法性能，以期准确有效地识别公交网络的重要站点，增强网络的连通性和韧性，提升网络的可靠性。

1 复杂网络基础理论

近年来，因城镇化发展和城市规模扩张，城市公交系统规模不断扩大，逐渐变成一个复杂巨系统，由此引发一系列难题。复杂网络理论因而被用于城市公交网络相关研究中。复杂网络中存在一些特殊的节点被称为重要节点，其受到攻击不能正常发挥作用时，整个复杂网络可能会受到较大的影响，因此节点重要性识别研究是复杂网络领域的重要研究方向。

复杂网络的数学表现形式为节点构成的集合

V

和连边构成的集合

E

组成的图

G = (V, E)

，网络节点数量

N = V

，连边数量

M = E

。

1.1 重要节点识别方法

1.1.1 节点度和度中心性

节点度

k i

表示与节点

i

直接连通的节点的数量，即网络中以节点

i

为端点的边的数量^[2]，其计算公式为：

（1）

k i = ∑ j ≠ i e i j

式（1）中：

e i j

为节点

i

与节点

j

之间的边。

其中，若节点

i

与节点

j

有直接相连的边，则

e i j = 1

，反之

e i j = 0

。

度中心性

D i

认为网络中与节点相连的节点越多，则该节点在网络中越重要。节点

i

的度中心性定义为节点

i

的度与该节点可能存在最大连边数量的比值^[2]，其计算公式为：

（2）

D i = k i N - 1

式（2）中：

N

为网络中节点的数量。

度中心性是最早用于识别重要节点的算法，具有计算速度较快、应用范围较广的优势，但其仅关注网络的局部特征，具有较大的片面性。

1.1.2 节点介数和介数中心性

介数

B i

表示网络中经过节点

i

的最短路径的数量与网络中所有最短路径数量总和的比值^[4]，其计算公式为：

（3）

B i = ∑ j ≠ k n j k i n j k

式（3）中：

n j k

为节点对

j

、

k

间的最短路径数量；

n j k (i)

为节点对

j

、

k

之间的最短路径中通过节点

i

的最短路径数量。

介数中心性

B i

认为网络中所有节点对的最短路径中经过节点

i

的次数越多，节点越重要^[4]。对无向网络来说，

B i

计算公式为：

（4）

B i = 2 B i (N - 1) (N - 2)

介数中心性考虑了节点之间的最短路径，节点介数越高，表明途经该节点的最短路径越多、节点的重要性越高，是容易造成网络拥堵的瓶颈点。

1.2 网络建模方法

复杂网络由节点和边组成，网络建模是将现实网络抽象成适合进行复杂网络分析的过程。本文针对公交网络进行建模，与其他建模方法相比，L空间法更能体现公交网络站点与站点之间、站点与线路之间的拓扑关系，侧重于公交基础设施的连接，反映网络自然连接的状态，便于分析网络最基本的特征和形态。因此，本文采用L空间法，将公交网络构造成由站点和线路构成的复杂网络，考虑站点间的连接情况和客流情况，将公交系统中的站点当作网络节点，站点间的关系当作节点的连边。按照以下原则构建无向加权复杂公交网络。

1）公交停靠站点为网络节点，若两站点是某条线路中相邻的停靠站，则两节点间有边相连，否则两节点不相连；两节点之间至多只能存在一条边。

2）名称相同的站点视为同一节点，若站点有多个分站，也视为同一节点；名称不同的两个站点即使距离很近，也视为不同节点。

3）环形线路以内环线的停靠站点为准；支线与主线视为两条线路；上行线路与下行线路走向不一致时，以上行线路的停靠站点为准。

4）节点间连边的权重为途经节点的客流情况。

2 DeB节点重要性识别算法

2.1 算法原理

现实公交网络中，相邻的两个公交站点之间往往相距不远，特别是在城市中心区域，干线和支线公交线路的平均站距一般分别为0.5~0.8 km和0.3~0.5 km^[19]，因此经常出现乘客在搭乘同方向公交线路时，在不同公交站点上、下车的现象。如图1所示，出行起点S到公交站点A和B、出行终点T到公交站点C和D的距离相差很少，因此从出行起点S到出行终点T之间可能存在4条出行路径，即S→A→C→T、S→B→C→T、S→A→D→T、S→B→D→T。

显示原图|下载原图ZIP|生成PPT

图1 公交出行上下车站点选择及其出行路径

站点的距离越近，各条路径出行时间相差不大的可能性越大，站点间客流的相互影响也越大。该影响力的大小与途经站点的线路数量、发车间隔、客流大小有关，也与站点之间的路径在整个网络中的位置有关。由此，本文认为在复杂公交网络中，节点的重要性不仅与节点及其邻居节点的度值有关，也与该节点及其邻居节点间的相互影响有关。鉴于此，本文提出基于节点度、邻居节点度、边介数和节点间客流的DeB重要节点识别算法，边介数和节点间客流是连边的重要属性，也分别作为网络拓扑结构特征和网络运营特征，在DeB算法中表现为节点连边对两端节点影响力的大小。

同节点介数一样，边介数

B e i j

是指网络中所有节点对的最短路径中经过边

e i j

的数量占最短路径总数的比例^[4]，其计算公式为：

（5）

B e i j = ∑ k ≠ l n k l (i j) n k l

式（5）中：

n k l

为节点对

k

l

间最短路径的数量；

n k l (i j)

为节点对

k

l

间最短路径中通过边

e i j

的最短路径数量。

由边介数的定义可知，

B e i j

越大，表示途经边

e i j

的最短路径越多，边

e i j

两端的节点

i

和节点

j

相互之间的影响越大。

为描述DeB算法下节点的重要性，引入节点吸引度

A i

指标，定义节点

i

的吸引度

A i

为节点

i

向其邻居节点吸收的度值与其自身度值之和。吸引度

A i

计算公式为：

（6）

A i = k i + ∑ j ∈ Γ i B e i j p i j k j

式（6）中：

Γ i

为节点

i

的邻居节点集合；

p i j

为途经节点对

i

、

j

间的客流。

更进一步，考虑到邻居节点对其邻居节点也会产生吸引，因此定义节点

i

的

n

阶吸引度

A i n

为节点向其邻居节点吸收

n

次之后的节点重要性指标，其计算公式为：

（7）

A i n = A i n - 1 + ∑ j ∈ Γ i B e i j p i j A j n - 1

式（7）中：

n ≥ 1

，且

A i 0 = k i

，即节点

i

的0阶吸引度等于其节点度。

DeB算法以边介数

B e i j

和节点间客流

p i j

这两项连边属性为纽带，将节点和邻居节点巧妙结合，得到的节点重要性度量指标

A i n

兼顾了度中心性所体现的网络局部特征和介数中心性所体现的网络全局特征。

2.2 算法有效性评价指标

通过节点重要性算法获得节点重要性序列后，需进一步验证算法的有效性。验证方法是：按节点重要性排序在所获得的节点序列中依次移除节点，即基于节点重要性算法的蓄意攻击，观察节点移除过程中网络结构和功能的变化情况。网络效率和最大连通子图是常用的评价网络结构或功能的指标。在公交网络中，网络效率表现为乘客通过公交出行到达网络中其他节点的难易程度，即网络效率越高，乘客公交出行越方便；最大连通子图表现为乘客通过公交出行可到达网络中其他节点的能力，即最大连通子图越大，乘客可到达目的地的概率越大。

1）网络效率和累积网络效率

网络效率E^[20]是指网络中所有节点对距离倒数之和的平均值，计算公式为：

（8）

E = 1 N N - 1 ∑ i ≠ j 1 d i j

式（8）中：

d i j

为节点对

i

、

j

间的最短距离。

其中，若节点对

i

、

j

之间不存在最短路径，则

1 / d i j = 0

。对于加权网络，式（8）中的

d i j

可替换为边权

w i j

，即考虑了边权

w i j

的网络效率。

累积网络效率

E c

^[21]是指节点移除的过程中，得到的所有网络效率之和，其计算公式为：

（9）

E c m = ∑ i ∈ m E i

式（9）中：

m

为已移除的节点的集合。

按照不同序列移除节点所得到的

E c

不同，

E c

越小表示该序列对网络效率的影响越大。

2）最大连通子图和累积最大连通子图

最大连通子图是体现网络连通性的度量指标，连通图的最大连通子图就是其本身，非连通图的最大连通子图是指连接节点数量最多的连通子图^[22]。节点移除后，连通图可能变成非连通图，并形成多个节点数量不同的连通子图，最大连通子图的规模

N m a x

越大，其最大限度保持正常通行的能力就越强。

N m a x

计算公式为：

（10）

N m a x = m a x N 1, N 2, N 3, ⋯

式（10）中：

N m a x

为最大连通子图规模，即最大连通子图包含的节点数量；

N 1

N 2

N 3

…为各连通子图包含的节点数目。

累积最大连通子图

N C m a x

是指节点移除过程中获得的所有最大连通子图规模之和，其计算公式为：

（11）

N C m a x m = ∑ i ∈ m N m a x i

按照不同序列移除节点所得到的

N C m a x

不同，

N C m a x

越小表示该序列对网络连通性的影响越大。

2.3 算例分析

为验证DeB算法的有效性，本节以图2所示的算例网络为例，研究分析DeB算法与度中心性、介数中心性两种算法在节点删除时网络结构和功能的变化。假设图2中节点间客流均为1，即算例网络为无权网络。因算例网络的直径为6，故将DeB算法得到的1阶吸引度、2阶吸引度和6阶吸引度与度中心性、介数中心性相比较，重要节点序列如表1所示。

显示原图|下载原图ZIP|生成PPT

图2 算例网络拓扑结构图

由图2和表1可知，节点6、7是“桥节点”，只要移除其中一个，网络将变成非连通图。介数中心性认为节点6、7是最重要的节点，介数均为0.56，DeB算法认为节点6的重要性较节点7更高，这符合节点6的一侧较节点7连接了更多的节点，重要性应较节点7更高的现象；节点2、3、4、5的度中心性均为0.44，节点8、10的度中心性均为0.11，但节点3、5更靠近网络的中心位置，因此其介数中心性更高，在DeB算法中，其吸引度也比节点2、4、10更高；节点1、9的度中心性均为0.22，但节点9是到达节点10的必经之路，其各阶吸引度也都比节点1的更高。由此可知，当网络为无权网络时，采用吸引度衡量节点重要性的DeB算法可有效识别出重要节点。

表1 算例网络的重要节点序列

节点	2	3	4	5	6	7	1	9	8	10
度中心性	0.44	0.44	0.44	0.44	0.33	0.33	0.22	0.22	0.11	0.11
节点	6	7	9	3	5	2	4	1	8	10
介数中心性	0.56	0.56	0.22	0.21	0.21	0.10	0.10	0.00	0.00	0.00
节点	6	3	5	7	2	4	9	1	8	10
1阶吸引度	6.82	5.86	5.86	5.51	5.22	5.22	3.27	2.80	1.60	1.40
节点	6	7	3	5	2	4	9	1	8	10
2阶吸引度	13.01	10.63	9.10	9.10	6.98	6.98	5.51	3.84	2.70	2.05
节点	6	7	3	5	9	2	4	8	10	1
6阶吸引度	133.5	122.6	65.9	65.9	57.5	30.9	30.9	29.8	14.9	14.0

DeB算法得到不同阶数的节点吸引度不同，其节点重要性排序也不同，当阶数

n = 6

时，节点9的吸引度比节点2和节点4的高，节点8与节点2和4的吸引度相接近，这与节点移除后对网络结构和功能的影响表现不一致（见图3）。因此，为提高DeB算法对重要节点识别的准确性，需针对不同的网络确定节点吸引度最佳阶数。

显示原图|下载原图ZIP|生成PPT

图3 移除节点8或节点2后算例网络拓扑结构图

3 实证分析

本文以宁波市公交系统为例，按照上文描述的建模方法构建无向加权的复杂公交网络。网络包含1 531个节点、2 231条边，平均节点度为2.91，平均最短距离为17.06站。

3.1 节点吸引度最佳阶数

节点

i

的

n

阶吸引度，是

n - 1

阶吸引度与节点通过连边的边介数向其邻居节点中吸引而来的吸收值之和。该吸收值与边介数、邻居节点的

n - 1

阶吸引度有关，而邻居节点的

n - 1

阶吸引度与其邻居节点的

n - 2

阶吸引度有关，由此推之，当

n

达到一定值时，节点吸引度将遍历网络中所有节点。

由本文第2节的研究可知，节点吸引度的阶数将影响DeB算法的有效性，考虑到本文研究的宁波市公交网络的平均最短距离为17.06站，故本文的研究对象为节点的1~9阶吸引度。

本文通过对公交网络进行模拟蓄意攻击，观察网络效率和最大连通子图的变化情况以确定最佳吸引度阶数。公交网络的节点数量较大，若逐一移除节点，数据处理时间会较长，因此采取每次移除0.05N个节点数量，即前19次每次移除77个节点，最后1次移除68个节点，分20次将节点完全移除的蓄意攻击策略。

图4所示为1~9阶吸引度对网络效率和最大连通子图的影响，图中的横坐标为节点移除比例，纵坐标为节点移除后的网络效率和最大连通子图规模。表2给出了1~9阶吸引度下累积网络效率和累积最大连通子图规模的数据。

显示原图|下载原图ZIP|生成PPT

图4 1~9阶吸引度对网络效率和最大连通子图的影响

由图4可知，不管是网络效率还是最大连通子图规模，1阶吸引度的曲线在大部分时间内处于图的最下方，表2中1阶吸引度的累积网络效率和累积最大连通子图规模也低于其余阶数吸引度，且累积网络效率和累积最大连通子图规模随节点吸引度阶数的增加而呈上升趋势。换言之，与其他阶数的吸引度相比，1阶吸引度能更好地衡量公交复杂网络节点的重要性。

表2 1~9阶吸引度下累积网络效率和累积最大连通子图规模数据

吸引度阶数	1	2	3	4	5	6	7	8	9
累积网络效率	2.890 0	3.063 8	3.118 1	3.224 6	3.305 0	3.458 5	3.510 1	3.631 2	3.722 5
累积最大连通子图规模/个	3 393	3 654	3 947	4 022	4 250	4 588	4 645	4 738	4 804

3.2 DeB算法验证

由于DeB算法获得的1阶吸引度对重要节点识别的准确性最高，因此研究比较网络效率和最大连通子图规模在基于1阶吸引度、度中心性、介数中心性三种蓄意攻击策略下的变化情况，以验证DeB算法的准确性。

1）网络效率

采取每次移除0.05N个节点，直至全部节点被移除的蓄意攻击策略，移除节点的比例和网络效率之间的关系如图5所示。在1阶吸引度、度中心性、介数中心性3种蓄意攻击策略下，1阶吸引度的网络效率下降最快，介数中心性下降相对缓和，度中心性介于二者之间。

显示原图|下载原图ZIP|生成PPT

图5 每次移除0.05N个节点对网络效率的影响

当节点移除比例低于0.2时，网络效率下降速率较快，尤其是移除了前0.05N个节点时，3种算法的网络效率下降幅度均最大。随着移除比例的增加，网络效率的下降幅度变小，体现了重要节点对网络效率的影响比其他节点大。当节点移除比例达到0.2N后，3种算法下的网络效率均低于0.1。

为进一步分析重要节点对网络效率的影响，本文还采取了第2种蓄意攻击策略，即每次移除1个节点，直至0.2N个节点被移除。该种攻击策略下，网络效率的变化情况如图6所示。

显示原图|下载原图ZIP|生成PPT

图6 每次移除1个节点直至0.2N个节点被移除对网络效率的影响

由图6可知，移除前2个节点时，介数中心性的网络效率下降最快，然后1阶吸引度的网络效率下降幅度超过了介数中心性，之后在部分区域与度中心性的网络效率下降幅度相差不大，但是多数情况下1阶吸引度的曲线处于图的最下方，网络效率下降幅度最大。

经测算，在节点移除比例由0.05增大到1的过程中，1阶吸引度的累积网络效率均比其他两种算法小，其次是度中心性，最大的是介数中心性，如表3所示。

表3 不同节点移除比例对应的累积网络效率

节点移除比例	0.05	0.1	0.15	0.2	0.25	0.3	0.35	0.4	0.45	0.5
度中心性	2.662 2	2.866 8	2.937 6	2.982 3	3.008 7	3.027 1	3.039 8	3.048 6	3.055 0	3.060 3
介数中心性	2.933 2	3.494 2	3.842 9	4.079 3	4.208 1	4.297 6	4.346 3	4.379 7	4.403 5	4.418 2
1阶吸引度	2.538 3	2.681 7	2.757 8	2.798 1	2.824 0	2.843 2	2.855 9	2.864 2	2.870 8	2.876 5
节点移除比例	0.55	0.6	0.65	0.7	0.75	0.8	0.85	0.9	0.95	1
度中心性	3.065 0	3.068 6	3.071 3	3.073 5	3.075 1	3.076 2	3.076 9	3.077 2	3.077 2	3.077 2
介数中心性	4.428 1	4.435 2	4.439 6	4.442 6	4.444 5	4.445 2	4.445 5	4.445 5	4.445 5	4.445 5
1阶吸引度	2.881 2	2.884 5	2.886 9	2.888 4	2.889 3	2.889 8	2.890 0	2.890 0	2.890 0	2.890 0

2）最大连通子图规模

与网络效率一样，分别采取两种蓄意攻击策略研究移除节点比例和最大连通子图规模之间的关系，详见图7和图8。

显示原图|下载原图ZIP|生成PPT

图7 每次移除0.05N个节点直至节点全部移除对最大连通子图规模的影响

显示原图|下载原图ZIP|生成PPT

图8 每次移除1个节点直至0.2N个节点被移除对最大连通子图规模的影响

由图7和图8可以看出，与移除节点对网络效率的影响一致，大多数情况下1阶吸引度的曲线都处于图的最下方，即其最大连通子图规模变化最大，网络的连通性最差。其中，图8中3种算法均呈现最大连通子图规模缓慢下降和突然下降交替出现的现象，即多数情况下，每移除1个节点，最大连通子图规模相应地减少1个，曲线下降较为缓慢，直至被移除的节点累积到一定的数量时，最大连通子图的规模出现断崖式下降，随后又恢复成缓慢下降的状态。移除的节点重要性越高，最大连通子图出现断崖式下降的频率也越快，体现了重要节点对最大连通子图的影响更大，少部分重要节点的移除会对网络的连通性产生严重的影响。

经测算，在节点移除比例由0.05增大到1的过程中，1阶吸引度的累积最大连通子图规模均比其他两种算法小，其次是度中心性，最大的是介数中心性（见表4），这与节点移除对网络效率的影响相似。

表4 不同节点移除比例对应的累积最大连通子图规模单位：个

节点移除比例	0.05	0.1	0.15	0.2	0.25	0.3	0.35	0.4	0.45	0.5
度中心性	2 891	3 299	3 539	3 774	3 829	3 873	3 913	3 937	3 961	3 975
介数中心性	2 829	3 775	4 372	4 783	5 122	5 408	5 546	5 635	5 690	5 714
1阶吸引度	2 443	2 811	3 057	3 140	3 184	3 228	3 253	3 277	3 301	3 318
节点移除比例	0.55	0.6	0.65	0.7	0.75	0.8	0.85	0.9	0.95	1
度中心性	3 986	3 997	4 004	4 011	4 017	4 023	4 028	4 033	4 034	4 034
介数中心性	5 730	5 739	5 748	5 754	5 758	5 761	5 764	5 766	5 767	5 767
1阶吸引度	3 332	3 343	3 353	3 362	3 371	3 380	3 388	3 392	3 393	3 393

以宁波市公交系统排名靠前的节点为例，进一步比较分析节点1阶吸引度与度中心性和介数中心性对重要节点的识别情况，表5仅列举了3种节点重要性识别算法获取的重要性排名前20的节点情况。研究结果表明，节点1阶吸引度是在度中心性基础上进行优化，因此其得到的节点重要性排序与度中心性的相似度最高，前20个节点中有13个相同的节点，但是排序大不相同，且距离越靠后，排序的差别越大。不同的7个节点中，宁大附属医院、红梅新村、镇海公交、白沙路、外滩等5个站点位于介数中心性前20，孔浦中学位于介数中心性的第31，陆家村分别位于度中心性和介数中心性的第25和53。这也说明DeB算法所获得的1阶吸引度融合了度中心性算法和介数中心性算法二者的特性，实现了二者的优势互补，可以识别出度中心性和介数中心性各自所忽视的部分节点的重要性。

表5 3种算法识别的重要性前20节点对比

排序	度中心性	介数中心性	1阶吸引度
1	高塘花园	红梅新村	宁大附属医院
2	东门口（天一广场）	镇海公交	红梅新村
3	望湖市场	庆丰桥东	中山西路文化路口
4	江厦公园	谢家	镇海公交
5	灵桥西（日新街）	天水家园北	白沙路
6	怡江新村	白沙路	大卿桥
7	谢家	市妇儿医院北院	东门口（天一广场）
8	三江中学	公交庆丰桥站	孔浦中学
9	老庙（市公交总公司）	宝庆讲寺	望湖市场
10	解放南路大梁街口	慈城	外滩
11	荣骆路	宁大附属医院	荣骆路
12	大卿桥	江澄北路民安东路口	高塘花园
13	马园社区	天一家园（泰安社区）	怡江新村
14	姚江花园	环城北路人民路口	解放南路大梁街口
15	鄞奉路尹江路口	日湖公园北	江厦公园
16	兴宁桥东	荣骆路	陆家村
17	中山西路文化路口	外滩	老庙（市公交总公司）
18	梅墟	慈城南门	兴宁桥东
19	锦苑小区（家乐福）	新星村	谢家
20	明楼公园（家乐福）	老庙（市公交总公司）	灵桥西（日新街）

3.3 算法性能总结

综合来看，相较于度中心性和介数中心性，1阶吸引度能更准确地识别网络中的重要节点。DeB算法获得的1阶吸引度融合了度中心性算法和介数中心性算法分别体现出的网络局部特征和全局特征，以及客流所体现出的网络现实特征，在宁波市公交网络重要节点识别中表现出较好的准确性。此外，本方法还应用于青岛市、株洲市等城市，为当地公交网络运营提供了有价值的参考，进一步验证了算法的普适性与可移植性。

4 结束语

准确识别重要公交站点，采取适当措施优化重要站点周边的道路交通条件，对提高公交网络运营的稳定性和韧性具有重要的现实意义。本文聚焦于连边对重要节点的影响，采用边介数和客流两项指标，从网络拓扑结构和网络实际运行状态两个方面描述连边对两端节点的影响，进而提出了DeB重要节点识别算法。在此基础上，通过对宁波市等城市公交网络的实证研究，发现该算法的节点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Ü 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.

Options

文章导航

模态框（Modal）标题

摘要

本文引用格式

Abstract

0 引言

1 复杂网络基础理论

1.1 重要节点识别方法

1.1.1 节点度和度中心性

1.1.2 节点介数和介数中心性

1.2 网络建模方法

2 DeB节点重要性识别算法

2.1 算法原理

图1 公交出行上下车站点选择及其出行路径

2.2 算法有效性评价指标

2.3 算例分析

图2 算例网络拓扑结构图

表1 算例网络的重要节点序列

图3 移除节点8或节点2后算例网络拓扑结构图

3 实证分析

3.1 节点吸引度最佳阶数

图4 1~9阶吸引度对网络效率和最大连通子图的影响

表2 1~9阶吸引度下累积网络效率和累积最大连通子图规模数据

3.2 DeB算法验证

图5 每次移除0.05N个节点对网络效率的影响

图6 每次移除1个节点直至0.2N个节点被移除对网络效率的影响

表3 不同节点移除比例对应的累积网络效率

图7 每次移除0.05N个节点直至节点全部移除对最大连通子图规模的影响

图8 每次移除1个节点直至0.2N个节点被移除对最大连通子图规模的影响

表4 不同节点移除比例对应的累积最大连通子图规模 单位：个

表5 3种算法识别的重要性前20节点对比

3.3 算法性能总结

4 结束语

参考文献

表4 不同节点移除比例对应的累积最大连通子图规模单位：个