基于小世界模型的交通网络拥堵状态研究

赵 军

(江苏食品职业技术学院信息工程系,江苏 淮安 223003)

基于小世界模型的交通网络拥堵状态研究

赵 军

(江苏食品职业技术学院信息工程系,江苏 淮安 223003)

在对海量数据进行分析和利用的同时，数据挖掘作为一种首选的工具已经普遍应用到各个领域中。为了解决交通网络中车辆拥堵的状态，在利用复杂网络中的小世界模型建立交通网络模型时，借助数据挖掘中的谱聚类方法对交通网络的拥堵状态进行分析，通过计算道路的平均拥堵时间控制交通灯的放行时间，使得整个交通网络不出现异常拥堵情况。采用NetLogo 5.0.3作为试验平台，对模拟交通网络进行分析，成功实现对交通流的调节，避免了长时间拥堵情况的发生。

交通网络 复杂网络 数据挖掘 小世界模型 拥堵 NetLogo

0 引言

随着城市交通在社会经济发展过程中的作用越来越重要，交通带来的城市拥堵问题也日益突出。为了更好地改善城市交通的整体状况，研究学者从多个方面对交通问题进行分析，其中一个非常重要的方向是基于数据挖掘和系统理论的复杂网络进行深入分析。

目前，有关车辆的数量增加与交通道路扩张的相互影响的研究，主要从以下4个方面展开：①城市交通拥堵的新城以及车辆行为在道路上的扩散规律；②道路的规划与车辆行为需求的影响；③交通控制与道路、车辆的分布情况之间的关系；④缓解城市拥堵的非经验型传播机制。

通过对以上几个方面的深入研究，越来越多的研究将车辆行为的复杂性与交通网络的复杂性相结合，利用动力学方法研究城市交通网络的拥堵原理、机制和解决方法。从复杂网络的研究可以看出，利用相互关联节点以及节点之间的关系,可以对互联网、蛋白质网、流行病网以及交通网等多种现实问题进行研究，设计的领域也包括诸如数学、生物学、物理学、社会科学、医学等。随着研究的不断深入，越来越多的问题都可以借助复杂网络的模型进行仿真与分析，成为一门交叉能力较强的学科。

同时，由于复杂网络中的规律性往往是通过对大量数据的分析后得到的，并且有的规律性还需要数据去验证，因此，借助数据挖掘技术可以对利用复杂网络研究的模型进行验证。通过这种结合的方法,可以在一定程度上提高复杂网络模型的可信度，更加有利于模型的推广。

1 交通网络复杂网络模型

在模拟交通状况的复杂网络模型中，常用小世界模型进行分析。小世界模型通过分析临近节点之间的关联性，构造了具有一定拓扑结构的随机网络，网络中的临近节点通过某一小概率的几率相互连接，形成局部无规律性而整体存在显著规律的网络。这种模型可以用于描述交通网络中的车辆行为，即车辆从一个节点(通常用路口表示交通网络中的节点)出发达到另外一个节点的可能性。

利用这种模型描述的交通网络具有以下特点。

① 将交通网络的道路复杂性描述为节点之间的链接关系，利用节点的高聚类性可以对交通网络的拓扑结构进行可靠性分析，有助于分析交通网络在各种交通流的影响下是否具有稳定性。

② 小世界网络的平均最小距离比较容易分析，可以使得在模拟交通网时保持较好的动态性和偏好依附性。这一点也比较接近车辆在交通网络中的实际运行机制。

同时，为了描述交通网络的动力学性质，很多学者也对交通网络的动力学特征进行了大量研究。其中，最具代表性的是陈克寒[1]对交通网络中的节点平均度进行分析，得到了交通网络在无标度网络情况下比随机网络更加容易发生拥堵的结论。而Luo[2]分析了无标度网络的拓扑结构发生变化时交通网络拥堵状况恶化的规律性。徐杨[3]通过引入网络效率的概念，进一步分析了在无标度情况下的网络全局效率与节点、边之间的关系。Seaton[4]通过对波士顿与维也纳两个城市街道网络进行网络模拟发现，小世界模型的各种性质更加符合交通网络的实际情况，对具有高度自组织性的交通网络的无标度性进行了论证。

在深入研究交通网络的动力学特性时，Ghandour[5]对互联网和交通网进行了对比性研究，发现两者均具有明显的波动性，并且存在的噪声也具有周期性。因此,利用带有噪声的小世界网络进行交通网络动力学分析是可行的。后来Arenas[6]对交通网络中的信息传递机制进行了分析，发现交通网络中的车辆符合信息传播的规律性，并且随着网络中节点最大介数与交通流的状态存在一定的位置关系。为了对交通网络的信息传递进行动态分析，李远成[7]利用二阶邻居搜索路由方法进行交通网中的车辆行为信息传播，也就是1/f噪声，从而在交通网络的信息传递与交通拥堵之间建立了关系。

2 交通网路动态模型建立

