影响最大化算法在城市公交网络中的应用研究

李 峰

(中北大学仪器科学与动态测试教育部重点实验室 山西 太原 030051)

0 引 言

近年来，严重的交通拥堵问题成为国内各大城市普遍面临的困扰，且形势日益加剧。而解决这一问题的首选措施即发展以巴士和地铁为代表的城市公共交通，所以对城市公交巴士系统的研究成为了一个热点课题。

已有的多项成果表明[1-3]，城市公交系统可以通过将公交站点抽象为节点，线路/站点间的联系抽象为连边的方式，建模为复杂网络，满足小世界和无标度等基本特征。对此，早期的研究多集中于孤立地考虑单条公交路线或单个停靠站点。然而，城市公交网络正常功能的维持往往在于多条重要线路，单独研究某一线路对城市交通网络建设的实质意义不大。所以，研究网络内所有公交线路间的相互协作与影响，逐渐成为当下探索城市公交系统的主流。基于此，本文以江苏省无锡市公交系统所建模的复杂网络为主体，对影响最大化算法在该系统的应用展开研究，以丰富城市公交网智慧化建设的理论，助力现实公交系统的规划、管理与决策。

1 研究现状

近年来，随着复杂网络理论[4-6]的丰富，城市公交网络研究涵盖了多个方面，包括城市公交网络静态特性的分析和统计、演化生成建模、行为与应用研究等。

其中应用研究还处于起步阶段，主要包括网络中关键站点的探测和网络的设计、优化与控制两方面的内容。第一类研究的出发点是城市公交网络中部分关键站点对于网络的静动态性能影响甚大。例如:影响网络鲁棒性的某些站点一旦失效，将会导致网络连通性的极大降低。基于此，文献[7]根据站点对网络路径长度与换乘次数的综合作用，提出了探测网络换乘关键站点的方法，并通过仿真实验证明了该方法的有效性。第二类研究则是通过调整城市公交网络的结构来实现系统的合理设计与优化，通过在网络运行时对网络施加干预来实现控制等，从而提升网络的整体服务性能和乘客的满意度。由于城市公交网络的线路优化是NP-hard问题[8]，所以现有的多数网络设计与优化研究都是基于启发式的优化规则，如基于聚合物理论而提出的根据乘客出行需求分布数据优化城市公交线路设置的算法[9]。网络控制研究的难点在于该问题的数学建模，如文献[10]中的时变时滞公交线路网络模型，尽管理论推导成立，却过于偏理想化。

到目前为止，基于复杂网络理论的城市公交系统研究尚有很大的探索空间，对于重要站点集、关键线路组的研究更是屈指可数。因此，本文以无锡市公交系统为研究对象，对其进行网络建模，结合复杂网络理论中的影响最大化算法思想，对城市公交系统中的核心路线组进行识别和分析。

2 算法应用

2.1 无锡市公交网络建模及特征分析

城市公交线路一般由站点和站点间的连接路段组成，有上行线和下行线的区分。由于任意站点A若存在路线可达站点B，则同样由站点B也可通过此路线到达站点A，所以，本文以无向化的方式对无锡市公交系统的相关数据进行处理。为保证研究的科学性和真实性，这里对本文数据做如下说明：

(1) 仅采用无锡市内所有的公交路线，不去除环线、旅游线路和夜班车路线等，周围区县线路不在研究范围。

(2) 数据均来源于无锡市公交公司官网。

(3) 采集数据截止日期为2019年3月2日，在此之后公交线路的变动情况不予考虑。

本文选取无锡市共302条公交线路，包括2 360个站点，对其进行公交线路建模和静态特征评估。之后利用影响最大化算法LCIR_AR[11]对网络的抗毁性和平均最短路径做了科学的分析，以证明所选线路组的合理性。

2.1.1无锡市公交线路网络模型的构建

城市公交系统的网络建模主要有两种方式，一种是将停靠站点作为网络节点，若两个站点由同一班车次承载，则建立连边，为无权无向网络；另一种是以公交线路为网络节点，拥有共同停靠站点的两条线路间存在连边，边的权重取决于共同站点的数目，即为加权无向网络。如前所述，本文旨在发现城市的关键线路组，所以主要采用第二种建模方式构建无锡市公交线路网络模型。大致实现流程如图1所示。

图1 无锡市公交线路网络建模实现流程

其中，数据处理部分的格式初始化是指将采集的所有公交线路数据中特殊符号进行统一；数据清洗主要是对周围区县线路予以删除；按需整理则是对公交线路的重新编号。部分处理后的公交线路的数据格式展示如表1所示。

表1 处理后的公交线路数据形式表

