复杂网络视角下的道路网络建模与分析

周 波,毛勇超，周 微，3

(1.新一代人工智能技术应用交通运输行业研发中心，杭州 310023；2.浙江工业大学 信息工程学院，杭州 310023；3.浙江交通职业技术学院，杭州 311112)

0 引 言

现实世界很多自然现象其实是一个极度复杂的系统，复杂系统描述了真实的物理世界，例如气候变化、生命进化等自然现象，这些都与人类生活息息相关。近年来，借助复杂网络来研究复杂系统已经成为学术界的主流趋势，复杂网络将复杂系统中的个体理解为节点，复杂系统中个体之间的相互作用以连边来表示，复杂网络在部分复杂系统领域中表现出了卓越的性能，例如社交网络分析、蛋白质分子预测、病毒传播拦截等领域。复杂网络的研究起源于图论，但早期的图论研究集中于用精确数学模型来构建图。进入21世纪，以WS小世界网络和BA无标度网络的研究开启了复杂网络的新纪元，越来越多的研究表明，真实世界的网络既不是完全随机的，也不是规则的网络。例如在社交网络中，多数个体的好友个数是几乎一致的，只有极少数个体的好友个数是非常庞大的，例如明星、演员等好友个数可能是以百万来记，但普通人的好友个数是一百个左右。

网络科学的一个核心主题就是揭示不同网络之间的共性特征，不同领域内的复杂网络表现出不同的特性，例如网页连接网络表现出小世界特性[1]，科学引文网络表现出无标度特性[2]。复杂网络已经逐渐深刻的影响人们对世界的理解，2021年全球顶尖科研机构DeepMind开源了用于蛋白质结构预测的AlphaFold系统，该系统以复杂网络视角构建蛋白质结构图，进行未知蛋白质结构的预测。随着社会活动越来越复杂，与国计民生息息相关的道路交通网络、电力网络、通信网络规模越来越大，其复杂性的特点也日益影响地区甚至国家的安全。例如，对电网的定点攻击可以造成电力网络瘫痪、对通信网络少数关键基站干扰可以造成通信瘫痪，航空网络的全球运营使得人们可以一天之内到达世界各个角落。

道路与人类生活息息相关，道路网络表现出高复杂性和非线性，但当前对道路网络的建模和分析主要集中于特定案例的研究。例如谌微微等基于站点的度中心性、紧密中心性、介数中心性三个中心性指标对轨道交通网络中站点的重要程度进行了评价[3]。例如刘海旭等根据复杂网络的脆弱性定义了城市轨道交通网络脆弱性概念，并且构建了城市轨道交通网络脆弱性评估模型[4]。徐敏等为定量分析地铁车站的重要性，建立考虑时间变化的网络节点评价模型，分析网络对节点重要度的影响情况，进而给出网络节点重要度的定义和评价方法[5]。孙立山等基于复杂网络的稳定性对北京市轨道交通网络进行了特性分析[6]，构建了北京市轨道交通复杂网络模型和客流动态传播模型，仿真分析了节点度、平均路径长度、聚类系数、网络直径、网络效率等特征参数值和其分布规律。

以上研究均集中于道路网络单个特性的研究，并没有给出不同道路网络的更广泛特性分析，并且由于交通源数据的大规模异构性特点，以上研究也没给出源数据的处理方法。本文将借助Gephi对道路网络进行建模并可视化，展示不同道路网络的复杂特性，以复杂网络视角展示道路网络更多的特性。本研究可以为后续交通流量预测、信号灯控制等研究方向提供模型支撑。本文所研究的道路网络为公路路网，不包含水路、铁路、航空等异质网络。本文中除非特别说明，否则道路网络均指区域内公路路网。对水路、铁路、航空等多种类的异质网络研究是我们今后的研究方向。

1 道路网络建模

