基于超网络视角对上海轨道交通网络的研究

孙 琳，郭进利 （上海理工大学，上海200093）

SUN Lin, GUO Jin-li (University of Shanghai for Science and Technology, Shanghai 200093, China)

0 引 言

18 世纪数学家欧拉对七桥问题的建模和分析开创了数学中图论这一分支，此后就有很多学者利用图论和复杂网来研究实际问题，来分析网络中存在的问题。复杂网络应用于对轨道交通的研究更成为热点问题，惠伟等[1]采用复杂网络以上海和北京公交线路为例通过计算复杂网络的静态特征值显示北京和上海的公交网络具有小世界特性。Latora 等[2]用复杂网络对波士顿地铁的网络特性进行初探。汪涛[3]等对北京、上海、广州三个城市地铁网络特征进行比较。杨杨[4]等对北京公共交通网络进行建模实证分析和对蓄意攻击做了有效的分析，有些学者对上海地铁当前网络和规划网络做了特性分析，得出重要节点不断向外部转移。以前的研究方式多限于研究节点与边同质的网络，无法完全刻画现实网络复杂性的特征，如生态网络和电力网络，前者节点不同质，后者边不同质。随着交通网络的发展，出现了铁路网、公路网、航空网等许多复杂的网络，这些网络节点和边的数量众多，结构复杂，我们已经不能用传统的复杂网络去研究轨道交通网络。

超网络也是一种特殊的复杂网网络，它既可完美刻画现实网络特征，本身又为综合网络，故超网络研究必将成为网络研究新潮流。大量学者对复杂网络进行研究，有些人摆脱了还原论的局限性，开始研究网络与网络之间的影响，超网络概念就被提出。对超网络的研究不仅有实际意义，也为研究系统的复杂性提出一种新的想法。最早使用超网络概念与运输系统的是Y.Sheffi[5]，而美国科学家A. Nagurney[6]在处理上述交织的网络，把高于而又超于现存网络的网络称为超网络，使超网络的定义开始明确。后来Berge[7-8]在1970 年提出了什么是超图的概念，并描述了无向超图理论，随后研究者对超图的超回路、着色和t-设计[9]等问题进行研究。21 世纪，大量研究者将超图理论以超网络的形式用于现实问题研究，如Bretto[10]用超网络于研究图像的处理，李晓强[11]用超网络对基于变分不等式的电子商务进行研究，Wang Z P[12]等用超网络来研究供应链，并且构建由两个制造商、两个分销商和两个需求市场组成的供应链超网络模型从而解决了各层次多标准优化的问题。

基于轨道交通网络的复杂性，本文从超网络视角对上海轨道交通进行研究，得到用超网络的度分布和聚类系数，分析轨道交通网络的特性，并提出一些规划建议。

1 超网络的定义

目前对超网络的研究还处于起步阶段，有一些概念还没有得到公认。但是已经有人从不同的视角来定义超网络。目前对超网络的定义有两种。

1.1 H. Frank 等在文献[13]中给出的定义

超网络里的节点表示给定集合的网络，而边和弧表示在给定集合中的结合移动和结合偏好，超网络唯一地表示由规则支配的所有结合移动和偏好。

1.2 用超图来定义超网络

超图[14]定义：设V=｛v1,v2,…,vn｝是一个有限集。若：（1）

则称二元关系H=（E,V）为一个超图。V的元素v1,v2,…,vn称为超图顶点，E=｛e1,e2,e3,…,en｝是超图的边集合，集合e的元素eI=｛Vi1,Vi2,…,Vij｝（i=1,2,3,…,m）称为超图的边。如果两个顶点属于同一条超边，则称这两个顶点邻接；如果两条超边的交集不空，称为两条超边邻接。如果一个超图H的任意两条超边至多有一个公共点，则称H为简单超图。

1.3 超网络相关定义

1.3.1 关联矩阵[14]定义

