一种路网拥堵关键节点识别方法、设备、介质

1.本发明涉及城市交通规划技术领域，尤其是涉及一种路网拥堵关键节点识别方法、设备、介质。


背景技术：

2.交通道路网络包含众多交通节点及连接节点的错综复杂的交通线路，是一个城市最重要的基础设施，一旦建设好，便具有长期存在的特性，其结构和布局集中体现了城市的拓扑结构和空间分布。然而伴随着出行方式的增多和交通工具的普及，交通拥堵的出现不仅直接增加居民的出行时间和成本，更会给社会带来巨额的经济损失。分析研究交通路网的关键区域及关键节点，研究路网的复杂特性，对于解决交通拥堵疏散，调整交通出行决策等相关问题具有十分重要的意义。
3.依据统计复杂网络信息种类和方向的差异，网络节点重要性评估方法可以分成以下三类：考虑邻居节点及局部信息、考虑特征向量及随机跳转机制、考虑节点位置及相关属性。第一类方法仅对节点邻域信息进行统计，计算复杂度低，但是忽略了节点在全局网络的度量，因而该种方法不适用于大型网络。考虑特征向量及随机跳转机制的方法起源于网页连接网络的节点识别，经典的算法包括pagerank、leaderrank等，该类方法从全局角度统计节点重要性，计算复杂度较高，但是其随机挑战机制和主要应用于有向结构不太符合现实其他网络。考虑节点位置及相关属性的方法是一种基于全局结构的粗粒化分解方法。基于位于网络中心的节点相比于位于网络边缘的节点更重要，该方法对节点分配ks值来快速评估节点的重要性，但是无法对同层的节点进行重要性排序。
4.但是，截止目前，所有针对复杂网络关键节点改进的方法存在以下两点研究空白：首先这些方法都没有面向实际路网进行研究，同时忽略交通拥堵特性和路网拓扑结构。
5.以上情况，在一定程度上阻碍了复杂网络信息挖掘在交通领域的发展和实际应用，当前缺少针对上述提出的问题的改进方法。


技术实现要素：