道路网络是一种特定领域的复杂网络，具有复杂网络的所有特性，但也表现出自身独特的性质。以某区域为例，将该区域内的居住场所、公司、景区等抽象为平面区域中的节点，节点与节点之间如果存在具有红绿灯的道路则将节点之间用一根线来表示，本文只考虑拥有红绿灯的道路可以为后续工作提供符合实际的模型，因为两点之间如果不存在红绿灯的道路，说明两节点之间流量较小，对整个区域的道路网络流量贡献较少，研究意义不大。因此，整个区域的道路网络构建成了一个无权、无向的网络，记为：G(V，E)，其中V表示图中的所有节点的集合，E表示图中点与点之间所有连边的集合。|V|表示节点的个数，|E|表示连边的个数。Ni(G)表示图G中节点vi的邻居个数，记为节点Ni的度。图G的度分布记为P(k)，其表示的含义为随机从图中选择一个节点，该节点的度为k的概率。对于一个完全随机的道路网络，两节点之间存在连边的概率记为p，则随机道路网络的度分布为：

(1)

在公式(1)[7]中，令λ=Np，对于一个较大区域，例如某城市来说N-1≈N(这种近似将给我们的理论分析带来极大便利，对于一个大城市来说，顶点的个数数以万计，减少一个顶点对网络整体的影响极其有限)，则：

(2)

当区域内的节点的个数足够大的时候，由极限知识可得：

(3)

(4)

(5)

因此，当区域足够大，例如某个中等规模的城市，区域内的节点个数N足够大时，随机道路网络的度分布近似为泊松分布，即：

(6)

随机道路网络的平均度即节点度的期望：

(7)

则道路网络的平均距离为公式(8)，其中lij为网络中节点i与节点j之间的最短距离：

(8)

网络中节点vi的聚类系数，其中Ni表示节点vi的邻居节点中存在连边的个数：

(9)

则整个网络的聚类系数为：

(10)

2 数据集的描述

本文将使用三个道路数据集进行建模并可视化，进而得出道路网络的相应特征。因为道路数据集具有一定的机密性，一个省甚至一个城市的道路数据可以分析出道路网络的交通枢纽和关键道路，对枢纽和关键道路的破坏可以造成整个道路网络的瘫痪，因此本文通过全美道路数据网站获取美国三个道路网络数据集，其中，数据集RoadNet-CA[8]是美国加利福尼亚州的道路网络，RoadNet-PA[8]是美国宾西法尼亚州的道路网络，RoadNet-TX是美国出租车行驶道路网络[8]。三个网络均是无向的道路网络。三个数据集的基本特性如表1所示：

表1 道路网络数据集节点和连边个数

从表1可以看出，道路网络数据集极其庞大，是典型的大数据系统，对大数据的分析不能用传统的解析方法，需要借助于计算机以统计的数学方法对其进行研究。

3 实验设置

三个数据集的原始格式均为txt的文本格式。本研究首先基于Visual Studio 2019编译器利用python3.7编写格式转化程序，将.txt文本格式的数据集转换成Graphml格式。该转化代码包含三部分，第一部分将txt文本格式的源文件提取出连边并以列表形式存储，同时将连边保存在硬盘驱动器上以二进制方式存储；第二部分将列表形式的连边导入Nextworkx，利用Networkx生成网络图的形式；第三部分将网络图形式的数据集输出为Graphml格式的数据集并保存在本地硬盘。所做的实验均基于Windows平台，平台采用英特尔(Intel)i7-8核处理器。

4 实验结果分析

三个数据集的可视化结果如图1～图3所示，因为网络包含的节点和连边较大，限于篇幅，本文利用Fruchterman-Reingold可视化技术对图片做了压缩处理，Fruchterman-Reingold是一种对大数据图的可视化优化方法[9]。三个道路网络的Fruchterman-Reingold重力参数均设置为5.0，速度参数均设置为4.0。

图1 RoadNet-CA道路网络可视化

图2 RoadNet-PA道路网络可视化

图3 RoadNet-TX道路网络可视化

图中节点的大小与节点的度成正比，节点的度越大，则可视化出来的节点越大。从图中可以看出来，道路网络是非常密集的，网络的度分布统计如表2所示，三个道路网络的密度统计如表3所示。

从表2可以看出，道路网络的节点度大量集中在1至4。

K-core分解算法是用于获取网络中比较重要节点的一种剥离算法[10]，网络中重要节点个数往往所占比例较少，但对网络结构的影响举足轻重，例如在信息传播网、流行病传播网、电力能源网等领域，对少数k值较大的节点进行攻击，可以造成整个网络的瘫痪。可视化网络的最大k-core如图4～图6所示。

表2 道路网络度分布统计

