基于社区发现法的高速铁路网络划分研究*

姚晓峰 ，张 鹏 ，孙克洋 ，杨 敏

（1 中国铁路北京局集团有限公司客运部 工程师，北京 100860；2、3、4 西南交通大学交通运输与物流学院 硕士研究生，四川 成都 610031）

0 引言

随着我国高速铁路交织成网，网络密度不断加大、各个线路交叉频率增加，导致大量本线和跨线列车的复杂开行。 同时，大部分线路不同速度、不同性质列车共线运行，列车运行间隔时间、车站作业间隔时间不统一，导致路网上的列车运行组织极其复杂。 高速铁路网络化列车开行方案优化面临着列车运行径路选择、跨线列车组织、换乘节点选择等关键问题，尤其在大规模路网条件下建模求解的复杂度将呈指数级增加。 因此有必要对目前高速铁路的网络特性进行分析，通过子网划分的方法将路网条件下列车开行方案优化问题转变为多个子网的列车开行方案优化和合并问题，逐步降低整体求解难度[1]。

针对高速铁路网络的研究以网络建设扩展[2]、网络结构演化[3]、网络经济发展[4]、交通小区划分[5]等为主， 随后复杂网络理论广泛应用于高铁网络研究。 社区结构作为复杂网络特性之一广泛运用于人际网络、万维网络、客流网络[6]、交通出行网络[7]中。目前高铁网络划分的研究以区域划分为主， 吴琪[8]引入博弈论的思想分析了区域铁路通道线间的协同竞争， 为编制区域铁路通道客运产品奠定基础。帅斌等[9]采用聚类的方法对全国运输网络进行了区域划分。 张强锋等[10]考虑既有聚类划分方法存在无法考虑区域网络中心性、连接性等缺点，提出根据路网的邻接特性建立区域网络划分决策优化模型。张兰霞[11]引入群落概念将路网划分为满足约束的群落。 王逸飞[12]根据线路之间的客流交换量将城际铁路网络划为不同的线团。

需要指出的是既有的区域划分存在无法评估、人为割裂长大跨线客流、 受主观影响较大等弊端。本文引入社区发现方法依据网络特性进行客观划分， 通过联系紧密的社区结构挖掘铁路网络规律，划分结果可评估，避免了主观经验主义影响。 同时重叠节点的发现可巧妙解决跨线节点选择问题，能够紧密结合客流需求实现“按流开车”，为网络划分提供了极大的支持。

1 问题分析

高速铁路网络是一个无向有权网络，且社区结构呈现重叠社区结构特性，本文根据既有重叠网络研究方法，结合空间网络特性，提出客流、距离加权的重叠社区发现方法进行网络划分。 网络划分的核心原则是根据客流需求、路网结构、动车组检修分布等将路网划分为多个运输区域，区域内部可根据各自特点设立不同的列车开车方案[13]。 在高速铁路网络上，由旅客出行需求形成OD 客流网络，体现了节点之间的联系； 当旅客选择对应的出行方案时，客流也就相应加载到高铁线路上，形成客流分配网络，体现出线路之间的联系。 研究高速铁路网络，既要从网络节点出发研究不同车站之间的客流交互、距离等因素，也要从网络边出发研究不同出行径路的选择和线路能力等。 本文提出的路网划分方法不再仅仅基于高速铁路网络的物理分布， 而是引入OD 客流和路径客流，研究客流对路网划分的影响。假定在OD 客流已知的基础上，参考文献[14]和[15]构建基于出行径路选择的高速铁路网络客流分配模型， 分别在OD 客流网络和客流分配网络上基于社区发现方法进行网络划分形成对应的三级网络，如图1 所示。

图1 高速铁路“路网-区域-线团”三级网络形成流程

2 路网-区域-线团三级网络划分方法

2.1 高速铁路区域网络划分

2.1.1 网络划分相关概念

由于旅客出行的多样化，高速铁路网络会产生不同起讫点之间的客流，通过客流分配模型进而可以确定出各条线路上的客流量。 各个节点之间以客流的交互量表示联系强度，与客流量的大小成正相关；以相互之间的距离表示影响强度，与距离远近成负相关，因此以节点客流量作为相似权，以节点距离作为相异权，将二者形成组合模重[16]来为高速铁路网络赋权，重构高速铁路网络。