6.本发明的目的就是为了克服上述现有技术存在的缺陷而提供一种路网拥堵关键节点识别方法、设备、介质，基于交通路网原始数据构建具有多个节点和连边的交通网络，通过k-shell分解确定多层邻域内的邻居节点并计算各节点的影响度评价指标，基于影响度评价指标，实现路网拥堵关键节点的识别。
7.本发明的目的可以通过以下技术方案来实现：
8.本发明的一个方面，提供了一种路网拥堵关键节点识别方法，包括如下步骤：
9.获取交通路网原始数据，通过网络建模获取包括多个节点和连边的交通网络；
10.针对所述交通网络进行k-shell分解，获取各节点的多层邻域内的邻居节点；
11.针对每个节点，基于多层邻域内的邻居节点计算影响度评价指标，基于所述影响度评价指标获取拥堵关键节点，实现路网拥堵关键节点的识别。
12.作为优选的技术方案，每个所述的节点包括如下信息：当前节点的度、邻居节点信息、唯一标识信息、节点对应的ks层以及sir仿真状态值信息。
13.作为优选的技术方案，通过网络建模获取包括多个节点和连边的交通网络的过程包括如下步骤：
14.将实际环境中的路口建模为所述交通网络中的节点，将实际环境中的道路建模为所述交通网络中的连边。
15.作为优选的技术方案，所述的邻居节点的确定过程包括如下步骤：
16.通过对所述交通网络进行k-shell分解，递归地剥离所述交通网络中的各个节点，将各个节点分配到不同的ks层中，基于预设的搜索策略确定当前节点多层邻域内的邻居节点。
17.作为优选的技术方案，所述的预设的搜索策略为广度优先的搜索策略。
18.作为优选的技术方案，邻居节点的影响度评价指标采用下式计算：
19.s＝∑si20.s1＝∑β
[0021][0022]
式中，s为当前节点的影响度评价指标，s1为第一层邻居节点的影响度评价指标，sn为第n层邻居节点的影响度评价指标，其中，n》1，β为sir模型中的传播概率，neighbor_n-1为当前节点的n层邻居节点，εi为当前节点到neighbor_n-1中每个节点的所有路径，d为节点之间的路径长度。
[0023]
作为优选的技术方案，所述的交通网络是无向且无权的网络。
[0024]
作为优选的技术方案，所述的拥堵关键节点的获取包括如下步骤：
[0025]
根据各节点的影响度评价指标和所属ks层对各个节点进行排序，获取所述拥堵关键节点。
[0026]
本发明的另一个方面，提供了一种电子设备，包括：一个或多个处理器以及存储器，所述存储器内储存有一个或多个程序，所述一个或多个程序包括用于执行上述路网拥堵关键节点识别方法的指令。
[0027]
本发明的另一个方面，提供了一种计算机可读存储介质，包括供电子设备的一个或多个处理器执行的一个或多个程序，所述一个或多个程序包括用于执行上述路网拥堵关键节点识别方法的指令。
[0028]
与现有技术相比，本发明具有以下优点：
[0029]
(1)识别精度高：基于交通路网原始数据构建具有多个节点和连边的交通网络，通过k-shell分解确定多层邻域内的邻居节点并计算各节点的影响度评价指标，基于影响度评价指标，实现路网拥堵关键节点的识别，本方法基于多层邻域内的邻居节点计算影响度评价指标，结合了交通路网的拓扑特性和交通车流的特性，深度挖掘网络中的关键节点，提高了识别精度。
[0030]
(2)运算复杂度低：本发明的节点重要性识别是通过计算节点的影响函数来确定的，而在网络建模时，将节点的邻居节点集，广度优先的邻居节点搜索算法等信息封装进节
点的信息中，因而计算节点的影响函数只需要简单的运算即可，极大降低了运算复杂度。
附图说明
[0031]
图1为实施例1中路网拥堵关键节点识别方法的流程图；
[0032]
图2为曼哈顿路网在双对数坐标下的度分布概率图；
[0033]
图3为sir仿真模型重复运行1000次下感染数量排名前十的节点每个步长中平均感染的节点数分布图。
具体实施方式
[0034]
下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本发明的一部分实施例，而不是全部实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动的前提下所获得的所有其他实施例，都应属于本发明保护的范围。
[0035]
实施例1
[0036]
如图1所述，针对现有方案复杂路网中未能有考虑路网拥堵传播因素的问题，本实施例提供了一种路网拥堵关键节点识别方法，结合交通拥堵特点对k-shell算法进行改进，并针对路网特性设计一种新的重要节点排序方式，实现拥堵路网下关键节点的准确识别。本发明能够以较低的运算复杂度和较高的计算精度，针对交通复杂路网交通拥堵重要节点进行综合分析，进行深度挖掘网络中的关键节点，具有很强的实用性。
[0037]
本方法包括如下步骤：
[0038]
步骤s1，收集现实复杂路网数据，包括路网的节点和连边信息，在本发明中，路口被建模成网络模型中的节点，连接路口的道路被建模成节点间的边。
[0039]
其中节点集定义为：
[0040]
v(g)＝{v1,v2,v3,
……
vn}
[0041]
边集定义为：
[0042]
e(g)＝{e1,e2,e3,
……
,en}
[0043]
步骤s2，对复杂路网中的节点类进行了封装，生成路网网络，并将节点的编号，度，邻居节点集，节点所属的ks层，sir仿真状态值纳入节点的属性中。
[0044]
步骤s3，对所述的复杂网络模型进行封装，将k-shell分解方法，基于广度优先的邻居节点集搜索方法，对复杂网络模型应用sir传播模型方法等纳入网络模型函数。对节点类构成的网络进行k-shell分解，节点都被分配到不同的ks层中，确定每个节点的ks值，并基于广度优先的搜索策略，确定每个节点三层邻域内的所有节点neighbor_0，neighbor_1，neighbor_2。
[0045]
步骤s4，针对每个节点i，计算一层邻居节点的影响函数s1＝∑
neighbor_0
β，其中neighbor_0为节点i的一层邻居节点，β为sir模型中的传播概率，对二层邻居节点的影响函数其中neighbor_1为节点i的二层邻居节点，β为sir模型中的传播概率，εi为节点i到neighbor_1中每个节点的所有路径，d为节点之间的路径长度，本发明把节点之间的连边设定为没有长度的量纲，因此对二层邻居节点路径长度d设定为2。
对三层邻居节点的影响函数其中neighbor_2为节点i的三层邻居节点，β为sir模型中的传播概率，εi为节点i到neighbor_2中每个节点的所有路径，d为节点之间的路径长度，三层节点的距离设置为3。一个节点i的总影响函数是对三层邻居节点影响的总和，总影响函数表示为s＝s1+s2+s3，其中s1，s2，s3即为上述三层影响函数。基于以上步骤对网络中每个节点计算总影响函数s。
[0046]
步骤s5，复杂网络节点重要性排序方式，即为：先输出ks值大的节点序号，对于同一ks值的节点，先输出总影响函数s大的节点序号，先输出的节点即为在交通拥堵背景下的路网重要节点。
[0047]
一种路网拥堵关键节点识别方法的实施方案如下：
[0048]
step1：实验对象选取与数据集收集。秉持着实验对象的普遍性和代表性，本发明选择了路网复杂度研究中的常被选取的对象——纽约曼哈顿。曼哈顿路网形状规整，街道交错横平竖直，而且通过纽约市打车数据开源网站，其路网的数据集便于获得，其中包括节点数据和边数据，节点csv数据包含3列，分别为节点编号(number)，纬度(latitude)，经度(longitude)。边csv数据包括两列，分别为源节点(source id)，目标节点(target id)，曼哈顿路网数据中共有4091个节点和9452条边。
[0049]
step2：对路网数据进行建模。在原始数据的基础上，本发明首先建立了复杂无向路网模型，然后创建了节点类，对节点的编号，度，邻居节点集，节点所属的ks值，sir仿真状态值进行了封装，便于后续步骤的调用。然后，本发明还针对拓扑指标对路网的复杂网络特性进行分析，图2为路网在双对数坐标系下的度分布，可以发现曼哈顿路网的度分布较好遵循了幂率，p(k≥x)
∝
x-μ
，经过matlab幂率拟合得到μ近似为4.934，在95％的置信区间为[6.952,2.917]，这表明曼哈顿路网是一个无标度网络。无标度特性是复杂网络的重要性质，曼哈顿路网具有明显的无标度特性表明了本实例选用其作为实验对象的代表意义。
[0050]
step3：曼哈顿路网k-shell分解。本步完成基于k-shell方法的路网结构分解，通过不断递归地剥离网络中度数小于或等于ks的节点，具体来说，从度指标的角度分析，度数为1的节点是网络中最不重要的节点，因此首先将度数1的节点及其连边从网络中删除。删除操作进行之后的网络中会出现新的度数为1的节点，接着将这些新出现的度数为1的节点及其连边删除。重复上述操作，直到网络中不再新出现度数为1的节点为止。此时所有被删除的节点构成第一层，即1-shell节点的ks值等于1。剩下的网络中，每个节点的度数至少为2。继续重复上述删除操作，得到ks值等于2的第二层，即2-shell。依此类推，直到网络中所有的节点都被赋予ks值。
[0051]
step4：基于交通拥堵特性的影响函数计算。本步骤计算在交通拥堵背景下的节点影响函数，根据发明技术路线中的定义，需要统计节点对三层邻域内的所有节点的影响函数。定义节点三层邻居节点集合分别为neighbor_0，neighbor_1，neighbor_2。对不同邻域内节点和邻居节点采用不同的处理策略。对邻居节点的评分函数s1为∑
neighbor_0
β，为对二层邻居节点的影响函数其中neighbor_1为节点i的二层邻居节点，β为sir模型中的传播概率，εi为节点i到neighbor_1中每个节点的所有路径，d为节点之间的路径长度，本发明把节点之间的连边设定为没有长度的量纲，因此对二层邻居节
点路径长度d设定为2。对三层邻居节点的影响函数其中neighbor_2为节点i的三层邻居节点，β为sir模型中的传播概率，εi为节点i到neighbor_2中每个节点的所有路径，d为节点之间的路径长度，三层节点的距离设置为3。一个节点i的总影响函数是对三层邻居节点影响的总和，总影响函数表示为s＝s1+s2+s3。
[0052]
step5：本实例将sir仿真模型重复运行1000次，记录每个节点每个步长中平均感染的节点数，其排序前10的节点如图3所示，由图可知，相同步长中纵坐标值越高，节点的传染性越强，即节点越重要。图3显示在sir模型中传染性最强的两个节点分别是3556和3226。
[0053]
本发明针对当前复杂路网中未能有考虑路网拥堵传播因素的问题提供了一种路网拥堵关键节点识别方法，结合了交通路网的拓扑特性和交通车流的特性，可以准确识别交通拥堵情况下的路网关键节点。
[0054]
实施例2
[0055]
本实施例提供了一种电子设备，包括：一个或多个处理器以及存储器，所述存储器内储存有一个或多个程序，所述一个或多个程序包括用于执行如实施例1所述路网拥堵关键节点识别方法的指令。
[0056]
实施例3
[0057]
本实施例提供了一种计算机可读存储介质，包括供电子设备的一个或多个处理器执行的一个或多个程序，所述一个或多个程序包括用于执行如实施例1所述路网拥堵关键节点识别方法的指令。
[0058]
以上所述，仅为本发明的具体实施方式，但本发明的保护范围并不局限于此，任何熟悉本技术领域的技术人员在本发明揭露的技术范围内，可轻易想到各种等效的修改或替换，这些修改或替换都应涵盖在本发明的保护范围之内。因此，本发明的保护范围应以权利要求的保护范围为准。