最后，利用处理后的公交线路数据对无锡市公交系统进行网络建模。具体建模过程如下：(1) 将公交路线按照编号抽象为网络节点；(2) 对各公交线路间的共同停靠站点进行统计，规定共同停靠站点数大于0的节点间形成链接。建模后的无锡市公交系统可视化如图2所示。

图2 无锡市公交线路网络图

2.1.2网络基本特征分析

由于在实际的发展中，对城市公交线路进行系统设计要求数据有较高的准确性，所以，有效分析和计算其网络模型的静态特征很有必要，这可以在一定程度上促进城市公交网络模型构建与应用的精准化发展。目前描述和度量网络特征的统计量众多，如网络平均度与度分布、平均距离、平均最短路径长度、平均聚类系数、紧密度、连通性等。根据研究需要，本文重点从度分布、平均最短路径长度、平均聚类系数这三个指标对无锡市公交线路网络进行分析。

通过对无锡市公交线路网络的建模，利用networkx工具得出该网络中节点的度分布图如图3所示。节点的度可以理解为某条公交线路可以换乘的路线条数。由图所反映的情况来看，degree∈[0,35]的网络节点所占比例相对较高，即换乘选择较少的公交线路较多，表明无锡市公交系统在边缘线路的建设方面存在一定合理性；而当degree∈[80,120]时，网络节点的度分布近似服从幂律分布，即换乘选择越多的公交线路数量越少，体现出无锡市公交系统相对科学，避免了在线路安排上的冗余以及人力、物力上的浪费。

图3 无锡市公交线路网络的度分布图

由于无锡市公交线路网络是完全连通的，所以任意两点间彼此可达。通过计算得到无锡市公交线路网络的平均最短路径长度为2.002 7，具有小世界特性。换句话说，两条线路之间实现换乘平均需要2次，显示出无锡市公交网络在换乘上的方便性。

在公交线路网络中，平均聚类系数定义为所有节点的聚类系数的平均值。计算得知无锡市公交线路网络的聚类系数为0.569 8，聚集特性良好。与北京的0.632 6、上海的0.654 0、杭州的0.620 5[2]相比，还存在一定差距。为便于查看，将该公交线路网络的基本拓扑特征整理如表2所示。

表2 无锡市公交线路网络的基本拓扑特征

2.2 影响最大化算法

本文选择影响最大化算法LCIR_AR(Local Collective Influence Rank-Adaptive Recalculation Algorithm)[11]来开展研究。该算法是对CIM(Collective Influence Maximization Algorithm)算法[12]的改进，通过调整其影响力节点的选取策略以及引入影响力节点候选集和自适应重新计算思维，提高了CIM算法的性能。描述如算法1所示。

算法1LCIR_AR算法

输入：网络G={V,E}，距离长度l，影响力节点集的规模k，控制参数λ

输出：选取的影响力节点集合S，执行轮数c

开始：

Step1以网络中任意节点i为根节点，利用广度(或深度)遍历其l层所有邻居节点。

Step2根据式(1)-式(3)计算节点i的CI值及LCII值，并将LCII值为0的节点添加到影响力节点候选集Sc。

Step3依次对网络中所有节点执行上述步骤Step 1-Step 2。

Step4初始化c=0。

Step5在网络G中移除Sc内的节点，执行c=c+1。

Step6并对更新网络重复Step 1-Step 5，直至节点候选集的规模达到|Sc|=k/λ。

Step7对候选集Sc中节点按照CI值降序排列，截取Top-k节点加入影响力节点集S。

Step8返回S、c。

结束

(1)

(2)

(3)

式中：di为节点i的度，N(i)表示节点i邻居节点的集合，l为距离节点i的最短路径长度。Ball(i,l)定义为属于以节点i为中心，半径为l的球内的节点集合， ∂Ball(i,l)则表示该球的边界。便于理解，将变量含义示意如图4。

图4 CIM算法的概念标注图

该算法主要有以下优势：(1) 避免了原CIM算法在网络适用中可能出现的富人俱乐部现象，进一步提高了算法在影响力节点识别上的准确度，同时保留了其发掘扮演经纪人角色的低度节点的能力。(2) 受益于局部领袖节点的选取策略、影响力节点候选集和自适应重新计算的思想，算法的执行效率较CIM大幅提升。映射到本文城市公交系统网络的影响力节点识别问题中，则表现为：不仅仅是转乘选择多的公交线路，转乘路线较少的公交线路同样具有被发掘重要性的可能，即该算法能够更准确地挖掘出无锡市公交系统中的重要线路。此外，该算法保证了所选公交线路的分散性，从而使得识别出的核心线路组在现实系统中的实际影响范围更大。最后，高效的执行效率对于处理规模随时会扩张的城市公交网络具有很强的适用性。