重叠网络社区划分主要有局部扩展、边划分和模糊发现等几类方法[17]，高速铁路网络布局呈现向四周发散的路网结构，局部扩展方法较为适用。 核心思想是通过联合引力度确定重叠社区的中心节点，然后从中心向邻接节点扩散，根据邻接节点对重叠社区的隶属度逐步合并社区，直到模块度最高为止。 设节点va，联合引力度定义如下：

式中：Fa为节点va的联合引力度为节点 va和 vj之间的最短距离；ma、mj为节点的加权质量，可用节点的联合度表示，表示节点在全网的影响力，与连接的节点数量和连接边权重有关； 其中Ka、Sa分别为节点va的连接度、连接强度，连接度为节点的连接节点数量，连接强度为连接边权重，β 为调节参数。

联合隶属度是判断节点对重叠社区的隶属关系的重要指标，设有重叠社区C，任意节点a 对重叠社区的联合隶属度，如式（2）所示。

式中：K(a,C)为节点a 对重叠社区C 的连接度，即连接的节点数量；S(a,C)为节点a 对重叠社区C 的连接强度，即连接边权重。

2.1.2 二级区域网络划分流程

Step 1：初始化网络。 根据高速铁路网络权重设计方法， 并输入相关信息构建加权网络G=（V，E，W），并将所有节点标记为“N”，即为尚未划入重叠社区。

Step 2：判断节点是否有标记“N”，若有，进入Step 3；若没有，结束。

Step 3：计算所有节点 a（标记为“N”）的联合引力度，取 max（Fa）,∀a∈V 的节点为重叠社区的中心节点z。

Step 4：构建初始中心社区。 搜索中心节点z 的所有邻接节点放入集合Vs中。 判断节点标记为“N”，则归入中心节点z，形成初始中心社区C，同时将中心社区的节点放入集合Vz。

Step 5：确定中心社区。 遍历集合 Vz，∀a∈Vz，计算B(a,C)，如果联合隶属度大于阈值，即B(a,C)≥BT，则从集合V 中删除节点a，进入下一步。否则，在集合Vz中删除节点a，最终形成中心社区Cz。

Step 6：搜索中心社区的邻接节点。 搜索中心社区的邻接节点放入集合VJ中，并计算节点对中心社区的联合隶属度 B(b,Cz)，∀b∈VJ。

Step 7：构建扩展集合。置扩展VK=Φ，遍历集合VJ，判断∀b∈VJ，若 B(b,Cz)≥BT，则将节点 b 放入集合VK中。

Step 8：扩展中心社区。判断扩展结合VK是否为空集， 若不是空集， 则将扩展集合节点加入中心社区，形成新的中心社区Cz，中心社区中所有节点标记为“J”，并返回 Step 5；若是空集，则返回 Step 2。

2.1.3 区域网络划分评价

模块度是评估社区发现算法质量的常用指标，根据Newman[18]提出的Q 函数可知，当模块度最大时，网络社区的划分效果最好。 考虑到空间网络对实际距离的敏感度较大， 需改进普通的模块度公式，从而提出了距离模块度[19]概念，如式（3）和式（4）所示。

式中：f(d(vi,vj))为节点 vi、vj的距离衰减函数，衰减函数为为实际距离，o 为数据的自适应值；d(vi,vj)为节点 vi、vj的实际距离。

2.2 高速铁路线团网络划分

二级区域网络实现了区域内部联系紧密，然而区域网络内含的节点仍旧较多，直达、换乘的处理仍旧比较复杂。 根据客流分配结果和路网基础结构分析，从经济效益和旅客出行需求出发，考虑在跨线节点处的客流达到一定的阈值才开行跨线列车，否则组织旅客中转换乘。 因此，借用换乘虚拟弧和换乘概率对二级区域网络内部线路进行再划分。 划分的方法如下：

假设一个高速铁路小线网有三条线路，分别为B-C、A-E、D-F， 其中车站 C、D 为网络中的跨线节点，如图2 所示。