一个图G= V,（）E的关联矩阵B满足下面条件：（1）B的每一行与G的顶点相关； （2）B的每一列与G的边相关联；（3） 如果第j个边与第i个顶点相关联，那么bij=1。

有n个顶点的联通图G的关联矩阵的秩是n-1。在上海轨道交通中，每一行与轨道交通站点有关，每一列与轨道交通线路有关，如果行中的站点在列中的线路中则在关联矩阵中写1 否则写0。

1.3.2 邻接矩阵[14]

一个图G= V,（）E的邻域矩阵S，满足下列条件：（1）S的每一行与G的顶点相关；（2）S的每一列与G的顶点相关；（3） 如果顶点vi与vj之间存在一个关系，即存在一个弧，链接着顶点vi与vj，那么sij=1；存在两个弧sij=2；否则，sij=0。

在上海轨道交通超网络中，邻接矩阵的每行和每列都与站点有关，在站点与站点之间由地铁形成的线路相连，当行中的站点与列中的站点在同一条线（一条弧） 中，则Aij=1。当行中站点与列中站点在共同的两条线路（两条弧） 中则Aij=2，如果两个站点没有在共同的线路中，则Aij=0。上海轨道交通的邻接矩阵A如下。

当A22=0 表示两个站点是同一个站点；

当A23=2 表示第2 个站点和第3 个站点有两条共有的线路；

当A2811=0 表明第281 个站点和第1 个站点没有在共同的线路中。

2 超网络度

对上海轨道交通286 个站点14 条线路进行统计，得到其度分布。

2.1 节点度

节点度[15]（Node Hyperdegrees） 节点连接的顶点数计为d（）i，在轨道交通网络中节点是每个站点，超边是每条地铁线路，节点度描述的是一个站点与其他站点的连接程度。上海市轨道交通超网络的节点度分布和累计度分布如图1、图2 所示。

由图1 可以看出节点度大部分在20 到40 之间，说明上海轨道交通网络站点之间的连通程度还是很小，可以计算出上海轨道交通所有节点度的平均值为31.51049，可以参考这个数值对包含站点少的线路进行调整和改造。由图2y=2.1408e-0.0577x可知节点度的累计分布符合指数分布。

2.2 节点超度

节点超度[15]（Node Hyperdegrees） 节点的超度定义为包含该节点的超边个数, 记为dH（）i。在轨道交通网络中，每个站点是节点，节点超度指的是有多少条超边经过同个站点。上海市轨道交通超网络的节点超度的分布和累计超度分布如图3、图4 所示。

由图3 可知，轨道交通网大部分站点的节点超度值为1，占整个网络的80%以上，表明大部分站点只有一条轨交线路经过。经计算，该网络的平均节点超度为1.188811，说明可换成的站点还是比较少。图4 双对数坐标中对散点图的拟合表明，节点度的累计概率分布p（k）服从幂律分布。网络的拟合结果为y=1.3885x-3.8216，可见从节点超度分析可得上海轨道交通网络具有无标度网络的特性。

计算轨道交通超网络节点超度和节点度按照节点超度的前11 个站点列表如表1 所示。

从表1 可知，按节点超度从大到小排列，前11 个站点相应的节点度如表1 所示。经统计，节点度和节点超度排名前10 的站点相同，金沙江站节点超度是第11，但节点度不是排名前11，说明13 号线路可以增加站点。由表1 可知前10 个站点节点度和节点超度都很大，所以这几个站点是上海轨道交通的重要站点，应该加强对这几个站点的保护，从而使整个交通网络高效率运行。

图1 轨道交通超网络节点度分布

图2 轨道交通超网络节点度的累计概率分布

图3 超网络节点超度的概率分布

图4 超网络节点超度的累计概率分布

表1 站点节点度和节点超度对比表

2.3 边超度

边超度[15]（Hyperedge Degrees） 如果两条超边有相同节点，则这两条超边通过该节点相连。边超度为与该超边相连的其它超边的数。上海市轨道交通超网络的边超度的分布和累计超度分布如图5、图6 所示。