技术特征：
1.一种路网拥堵关键节点识别方法，其特征在于，包括如下步骤：获取交通路网原始数据，通过网络建模获取包括多个节点和连边的交通网络；针对所述交通网络进行k-shell分解，获取各节点的多层邻域内的邻居节点；针对每个节点，基于多层邻域内的邻居节点计算影响度评价指标，基于所述影响度评价指标获取拥堵关键节点，实现路网拥堵关键节点的识别。2.根据权利要求1所述的一种路网拥堵关键节点识别方法，其特征在于，每个所述的节点包括如下信息：当前节点的度、邻居节点信息、唯一标识信息、节点对应的ks层以及sir仿真状态值信息。3.根据权利要求2所述的一种路网拥堵关键节点识别方法，其特征在于，所述的拥堵关键节点的获取包括如下步骤：根据各节点的影响度评价指标和所属ks层对各个节点进行排序，获取所述拥堵关键节点。4.根据权利要求1所述的一种路网拥堵关键节点识别方法，其特征在于，通过网络建模获取包括多个节点和连边的交通网络的过程包括如下步骤：将实际环境中的路口建模为所述交通网络中的节点，将实际环境中的道路建模为所述交通网络中的连边。5.根据权利要求1所述的一种路网拥堵关键节点识别方法，其特征在于，所述的邻居节点的确定过程包括如下步骤：通过对所述交通网络进行k-shell分解，递归地剥离所述交通网络中的各个节点，将各个节点分配到不同的ks层中，基于预设的搜索策略确定当前节点多层邻域内的邻居节点。6.根据权利要求5所述的一种路网拥堵关键节点识别方法，其特征在于，所述的预设的搜索策略为广度优先的搜索策略。7.根据权利要求1所述的一种路网拥堵关键节点识别方法，其特征在于，邻居节点的影响度评价指标采用下式计算：s＝∑s
ii
式中，s为当前节点的影响度评价指标，s1为第一层邻居节点的影响度评价指标，s
n
为第n层邻居节点的影响度评价指标，其中，n>1，β为sir模型中的传播概率，neighbor_n-1为当前节点的n层邻居节点，εi为当前节点到neighbor_n-1中每个节点的所有路径，d为节点之间的路径长度。8.根据权利要求1所述的一种路网拥堵关键节点识别方法，其特征在于，所述的交通网络是无向且无权的网络。9.一种电子设备，其特征在于，包括：一个或多个处理器以及存储器，所述存储器内储存有一个或多个程序，所述一个或多个程序包括用于执行如权利要求1-8任一所述路网拥堵关键节点识别方法的指令。
10.一种计算机可读存储介质，其特征在于，包括供电子设备的一个或多个处理器执行的一个或多个程序，所述一个或多个程序包括用于执行如权利要求1-8任一所述路网拥堵关键节点识别方法的指令。

技术总结
本发明涉及一种路网拥堵关键节点识别方法、设备、介质，包括以下步骤：1)收集真实路网数据并进行路网建模：2)基于邻居节点集搜索方法，对复杂网络模型应用SIR传播模型方法等纳入网络模型函数；3)对原始复杂路网进行k-shell分解，保存每个节点的ks层并确定其三层内的邻居节点集；4)根据交通拥堵特性计算每个节点的三层影响函数和总影响函数；5)根据每个节点的ks层和总影响函数值确定其在交通拥堵情境下的重要程度。与现有技术相比，本发明改进的k-shell关键节点识别方法结合了交通路网的拓扑特性和交通车流的特性，可以准确识别交通拥堵情况下的路网关键节点。通拥堵情况下的路网关键节点。通拥堵情况下的路网关键节点。


技术研发人员：李莉 龙旭明 赵慧 龚炜
受保护的技术使用者：同济大学
技术研发日：2023.02.28
技术公布日：2023/5/16