小世界网络最早由Watts和Strogatz在1998年提出，将高集聚系数和低平均路径长度作为评价物理网络是否具有小世界特性的特征值，一般称作Watts-Strogatz (WS)模型，是最典型的小世界网络模型^[1]。小世界网络的实质是一种看似不相连的绝大部分节点，实际上经过少数几步就可以到达，也就是平均路径较短。虽然随机网络的平均路径长度也很小，但其聚类系数却远小于同等规模的小世界网络^[2]。

平均路径长度用来描述2点之间的分离程度，用二者之间的连接数目衡量；聚类系数用来描述点的紧密程度^[3]，也就是该节点与任意2个邻居节点组成封闭三元组的程度。在社会学中，聚类系数指在指定节点周围的所有节点之间信息传递的通达性，通常用邻居节点之间实际存在的连结数目与最大可能存在的连结数目的比值衡量。

公交网络和有轨公共交通网络的增长以线路为单位^{[3, 4]}，每次增加到已有网络中的是一条线路，而非一个车站，每条线路上有换乘车站和非换乘车站。从信息传递的角度看，在一条线路上任意2个车站之间传递信息，不需要换乘就可以到达，但是在社会网络中，每经过一个人，都需要进行信息转述。例如在朋友网中，假设一个人并不认识他朋友的朋友，那么要从这个人传递信息给他朋友的朋友，就必须要经过2次转述。因此，研究公交网络和有轨公共交通网络的小世界特性，不能简单的套用社会网络小世界特性评价方法。

已有学者认识到上述问题的存在，因此，在研究地铁网络、铁路网络和公交网络时，采用P空间(Space-of-Stops)建模，并用换乘次数作为路径长度的评价指标^[4]。相比L空间(Space-of-Stations)建模，更加适用于这类以线路为演化单位的公共交通网络。P空间建模，有效地解决了换乘次数作为这类公共交通网络平均路径长度的衡量指标的评价模型问题，但在衡量聚类系数时仍然无法差异化车站直接、间接相邻对信息传递效率的影响。

本文针对这一问题提出基于信息传递效率的聚类系数算法，以此为基础对全球52个城市的地铁网络的小世界特性进行评价。

1 聚类系数算法 1.1 聚类系数算法回顾

在社会学中，聚类系数描述网络中节点的所有邻居节点也互为邻居节点的比例。节点的聚类系数定义如式(1)所示^[5]，即

${C_i} = \frac{{3{N_\Delta }\left( i \right)}}{{{N_3}\left( i \right)}}.$

(1)

其中: a_ij表示任意2个节点i和节点j之间，如果存在连边，则a_ij=1，否则${N_\Delta }\left( i \right) = \sum\limits_{k \ge j} {{a_{ij}}{a_{ik}}{a_{kj}}} $表示网络中含有节点v_i的封闭三元组的总数，${N_3}\left( i \right) = \sum\limits_{k \ge j} {{a_{ik}}{a_{ij}}} $，表示包含v_i的封闭三元组的最大值。1个节点的聚类系数也可以记为式(2)，即

$${C_i} = \frac{{2{e_i}}}{{{k_i}\left( {{k_i} - 1} \right)}}.$$

(2)

其中：e_i表示v_i的邻居节点之间的连边数;k_i表示v_i的度，定义为v_i的邻边数。

1.2 在公共交通网络中的应用

示例地铁网络图 1a,L空间建模情况下(图 1b)。地铁网络中度为1的车站只有1个邻居车站(v₁,v₄,v₅,v₆)，式(2)的分母k_i(k_i-1)=0，使得C_i没有意义，因此该聚类系数算法不适用于地铁网络^[6]。

为了解决始末节点的聚类系数在L空间建模方法下无意义的问题，学者采用了P空间建模的方法计算聚类系数(图 1c)。关于P空间建模方法的主要文献、应用及其分析结果见表 1。

P空间建模的聚类系数算法假设：1条线路上的所有车站都互为邻居，且同1条线路上任意2个车站距离都为1。例如，在图 1b中，v₁和v₄的测地线距离a_1,4=3，换乘次数T_1,4=1；v₃和v₄的测地线距离a_3,4=1，换乘次数T_3,4=1。