由图5 可知边超度是9 的线路占的比例最大，其次是边超度为7 的线路。说明有些线路与其他线路之间的联系很少，比如5 号线和16 号线。像边超度比较小的线路可以成为以后规划的重点线路。经计算网络的平均边超度为6.571429，可以看出边与边之间的联系还比较少，对小于平均边超度的线路应进行调整和改造。对于边超度较大的线路进行重点保护，以免被蓄意攻击，导致整个交通的瘫痪。

3 轨道交通超网络的聚集系数

H=（V,E）表示一个简单超图，节点集V=｛v1,v2,…,vN｝，超边集E=｛E1,E2,…,Em｝，邻接矩阵A（H）是对称方阵，元素aij为连接节点vi和vj的超边条数，主对角线上的元素为零。假设H是有N个节点的简单超图，它的邻接矩阵A是一个是对称矩阵，因此存在一个正交矩阵U=uij，使得A=UDUT，其中：D=diag（λ1,λ2,…,λn），U的列向量是与A的特征值相对应的正交向量。

设vi和vj是超图H的两个节点，A是H的邻接矩阵，那么H中长度为k的从vi到vj的路径（对应于复杂网络，也称为vi-vj链） 的个数就可以用矩阵Ak第i行第j列的元素值来表示。

图5 边超度的概率分布

图6 边超度的累计概率分布

H中长度为k的vi-vj链的条数为因此，H中长度为k的所有链的条数为：

H中从vi开始最后又回到vi的长度为k的闭合链的条数则由给出，是Ak的第i个对角线元素的值：

那么H中长度为K的闭合链的总条数就是：

聚类系数的理论来源是社会学文献中的传递系数：

其中分子中的6 表示一个三角形可以形成6 条长度为2 的路径，从而保证当图KN是完全连通图时C2（G）=1。由于上面的结论只适合没有重边的简单图，因此当所研究的网络中有重边时就将其化为简单图再计算聚类系数，所以将（4） 式推广到超网络中可以得到超网络的聚类系数[16]如下：

其中超三角形是由三个不同的节点和三条不同的超边组成的一个序列其中这三个点彼此相连而长度为2 的路径则形如vi,Ep,vj,Eq,vk的序列。

我们可以用长度为3 的闭合链的个数来计算超网络中超三角形的个数，但是必须减去不能形成超三角形的长度为3 的闭合链（假超三角形） 的个数。

假超三角形形成的原理：假超三角形三个顶点在同一条超边里。所有三条边都是同一条超边Ei的假超三角形个数为ti其中为超边Ei1,Ei2,…,Eij交的基数用ai1,ai2,…,aij表示。因此假超三角形个数：

同理在计算长度为2 的路径时，需要计算两个节点在同一条超边Ei的长度为2 的假的路径数，p=6t所以超网络的聚集系数由（1）、（3）、（5）、（6） 式可以得：

整理上式可得：

在地铁网络中超网络的邻接矩阵是286 行286 列的矩阵，由邻接矩阵A通过Matlab 编程计算可以得到正交矩阵u=u286,286和其相对应的特征值和特征向量，从而得到：

把式（9）、（10）、（11）、（12） 代入公式（8） 中可以得到：

式（13） 中C2（H）为整个网络的聚类系数，可以反映整个超网络中节点的紧密性网络的聚类一般在[0,1]之间，相对于中间值0.5 是比较小的，另外我们用超网络来计算2020 地铁规划网络的聚类系数得到0.4763668932，相对来说目前网络的聚类系数比较小，表明目前网络的密集度比较差，这也与我国轨道交通建设处于初级阶段的情况相符。还需要更多的发展过程。

4 结论和展望

基于超网络方法研究上海市轨道交通网络，通过分析和研究得到以下结论:

（1） 从节点度分布和节点超度分布可以看出，上海轨道交通网络节点超度为前10 的站点，节点度的大小也是前10，从超网络的节点度和节点超度都可以得到世纪大道、东方体育馆、曹杨路、徐家汇、镇平路、人民广场、虹桥路、金沙江路、中山公园、宜山路站点的节点度和节点超度都很大，说明这几个站点是关键节点。但是两种度的值又不是相同的。其中节点超度的累计度分布跟复杂网络中的累计度分布都符合幂律分布。节点超度度大的站点是关键节点，如果对度大的这些站点进行蓄意攻击，整个网络会瘫痪。目前对超网络的蓄意攻击还没有深入的研究，在后续的文章中会对超网络的蓄意攻击做出解释。

（2） 从边超度分布可以看出1、2、4、8、11 号线边超度较大，应重点保护这几条线，保证这几条线路的可靠性。对于边超度较小的线路应该进行改造和扩展，来使整个网络的辐射半径增大。

（3） 从聚类系数可以看出目前上海轨道交通的密集程度比较小，随着城镇人口的增加应加强对我国轨道交通的建设。

用超网络研究轨道交通还处于起步阶段，对于一些超网络的静态特征还没有确切的定义。随着线路的增加用超网络的节点超度来研究交通网络更加方便。可以将超网络应用于全国铁路网络，同样比用复杂网络来研究全国铁路网络方便。当然也可以用超网络来研究公交网络甚至航空网络。对于公交和地铁网络的换乘也提供了很好的思路。

[1] 惠伟，王红. 复杂网络在城市公交网络中的实证分析[J]. 计算机技术与发展，2008(18):217-222.

[2] Latora V, Massimo M. Is the Boston Subway a small-world network[J]. Physica A, 2002,314:109-113.

[3] 汪涛，方志耕,等. 城市地铁网络的复杂性分析[J]. 军事交通学院学报，2008,10(2):24-27.

[4] 杨杨，关伟. 北京市公共交通网络复杂性分析[D]. 北京：北京交通大学（硕士学位论文），2011:59-63.

[5] Sheffi Y. Urban Transportation Networks: Equilibrium Analysis with Mathematical Programming Methods[M]. Printice-Hall,1985:33-89.

[6] Anna Nagurney, J. Dong. Supernetworks: Decision-Making for the Information Age[M]. Cheltenham Edward Elgar Publishing,2002:1-368.

[7] BERGE C. Graphs and hypergraphs[M]. New York: Elsevier, 1973:389-391.

[8] BERGE C. Hypergraphs: The theoryoffinite sets[M]. Amsterdam: Elsevier Science, 1989:1-2.

[9] TUANND. Hypergraphical t-designs[J]. Discrete Mathematics, 2006,306:1189-1197.

[10] BRETTOA, GILLIBERYL. Hypergraph-based image representation[J]. Lecture Notes in Computer Science, 2005,35:1-11.

[11] 李晓强. 基于变分不等式的电子商务超网络研究[D]. 大连：大连海事大学（硕士学位论文），2006:8-50.

[12] Wang. Zhang FM, Wang Z T. Research on return supply chain supernetwork model based on variationalinequalities[C]//Proceeding of 2007 IEEE international conference on automation and logistics. Jinan, China, 2007:25-30.

[13] Frank H, Page J, Myrna H, et al. Networks and farsighted stability[J]. Journal of Economics Theory, 2005,120(2):257-269.

[14] 贝尔热C，卜月华，张克民. 超图—有限集的组合学[M]. 南京：东华大学出版社，2002:1-40.

[15] 胡枫，赵海兴. 一种超网络演化模型构建及特性分析[J]. 中国科学，2013,43(1):16-22.

[16] Estrada E, Rodrigues V R. Subgraph centrality and clustering in complex hyper-networks[J]. Phsical A, 2006,364(1):581-594.

[17] 王志平，王众托. 超网络理论及其应用[M]. 北京：北京科学出版社，2008:5-30.

[18] 漆玉虎，郭进利,等. 超网络度参数研究[J]. 科技与管理，2013,15(1):34-38.