图2 小线网示意

设根据客流分布计算出在跨线节点C、D 的换乘概率如表1 所示，取换乘概率阈值为0.5。

表1 小线网换乘节点换乘概率（单向）

图3 线团网络划分示意

3 案例分析

以成都局管内高速铁路线路为网络基础数据，进行实例分析。 根据铁路运行图编制系统V4.0 的2021 年高速铁路列车开行情况为基础，假定分界站为终到站，分界站以远不作考虑，选择10 个线路上的62 个车站构建物理网络。 以2021 年第四季度的客票数据作为依据，统计某日内高速铁路网络上的OD 客流数据， 并根据车站和线路区间的基础数据构建物理网路。

借用文献[13]提出的改进Dijkstra 算法先求解最短径路，再用双扫描算法求解合理径路集，根据OD 客流数据， 共计客流1 202 对， 在操作系统为WINdows11，CPU：Intel(R) Core(TM)i7-10710U，主频1.19 GHz，16.0 GB 的系统环境下使用 Python 软件进行求解，取绕行率，搜索出合理径路集8 262 条。随后借鉴文献[20]和文献[21]的研究数据进行试验配流，可得到各线路区间的客流分配量，如图4 所示。

图4 客流分配结果

随后进行二级区域网络划分。 以路网中节点之间1 202 对OD 客流以及节点之间的距离为基础数据，设加权网络调试权重为βw，以社区评价指标距离模块度Q 作为评价指标。 当βw=0.3 时，有最高距离模块度Q=0.76，最终得到最佳的区域划分结果，从中发现重叠节点和中心节点，如图5 和表2 所示。

图5 二级区域网络节点划分结果

表2 二级区域网络划分结果

随后在二级区域划分的基础上进行线团网络划分。 本文以区域1 为例，基于客流分配结果和路网基础条件分析客流分布和线路走向， 如表3 所示，在换乘节点12 处，共衔接成贵、成渝、沪蓉、西成四个线路方向，根据客流分配结果可得到四个方向的衔接的跨线客流量， 根据公式可计算换乘节点的各个方向客流的换乘概率， 如表3所示。

表3 换乘节点12 各衔接方向的换乘率

根据表3 可知， 虚拟换乘弧21-12-52 和13-12-52 的换乘率较低，有开行直达列车的潜力，而虚拟换乘弧45-12-52 和21-12-45 的换乘率较高，考虑换乘运输。 同时，根据线路走向分析可知，成贵和西成高铁较为平顺地衔接于成都东站，而成渝和西成高铁的衔接相对比较弯曲， 故将该换乘节点12设置50%为换乘率阈值，其他弧段的换乘率为中间值，将成贵和西成高铁化为同一线团网络，成渝和沪蓉则单独成团。 同理，区域网络1 在节点23 处有绵泸高铁衔接，并在节点23 处形成一个Y 行线路，弧段22-23-54 则相对平滑， 故可将两条线路划分为同一线团网络。 因此，可将区域1 内的区域网络划分为三个线团网络，如图6 所示，图中黑色节点23、47 为二级社区网络划分时发现的重叠节点，节点12 则是在三级网络划分时发现的换乘节点。

图6 区域网络1 的三级网络划分结果

4 结论

本文分析了既有区域划分的劣势，根据我国铁路网络长短途客流并存、 区域性结构布局等特点，探索性地提出高速铁路“路网-区域-线团”三级网络划分：将高速铁路物流网络转换为客流网络并将其作为一级网络；二级区域网络划分以节点客流量和距离作为相似权和相异权， 采用局部扩散思想，并基于联合引力度的重叠社区发现方法寻找中心社区， 完成社区结构划分从而形成二级区域网络；三级线团网络划分根据换乘节点的换乘概率和列车运行条件，形成内部以直达客流交互为主的线路团体，从而形成高速铁路“路网-区域-线团”的三级网络。 最后选取成都局管内的高速铁路网络作为案例，将路网划分为3 个二级区域网络并以区域1 为例将其划分为3 个线团网络，为高速铁路列车开行方案优化设计提供了良好的前提条件。