利用小世界模型对交通网络进行模拟时，首先要对道路的方向性、路段的长度和车辆滞留时间等因素进行定义。因此，交通网络符合有向加权图的基本特点，可以对该网路模型做如下定义[8]。交通网络G(V,E,W)表示由交通路口(节点)V、道路E(边)以及道路的权重(边的权重)W组成。该网络可以使用邻接矩阵A(aij)表示，其中矩阵元素定义为：

(1)

当节点i≠j时，如果两个节点之间存在连接，则元素为1，否则为0。

对网络的权值也同样可以利用矩阵B(bij)表示，其中矩阵元素定义为：

(2)

当节点i≠j且两者之间存在边的情况下，该边的权重为wi，否则为+∞。

为了研究车辆在该网络中的行为规律，对车辆的行为选择进行了仿真。文献[9]利用改进的二项分布模拟具有无标度特性的网络，将节点的最小度的求解方法转换为小世界网络度的分布情况，即：

式中：N为网络中的节点数量；p为节点之间相连接的概率；k为网络中的边的数量；K为每个节点的最小度；c为网络的簇系数。

在该交通网络中，车辆动态变化的过程可以利用信息在该小世界网络中进行传递的过程来模拟，并且利用信息迟滞的现象模拟交通网络的交通拥堵状况。因此，对交通网络的动力学分析，可以借助无标度特性网络的最短路由策略进行分析，可以利用局部和全局网络的信息传递特点进行计算。

本文采用局部信息路由策略对网络模型的信息传递进行定义：在拥有信息量为N的网络中，每个单位时间中的信息都希望从源点向目的点靠近，并且带有随机性，每个邻接节点在单位时间内可以容纳的信息量为M。因此，在信息传递的过程中，需要建立以一定概率情况下的控制，本文采用静态局部定义法表示该概率，即：

(3)

可以看出，对于节点度越大的节点，越不容易接收新的信息量。

同时，为了描述车辆在道路上运动的阻碍性，本文利用电阻距离定义两节点之间的距离。这种距离模型有效地模拟了交通网络中道路拥堵状况对车辆形式的阻碍性，类似于电流在通过电阻时的热能损耗。

首先，将交通网络G(V,E,W)中的电阻距离矩阵表示为矩阵B(bij)的拉普拉斯谱矩阵L=(lij)，于是两节点之间的电阻距离可以表示为：

(4)

且有：

L=D-H

(5)

式中：H为图G(V,E,W)的邻接矩阵。

(6)

式中：vki为第k个特征值对应特征向量中第i个元素的个数；vkj为第k个特征值对应特征向量中第j个元素的个数；λk为谱矩阵的特征值第k个大的特征值。

3 节点距离的相似性

本文在描述交通网络的拥堵状态时，使用节点电阻距离的相似性表示道路拥堵的传递性，这一概念可以在文献[10]中得到验证;并给出了节点之间电阻距离的计算方法。但是由于该方法在小世界模型中存在局部收敛的特性，造成电阻距离变化引起节点信息量变化后对电阻距离产生反作用，因此不能描述动态的交通网络。本文引入了利用数据挖掘中的聚类分析对节点的信息量和电阻距离进行分类的方法，结合谱图理论的划分原理，量化交通网络中道路的拥堵状态，即电阻距离的动态变化。

首先，通过NP问题代替交通网络中道路拥堵造成的信息传递问题，利用谱聚类的方法寻求最优划分，也就是寻找一个无线逼近状态对图进行划分。本文的设计思想是利用最小割集准则建立目标函数：

(7)

而规范割集准则的目标函数为：

(8)

建立该目标函数的目的是将交通网络图划分为A、B两个子图。其中一个子图是从节点i到节点j消耗信息量最少的子图，而另一个子图是消耗信息量最大的，用于表示交通拥堵的代价。

其次，对子图划分采用谱聚类的方法，并利用高斯核函数表示相似距离：

(9)式中：‖vi-vj‖为两个节点之间的欧式距离；σ为常数。

最后，结合本文提出的小世界网络模型中局部搜索概率的方法，对图中的电阻距离进行聚类。步骤如下。

① 初始化图G(V,E,W)的邻接矩阵H与聚类个数k。

② 利用矩阵H的n个k维行向量作为数据对象集。

③ 使用k-means方法对H的行向量进行聚类。

④ 只有当H的行向量属于其中一个簇时,才将原始i向量归为一个电阻聚类。

⑤ 返回第②步执行，直到所有行向量被分析。

4 试验

本文利用NetLogo5.0.3作为试验平台，模拟了125辆随机运行的车辆在30个路口的随机运动，结合本文提出的小世界模型建立车辆与道路关系网络。节点表示车辆，两个节点之间有变化的链接说明可以有直接连接的道路。模型如图1所示。

图1 初始化小世界模型Fig.1 Initialization of the small world model