2.3 关键公交线路组的识别

2.3.1实验平台及设置

本文实验的硬件环境为：2.50 GHz Intel(R) Core(TM) i5-3210 CPU，4 GB的内存；操作系统为：Windows；开发环境及语言为Python 2.7。影响最大化算法LCIR_AR的参数设置为距离长度l=2，核心线路数k=50，控制参数λ=1。实验主要从两部分展开：首先是所选节点集对网络平均最短路径的影响，其次是对网络连通性的影响。所有实验的比较对象均为随机选择的同等规模的节点集合。鉴于该公交线路网络的密度过高，删除较少节点对网络的连通性基本无影响。所以在第二部分实验中，对网络进行一定的简化处理，仅保留共同停靠站点大于2的连边，以增强效果的可视性。

2.3.2实验结果和分析

在城市公交系统中，遇到人为或者自然的意外而导致某些线路无法正常使用的情况在所难免。这种场景映射到公交线路网络，即为节点失效。站在研究的角度上来说，最常见的处理方式则为删除该失效节点及与之关联的链接。不失一般性，本节实验中，将LCIR_AR算法所选影响力节点集中的所有节点视为失效，对其及其连边进行移除操作，从而分析其对网络平均最短路径和网络连通性的影响。关于LCIR_AR算法的节点选择策略可见算法1，这里不再赘述。为证明该算法在影响力节点选取上的精准性，从公交线路网络中的302个节点中随机选取相同数目的节点作为对比。

(1) 网络平均最短路径实验。此实验中，所用网络为未简化的无锡市公交线路原型网络，两种方式下所选的待移除节点记录如表3所示，表中节点区分先后。图5为依次移除所选节点，网络的平均最短路径变化曲线。

表3 LCIR_AR算法和随机选择的Top-50节点

图5 节点移除与网络平均最短路径长度关系图

由图5可以看出，随着LCIR_AR算法所选网络节点的逐个移除，平均最短路径大致呈增长趋势，而随机选择情况下，网络平均最短路径没有明显的变化。这是因为当某些重要公交线路无法运行时，民众出行的便利性受到影响，换乘/绕道的概率上升，网络的平均最短路径自然加大。对比之下不难发现，同样是网络中50个节点，后者所选出的节点，对于网络平均最短路径的影响更大。也就是说，公交线路存在重要与否的差异，针对性地攻击会比随机破坏，在网络平均最短路径上更有杀伤力。因此，需对公交系统中的多条重要线路加强保护，以维护该城市公交出行的方便度。

(2) 网络连通性实验。如前所述，此实验以简化处理后的无锡市公交线路网络为主体。此时由LCIR_AR算法和随机选择所确定的待移除节点记录如表4所示，节点同样区分先后。随着所选节点的移除，网络的最大连通分量和连通分量个数均会受到影响，变化曲线分别如图6和图7所示。

表4 LCIR_AR算法和随机选择的Top-50节点

图6 节点移除与网络最大连通分量关系图

图7 节点移除与网络连通分量个数关系图

观察图6和图7，可以得出结论：较之于随机选择，从网络中移除LCIR_AR算法所选的影响力节点，网络连通性快速下降，形成多个网络碎片。原因是LCIR_AR算法可以识别公交系统中的若干枢纽线路，对其进行移除后，网络急剧瓦解，系统的运输功能极大受阻或减弱。

综上，影响力最大化算法LCIR_AR能有效挖掘无锡市公交系统中的核心线路组，对于该市公交系统的线路保护、合并或撤销等建设工作具有一定的指导意义。

3 结 语

本文以无锡市公交系统为例，建立了无锡市公交线路复杂网络模型，通过运用复杂网络中的影响最大化算法对网络中的若干关键线路进行识别，并结合网络抗毁性等实验，分析验证了所选线路的有效性。该研究的主要贡献可以归结为：

(1) 首次将影响最大化理论引入于城市公交系统的研究，可为该领域后续更深入的探索工作提供参考。

(2) 识别公交系统的核心线路组，对于理解、完善城市公交的骨架结构有重要意义，如扩大覆盖率、平衡均衡性、调整公交线安排等。

(3) 基于挖掘到的核心线路组，一定程度上能够指导城市公交的重建/恢复工程。当城市公交系统由于不可抗力的灾难基本崩溃，优先修复这些重要线路，以最大限度地保障公交网络的正常功能。

(4) 核心线路组的利用，有助于提升外来游客的出行体验。从核心线路组内选择出行方案，能够在减少换乘次数的同时节省一定的时间。