在图 1c中，a_1,4=a_3,4=1 ，可以看出，P空间建模的方法只考虑了换乘对车站对距离远近的影响，而忽略了中间车站(如v₂和v₃)对远近的影响。

从聚类系数的本质意义来看，在社会网络中，不需要经过其他节点直接相连的节点称之为邻居节点，因此在公式

$${N_\Delta }\left( i \right) = \sum\limits_{k > j} {{a_{ij}}{a_{ik}}{a_{kj}}} $$

中，a_ij=a_ik=a_kj=1.表示在包含v_i的封闭三元组中，任意2个节点之间都直接相连。在示例地铁网络中，虽然v₁和v₄不需要换乘即可到达，但必须经过v₂和v₃，当这2个车站出现故障时，v₁和v₄的“邻居”关系必然受到影响。然而，在P空间下的聚类系数算法却忽略了中间节点的存在，故认为是不恰当的。算法应该能够差异化同一线路直接相连的邻居节点与需要经过中间节点连接的邻居节点对信息传递效率的影响。

基于此，本文构建基于信息传递效率的聚类系数新算法,来解决以线路为演化单位的公共交通网络小世界特性评价方法的问题。

2 基于信息传递效率的聚类系数新算法

定义1 地铁网络中邻居节点。

所有与指定v_i在同一条线路上的车站都称为v_i的邻居节点。v_i有经l₁,l₂,……,l_n经过，每条线路含有的节点数目为，v_l1,v_l2,……,v_ln,V_neighbor(i)= v_l1,v_l2，…，v_ln。以示例地铁网络为例，v₅只有λ₁经过，所以v₅的邻居节点为v₂,v₆,v₈；v₂有l₁和l₂经过，所以V_neighbor(2)={v₁,v₃,v₄,v₅,v₆,v₈}。邻居节点又有直接相邻和间接相邻2类。直接相邻指在1条线路上指定的2个车站，不需要经过其他车站就可以到达，如图 1a中的v₁和v₂；间接相邻指在1条线路上指定2个车站，需要经过其他车站才能够到达，如图 1a中的v₁和v₄。

定义2 紧密程度。

地铁网络中包含v_i的封闭三元组的紧密程度由三元组的3条边的平均测地线长度的倒数衡量。测地线长度表示2个节点之间的距离，距离越长，节点越疏远；反之，距离越短，节点越紧密。因此，用测地线长度的倒数——效率^[7]，作为节点亲疏程度的量化指标，能够解决直接相邻和间接相邻对信息传递效率影响的问题，能反映间接相邻中间车站对信息传递的阻碍作用。记的封闭三元组的紧密程度为${E_\Delta }\left( i \right) = \frac{1}{3}\left( {\frac{1}{{{a_{ij}}}} + \frac{1}{{{a_{ik}}}} + \frac{1}{{{a_{kj}}}}} \right)$，当v₁的封闭三元组的任意2个车站都直接相邻时，有a_ij=a_ik=a_kj=1,封闭三元组的紧密程度达到最大值${E_\Delta }{\left( i \right)_{\max }} = \frac{1}{3}\left( {1 + 1 + 1} \right) = 1$。

在示例地铁网络中(图 1a)，以v₂为例，其邻居节点V_neighbor(2)={v₁,v₃,v₄,v₅,v₆,v₈}，其中，v₅,v₈,v₆∈l₁，v₁,v₃,v₄∈l₂；由于同1条线路上的任意2个节点都由该线路相连，所以可以与v₂组成封闭三元组，如Δv₂v₅v₆、Δv₂v₅v₈、Δv₂v₈v₆(图 2)，实线表示实际中存在的轨道线路，虚线表示该节点对并不是如图所示的直接相连，而是由该虚线所围成的闭合区域内的实线顺序连接，v₅v₆: v₅→v₂→v₈→v₆；椭圆实线围成的区域内的节点为v₂的所有邻居节点，网络中包含v₂的所有封闭三元组为集合{Δv₂v₅v₆、Δv₂v₅v₈、Δv₂v₈v₆、Δv₂v₁v₃、Δv₂v₁v₄、Δv₂v₃v₄、Δv₂v₃v₈ }。