在置信度为0.149的情况下，得到平均最小路径长度为3.958。以该长度作为交通网络中道路拥堵时间的最大值，反映到现实情况为交通灯的平均等待时间，可以验证以某一时刻为基准以后时刻路口的交通拥堵状态。系统仿真结果如图2所示。图2(b)中，纵坐标表示车辆平均速度，为一个相对量，其中，0表示车辆静止，1表示车辆最高限速。图2(c)中，纵坐标表示车辆平均等待时间，也为一个相对量。

图2 系统仿真结果Fig.2 The system simulation results

在NetLogo中，利用以下4个参数对建立起来的模型进行控制。

① 一个节点重新连接网络的性能，表示小世界模型中的某个节点的权重，如果不改变初始度，默认为模型中节点的度。

② 聚类系数，这个指标只当模型开始运行后才会变化，表示共有多少聚类产生。

③ 平均路径长度，表示有向小世界图中的所有节点达到任何节点的平均路径长度。每经过一个节点，长度增加1，这里取平均长度。

④ 所有节点重新连接网络的性能，表示小世界模型中的所有节点的权重平均值，如果不改变初始度，默认为模型中所有节点的平均度。

可以通过3个观察窗对系统动态运行过程中的参数变化进行观察，分别为：①在交通网络中遇到红灯停止的车辆；②所有车辆的平均速度；③所有车辆的平均等待红灯时间。

在试验中，共计运行1 220个单位时间。可以看到，每个路口的等待时间都比较均匀，也就是没有造成非常拥堵的状况。

5 结束语

通过利用小世界模型对交通网络的车流量进行模拟，并借助数据挖掘中的谱聚类方法计算交通流中的节点拥挤程度，采用节点电阻距离的相似性表示道路拥堵的传递性。给出了节点之间电阻距离的计算方法，利用这种方法可以对交通枢纽进行流量控制。借助NetLogo平台对本文提出的方法进行仿真，仿真结果表明，采用该方法对交通进行调节后，可以有效避免长时间的交通拥堵状况。

[1] 陈克寒，韩盼盼，吴健.基于用户聚类的异构社交网络推荐算法[J].计算机学报，2013,36(2):349-359.

[2] Luo Y,Packirisamy V,Hsu W C，et al. A dynamic performance tuning for speculative threads[C]∥Proceedings of the 36th ACM/IEEE Annual International Symposium on Computer Architecture,Austin,USA,2009:462-473.

[3] 徐杨,张玉林,孙婷婷,等.基于多智能体交通绿波效应分布式协同控制算法[J].软件学报，2012,23(11):2937-2945.

[4] Seaton K A，Hackett L M.Station trains and small-world networks[J].Physical A,2004,339(3-4):635-644.

[5] Ghandour W J，Skkary H，Masri W.The potential of using dynamic information flow analysis in data value prediction[C]∥Proceedings of the 19th International Conference on Parallel Architectures and Compilation Techniques.Vienna,Austria,2010:422-431.

[6] Arenas A,Iacute,A Az-Guilera,et al.Communication in networks with hierarchical branching[J].Physical Review Letters,2001,86(14):3196.

[7] 李远成，阴培培，赵银亮.基于模糊聚类的推测多线程划分算法[J].计算机学报，2014,36(2):589-592.

[8] Zhang X C,You Q Z.Clusterability analysis and incremental sampling for Nyström extension based spectral clustering[C]∥Proceedings of the IEEE 11th Int’l Conerence on Data Mining(ICDM),2011:942-951.

[9] 金弟,杨博,刘杰,等.复杂网络簇结构探测——基于随机游走的蚁群算法[J].软件学报,2012,23(3):451-464.

[10]Yan D H,Huang L,Jordan M I.Fast approximate spectral clustering[C]∥Proceedins of the 15th ACM Conference on Knowledge Discovery and Data Mining(SIGKDD),2009:907-916.

Researching the Congestion Status of Transportation Network Based on Small World Model

In analyzing and applying massive data, as the preferred tool, data mining has been popular used in various areas. In order to solve the problem of congestion status of transportation network, in establishing transportation network model by adopting complex network small world model, the method of spectral clustering in data mining is used to analyze the congestion status of transportation network. Through calculating the average congestion time to control the traffic lights, thus abnormal congestion of the transportation network may not appear. With NetLogo 5.0.3 as the experimental platform, the emulated transportation network is analyzed, and the traffic flow is regulated successfully, and long period congestion is avoided.

Transportation network Complex network Data mining Small world model Congestion NetLogo

江苏省高等职业院校国内高级访问学者计划资助项目(编号：2014FX033)；

淮安市科技攻关基金资助项目(编号：HAG2010065、HAS2014021-2、HAS2014025-3)。

TP391

A

10.16086/j.cnki.issn1000-0380.201506005

江苏省住建厅建设科技项目(编号：2014JH20);

修改稿收到日期：2014-12-05。

作者赵军(1971-)，女，2006年获江苏大学计算机技术专业，获硕士学位，副教授、高级工程师；主要从事网络安全、数据挖掘的研究。