图4 CA网络的3-core结构

图5 PA网络的3-core结构

图6 TX网络的3-core结构

由图4～图6可以看出，节点度较大的节点直径较大，但这些大度节点的个数是非常小的，并且道路网络的最内层核结构是非常“破碎的”，有许多规模不大的全连接结构，构成紧密的“团簇”结构，进一步可以得出3-core结构内的点至少有3个邻居节点属于3-core结构，最后可以看到，即使网络中若干节点的度值较大(例如表2所示CA网络中存在度值为10的节点)，但这些节点的最大核值不会超过3。三个道路网络的特性如表3所示：

表3 道路网络的统计特性

通过以上的分析，我们可以得出道路网络区别于其他复杂网络有其自身的一些特性。道路网络的平均度较小，这与我们的实际感受是符合的，在道路网络中一个节点，例如居住小区，其出去的道路往往只有2～3条路，最多可能就是4条路出去，不太可能存在大量道路都连到一个节点上的情况。从表3中可以看出，道路网络的直径反映了道路的网络的大小，对于一个特大城市来说，网络直径往往更大，例如PA网络表示的美国宾西法尼亚州实际上比CA网络表示的美国加利福尼亚州要小，美国加利福尼亚州的发达程度也要远远大于宾西法尼亚州。道路网络的最大k-core结构较小，最大k-core结构所包含的节点和连边在整个网络中的比例也非常小，这些节点往往是整个网络的关键节点，这些节点的坍塌将造成整个网络的坍塌，网络坍塌意味着网络中存在大量节点相互之间无法到达，如果在战争年代，这些k值较大的节点就是咽喉要道。通过对大数据规模的道路网络可视化特性统计，本文归纳出道路网络的一些性质：

(1) 道路网络结构的复杂性。本文只考虑无权、无向的单连边道路网络，但在实际场景中，两个节点之间可能存在着不同类型的道路，例如城市中出发地和目的地之间存在着城市快速路的连接，也存在普通道路连接，甚至存在水路、地铁等不同性质的道路。本文简化道路网络的异构特性，主要建模道路网络，即使是简化后的道路网络从可视化结果来看，这个网络规模也足够庞大，对计算机的运行效率带来极大挑战。

(2) 道路网络的小k特性。道路网络的最大k-core的k值往往并不大，并且最大k-core结构的节点和连边占比也非常小，表明在道路网络中，对于整个网络结构有影响的关键节点和关键连边是非常有限的。如果从战略角度来看，破坏这些节点和连边就能让整个区域交通瘫痪，如果从城市管理角度来看，加强这些节点和连边的交通管控，就能让整个城市交通更加顺畅。

5 结 语

本文利用Gephi和Networkx构建并可视化道路网络的结构，编写数据格式变换程序，最后分析道路网络的特性，得出道路网络具有高复杂性、小k值的特性，同时发现真实的道路网络与随机道路网络表现出差异性。本文的主要贡献值在于总结了道路网络的共有特性为后续研究提供借鉴。

交通道路网络是由大量节点通过道路连接构造而成，本身具有复杂性、非线性、非封闭性和突变性的特征。本文通过对道路网络进行建模可视化，对比道路网络所拥有的特性，可以为后续对道路网络的流量预测、动态分析等研究提供前期模型和数据支撑。本文的研究对道路网络的后续研究提供了思考的起点，例如，从出发地到目的地，判断某条路径拥挤，并不需要该路径所包含的所有路段都拥挤，只要有一个路段拥挤甚至某一点拥堵就够了。如果在道路网络中考虑交通流的因素，可以构造一个权重的道路网络，就可以研究道路的交通流量问题，这个问题此前已经被大量研究，也涌现出了新颖的理论知识，但从实际的道路流量来看，理论和实际还存在着巨大的鸿沟。直观上的感受道路网络的连边越多，道路流量将变小，实际的体验是某城市中原先的某个道路并不拥堵，但是新开辟了一条道路以后反而变得更拥挤。这种理论和实际存在差距的特性在道路网络研究中广泛存在，说明道路网络是一个高度复杂的系统，具有多学科交叉融合的特点。

随着时间的推移，道路数据越来越庞大，如何高效快速处理大规模图数据又是一个新型和热点的研究方向。