Δv₂v₅v₆的效率为：

$$\begin{array}{c} {E_{\Delta 256}}\left( 2 \right) = \\ \frac{1}{3}\left( {\frac{1}{{{a_{25}}}} + \frac{1}{{{a_{56}}}} + \frac{1}{{{a_{62}}}}} \right) = \frac{1}{3}\left( {\frac{1}{1} + \frac{1}{3} + \frac{1}{2}} \right). \end{array}$$

网络中包含v₂的所有封闭三元组的效率为：

$${E_\Delta }\left( 2 \right) = \sum\limits_{k > j} {\frac{1}{3}\left( {\frac{1}{{{a_{ij}}}} + \frac{1}{{{a_{ik}}}} + \frac{1}{{kj}}} \right).} $$

其中：a_kj>0，且v_k,v_j∈V_neighbor(2)。

车站v₂与其邻居节点V_neighbor(2)组成封闭三元组的理论最大值为：

$$\begin{array}{c} {E_\Delta }{\left( 2 \right)_{\max }} = \\ \frac{{{V_{{\rm{neighbor}}}}\left( 2 \right)\left( {{V_{{\rm{neighbor}}}}\left( 2 \right) - 1} \right)}}{2} = \frac{{6\left( {6 - 1} \right)}}{2}. \end{array}$$

定义3 聚类系数

网络中节点的邻居节点之间互为直接相邻的比例，也就是小集团的紧密程度定义为基于信息传递

效率的聚类系数。v_i和网络的聚类系数如式(3)所示，即

$\begin{array}{l} {C_i} = \frac{{{E_\Delta }\left( i \right)}}{{{E_{{\rm{neighbor}}}}{{\left( i \right)}_{\max }}}} = \\ \frac{{2\sum\limits_{k > j} {\left( {\frac{1}{{{a_{ij}}}} + \frac{1}{{{a_{ik}}}} + \frac{1}{{{a_{kj}}}}} \right)} }}{{3{V_{{\rm{neighbor}}}}\left( i \right)\left( {{V_{{\rm{neighbor}}}}\left( i \right) - 1} \right)}}. \end{array}$

(3)

由图 2看出，v₂的封闭三元组有2类，即

1) 同一条线路上的2个车站与该车站组成的封闭三元组；

2) 与非同一条线路上的2个车站与该车站组成的封闭三元组。

由虚线、实线组成的封闭三元组，三点必然在同一条线路上，由实线组成的封闭三元组，有两点必然不在同一条线路上。在计算时，所有虚线须由其对应的所有实线代替，因此，式(3)解析如式(4)，即

${C_i} = \frac{2}{3}\frac{{\sum\limits_{k > j,k \in {l_i},j \notin {l_i}} {\left( {\frac{1}{{{a_{ij}}}} + \frac{1}{{{a_{ik}}}} + \frac{1}{{{a_{kj}}}}} \right) + \sum\limits_{{l_i}} {\left( {\left( {{V_{{l_i}}} - 3} \right)\sum\limits_{j \in {V_{{\rm{neighbor}}}}\left( i \right)} {\frac{1}{{{a_{ij}}}} + \frac{1}{2}\sum\limits_{i,j \in {c_{{l_i}}}} {\frac{1}{{{a_{ij}}}}} } } \right)} } }}{{{V_{{\rm{neighbor}}}}\left( i \right)\left( {{V_{{\rm{neighbor}}}} - 1} \right)}}.$

(4)

由式(4)看出，C_i与V_neighbor(i)成反比关系，V_neighbor(i)取决于经过v_i的线路数目l_i，而在本研究的前面部分定义节点经过的线路数目为节点度，因此，C_i节点度成反比；同时，C_i与a_ij成反比，由于a_ij的大小取决于v_i的位置，v_i越靠近线路的中心位置，a_ij越小，则C_i越大。

网络全局聚类系数有如式(5)所示，即

$\delta C = \frac{1}{N}\sum\limits_i {{C_i}} .$

(5)

3 地铁网络小世界特性评价

在地铁网络中，换乘次数是乘客选择出行路径的主要考虑因素；如果将乘客看作是拓扑线路结构上的信息，从社会网络平均路径算法的初衷看，地铁网络中的平均路径长度指标需要反映乘客的下车上车次数，由此，本论文与已有的大部分研究一样，将换乘次数δ作为评价平均路径长度的指标，采用基于线路始末站点的搜索算法进行计算。

地铁网络是否具有小世界网络特性，需满足：在车站数目N很大时，平均路径长度近似于 δ∝lg(N)；聚类系数C大约和同等规模(相同节点数目和平均度分布)的规则网络在同一数量级，且远大于随机网络的聚类系数C_random^[8]。随机网络聚类系数随着网络节点数目增加而减小，C_random计算方法如式(6)所示，即

${C_{{\rm{random}}}} = \frac{{2E}}{{N\left( {N - 1} \right)}}.$

(6)

其中：E表示随机网络中边的数目；N表示随机网络中节点数目。

4 案例分析

样本选取原则，从全球有地铁的城市进行筛选，筛选原则：

1) 线网需要有3个及以上换乘车站，以此保证选取研究对象的网络特性。

2) 线网需要有3条及以上拓扑结构上独立线路。

经筛选，有52个城市的地铁网络符合以上2个原则，故以此为样本，在采用Java语言编写的Urban_metro_cas城市地铁复杂网络自适应分析系统中建立网络模型，并做相关计算。

根据式(4)计算得到相同规模的随机网络聚类系数C_random在0.01~0.16之间，平均值为0.06。由式(5)计算得到52个城市的地铁网络聚类系数值在0.195~0.407之间，平均值为0.290。地铁网络的平均换乘次数δ在0.5~1.8之间，也就是52个地铁网络的换乘次数在1~2次之间，平均换乘值为0.996，即平均换乘1次。相同规模随机网络平均路径长度在3.26~6.15之间，均值为4.53。计算结果如图 3和图 4所示

由图 3和图 4可以看出，52个地铁网络都满足小世界网络特性的2个充分必要条件。首先，52个地铁网络的平均路径长度δ小于随机网络平均路径长度值ln(N)(图 3)，如果将始末车站对之间所经过的连结数目作为评价网络平均路径长度指标，则会得到相反的结论；其次，地铁网络的实际聚类系数C也远大于有相同节点数目N的随机网络聚类系数C_random(图 4)，然而远小于以线路为演化单位的公共交通网络中P空间下的聚类系数值。究其原因，P空间下的聚类系数基于如下假设：任意2个车站如果能够不需要换乘到达，则认为直接相连，信息传递效率为1，从而忽略了中间车站对信息传递的阻碍作用。而本文的计算方法考虑了间接相邻和直接相邻在信息传递效率的方面的差异，认为中间节点对信息的传递有阻碍作用，因此2个车站之间信息传递效率与含有中间车站数目成反比，故计算得到的聚类系数值相比传统的计算方法得到的数值要小，但仍然远大于随机网络聚类系数值，因此，地铁网络具有小世界特性。

5 结 论

本文研究了地铁网络小世界特性评价方法，结合地铁网络的特有属性，给出基于平均换乘次数的平均路径长度度量方法及基于信息传递效率的聚类系数度量方法。本文考虑了中间车站对信息传递效率的影响，提出适用于以线路为演化单位的公共交通网络的基于信息传递效率的聚类系数计算方法。最后通过对全球52个地铁网络最低效率的拓扑线路网络做实证分析，得到平均换乘次数(平均路径长度)小于网络节点数目的对数值，聚类系数取值在0.195~0.407之间，小于传统的P空间下得到的地铁网络聚类系数值，但远大于同等规模随机网络聚类系数取值，满足2个判定网络是否具有小世界特性的条件，故认为基于信息传递效率的聚类系数算法能够更加严格地评价物理网络是否具有小世界特性，在此方法下，52个样本城市地铁网络仍具有小世界特性。该结论能够为地铁网络的演化模型构建提供基础。