在计算机科学、社会学、交通网络、经济管理等诸多领域, 复杂网络已成为大量真实复杂系统的重要分析工具[1].大量研究表明, 与网络中其他节点相比, 复杂网络的重要节点对网络动态过程有较强的影响, 如网络同步、疾病传播、交通导航等.因此, 重要节点的识别不仅能够揭示网络结构、功能及其相互关系, 同时也有助于解决实际问题[2].任晓龙等[3]系统地介绍了节点重要性排序方法, 并对比了各方法的优缺点以及应用范围.

仓储就是在特定的场所储存物品的行为.仓储节点的选址关系到整个物流链的流通效率.为确定复杂网络中的重要节点和线路, 及资源分配机制提供有力的决策依据, 在复杂网络重要节点的识别中, 逼近理想解排序法 (TOPSIS) 作为一种同时考虑多方面因素的综合评价方法, 得到了较为广泛的应用, 如Liu等人[4]采用网络效率证明了TOPSIS方法可以更准确地识别山西大水网和北京地铁网的重要节点;Hu等人[5]利用SIR模型模拟实验表明加权TOPSIS方法可以准确地对节点的重要性进行排序.然而, TOPSIS方法在评价节点重要性时具有一定的局限性, 位于正理想方案和负理想方案的连线的垂直平分线上的点不能区分.模糊多准则决策方法 (VIKOR) 是Opricovic和Tzeng等人提出的一种折衷排序方法[6], 已在多个领域中获得了成功应用[7].VIKOR方法的原理是定义各准则的正理想点和负理想点, 计算各方案的群效用值和个体遗憾值, 通过最大化群体效用值和最小化个体遗憾值来对方案集进行折衷排序, 进而对方案进行综合评价.将VIKOR方法引入到物流仓储节点的选址问题, 辅助做出更加合理的决策.

1 理论基础

在复杂网络研究领域, 学者们提出了多种节点重要性评价指标, 如度中心性、介数中心性、接近性中心性、特征向量中心性、离心中心性、Katz中心性、K核分解等[3]本文考虑到轨道交通网的特征及相关研究成果, 从局部属性、传播属性、全局属性以及拓扑属性角度出发, 选择了度中心性、介数中心性、接近性中心性和特征向量对物流仓储节点选址进行综合评价.相关指标的描述如下.

定义1 局部属性——度中心性 (Degree Centrality, 简称DC)

DC(i)=∑NjmijN−1$(i)=\frac{{\displaystyle {\sum }_j^{{\rm N}}m}{}_{ij}}{{\rm N}-1}$, (1)

其中, N表示网络的总节点数, i表示目标节点, mij表示节点i和节点j连接关系, 如果两个节点直接相连接, 则mij=1;反之, mij=0.DC表示一个节点与其邻居节点的连通能力, 数值越大, 节点越重要.

定义2 传播属性——介数中心性 (Betweenness Centrality, 简称BC)

BC(i)=2(N−1)(N−2)∑s≠i≠tpst(i)pst$(i)=\frac{2}{({\rm N}-1)({\rm N}-2)}{\displaystyle {\sum }_{s\ne i\ne t}\frac{p{}_{st}(i)}{p{}_{st}}}$, (2) pst(i)$p{}_{st}\left(i\right)$

其中, pst表示从节点s到节点t的所有最短路径数量之和, pst (i) 表示节点s到节点t的所有最短路径中经过目标节点i的最短路径数.节点的重要程度与节点的介数中心成正比.

定义3 全局属性——接近性中心性 (Closeness Centrality, 简称CC)

CC(i)=N−1∑j≠idij$(i)=\frac{{\rm N}-1}{{\displaystyle {\sum }_{j\ne i}d}{}_{ij}}$, (3)

其中, 表示目标节点i到节点j的所有最短距离之和.CC用于衡量目标节点对网络中其他节点的影响能力, 数值越大, 节点越重要.

定义4. 拓扑属性——特征向量中心性 (Eigenvector Centrality, 简称EC)

EC(i)=1ρ∑Nj=1mijej$(i)=\frac{1}{\rho }{\displaystyle {\sum }_{j=1}^{{\rm N}}m}{}_{ij}e{}_j$, (4)

其中, ρ是节点的邻接矩阵M的最大特征值, e=(e1,e2,⋯,en)T$e=\left(e{}_1,e{}_2,\cdots ,e{}_n\right){}^{{\rm T}}$是网络的邻接矩阵M对应的最大特征值ρ的特征向量.节点的特征向量中心性数值越大, 说明该节点越重要.

2 基于VIKOR方法的节点重要性综合评价

从整体角度出发, 不考虑交通网的方向和站点之间的距离, 运用复杂网络理论, 将交通网中的站点视为复杂网络的节点, 站点之间的连接抽象成复杂网络的边, 提取上海轨道交通网的全局网络拓扑结构, 将其转化成无向图G=<V, E, M>, 总共包括303个节点, 节点编号为1-303.其中V={v1,v2,⋯,v303}$V=\left\{v{}_1,v{}_2,\cdots ,v{}_{303}\right\}$是网络中节点的集合, E={e1,e2,⋯,em}∈V×V$E=\left\{e{}_1,e{}_2,\cdots ,e{}_m\right\}\in V\times V$是节点与节点之间边的集合, M=[mij]n×m是网络的邻接矩阵, 如果节点i和节点j直接相连, 则mij=1;否则, mij=0;另外mii=0.

在复杂网络中, 每个节点代表一个备选方案, 节点的评价指标则是评估方案的多个标准, 所以网络节点的选择可视为一个多属性决策问题.应用VIKOR方法, 具体步骤如下:

步骤1:确定决策矩阵.

在上海轨道交通网中, 节点集合V={v1,v2,⋯,v303}$V=\left\{v{}_1,v{}_2,\cdots ,v{}_{303}\right\}$, 属性集合F={f1,f2,f3,f4}={EC,DC,BC,CC}$F=\left\{f{}_1,f{}_2,f{}_3,f{}_4\right\}=\left\{EC,DC,BC,CC\right\}$, vi(fj)(i=1,2,⋯,303;j=1,2,3,4)$v{}_i\left(f{}_j\right)\left(i=1,2,\cdots ,303;j=1,2,3,4\right)$表示节点i在指标j下的重要性评估值, 决策矩阵P可以表示为:

步骤2:确定各属性的正负理想点.

f∗j=maxjvi(fj),f−j=minjvi(fj),fj$f{}_j^{*}=\max {}_{j}v{}_i\left(f{}_j\right),f{}_j^{-}=\min {}_{j}v{}_i\left(f{}_j\right),f{}_j$是效益型属性, (6)

f∗j=minjvi(fj),f−j=maxjvi(fj),fj$f{}_j^{*}=\min {}_{j}v{}_i\left(f{}_j\right),f{}_j^{-}=\max {}_{j}v{}_i\left(f{}_j\right),f{}_j$是成本型属性. (7)

步骤3:确定各个属性的权重值.

EC、DC、BC、CC均为效益型指标, 其值越大, 表示节点的位置越重要.这四个指标的权重使用层次分析法 (AHP) [8]计算得出, 步骤如下:

首先, 利用 (0, 1, 2) 三标度法对四个指标进行相互比较, 然后构建一个比较矩阵CV.

与其他指标相比, DC简单直观且计算复杂度低, 直接描述了节点的影响力, 因此DC被认为是最重要的指标.BC、CC描述了节点的传播属性和全局性属性, 时间复杂度较高, 所以重要性低于DC.EC是根据邻居节点的信息评价该节点的重要性, 传播的信息较少, 因此EC是最不重要的.比较结果如表1所示.

表1 三标度法构建重要性指标的比较值 

Table 1 The comparison of the importance indicator of the three scales method

在表1中,

然后, 按照极差法把比较矩阵CV构造成判断矩阵[8].

最后, 经一致性检验, 得到各指标的权重分别为wEC=0.0727, wDC=0.4218, wBC=0.2088, wcc=0.2967.

步骤4:计算各个节点的最大化群效用值Si、最小化个体遗憾值Ri和Qi的值.

Si=∑mj=1wjf∗j−vi(fj)f∗j−f−j$S{}_i={\displaystyle {\sum }_{j=1}^{m}w}{}_j\frac{f{}_j^{*}-v{}_i\left(f{}_j\right)}{f{}_j^{*}-f{}_j^{-}}$, (9)

Ri=maxj[wjf∗j−vi(fj)f∗j−f−j]$R{}_i=\max {}_j\left[w{}_j\frac{f{}_j^{*}-v{}_i\left(f{}_j\right)}{f{}_j^{*}-f{}_j^{-}}\right]$, (10)

Qi=vSi−S+S−−S++(1−v)Ri−R+R−−R+$Q{}_i=v\frac{S{}_i-S{}^{+}}{S{}^{-}-S{}^{+}}+(1-v)\frac{R{}_i-R{}^{+}}{R{}^{-}-R{}^{+}}$, (11)

其中, S+=miniSi, S-=maxiSi, R+=miniRi, R-=maxiRi, v表示决策机制系数, v∈[0, 1].如果v>0.5, 则表示决策依据最大化群效用的决策机制进行;v<0.5, 则表示决策依据最小化个体遗憾的决策机制进行;v=0.5, 则表示根据决策者的协商进行决策.

步骤5:由Si、Ri和Qi三个排序列表对节点进行排序, 数值越小表示方案越优.

3 网络效率分析

为验证VIKOR方法在物流仓储节点选址中的性能, 本文利用网络效率进行分析, 将VIKOR方法与TOPSIS方法[4]和随机失效方法[9]进行比较.网络效率[10]表示网络的连通性能, 其值越大, 代表网络的连通能力越强.网络效率由公式 (12) [11]给出:

ε=1N(N−1)∑i,j∈G,i≠j1Γij$\epsilon =\frac{1}{{\rm N}({\rm N}-1)}{\displaystyle {\sum }_{i,j\in G,i\ne j}\frac{1}{\Gamma {}_{ij}}}$, (12)

其中, Γij表示节点i到节点j的最短路径长度, ε的取值范围为[0, 1], ε=1表示网络的连通性最好, ε=0表示网络的连通性最差.

本文通过删除部分节点对网络遭受蓄意攻击和随机攻击进行仿真实验, 网络效率的下降速度可以刻画方法的有效性.网络效率下降速度越快, 证明该方法识别重要节点的效果越好.网络效率的相对值fk由公式 (13) [4]给出:

fk=εkε0(i=1,2,3)$f{}_k=\frac{\epsilon {}_k}{\epsilon {}_0}(i=1,2,3)$, (13)

其中, 初始网络效率ε0=0.0996, εk(k=1,2,3)$\epsilon {}_k\left(k=1,2,3\right)$表示以VIKOR方法、TOPSIS方法、随机失效方法排名发生节点失效时的网络效率.

复杂网络中使用不同的评价方法, 删除同样数量的节点后网络效率的值会不尽相同.为更直观地比较VIKOR方法和其他两种方法的性能, 我们引入网络效率偏差值, 其可由公式 (14) [4]给出:

fk1=fk-f1 (k=2, 3) . (14)

当△fk1≻0时, 表示VIKOR方法的性能优于TOPSIS方法和随机失效方法;反之, TOPSIS方法和随机失效方法优于VIKOR方法.

以上海为例, 分别采用三种方法依次攻击排名前45的节点, 结果如图1和图2所示.图1给出了不同方法攻击下的上海轨道交通网网络效率相对值变化情况, 可以看出采用VIKOR方法攻击前28节点时, 网络效率的下降速度最快.例如, 当前10个节点失效后, 由VIKOR方法、TOPSIS方法、随机失效方法得到的网络效率降至0.59, 0.64和0.94, 这说明了VIKOR方法在识别网络中重要节点上的是很有效的.攻击该网络排名前28-45的节点时, VIKOR方法逐渐与TOPSIS方法重合, 但仍优于随机失效方法.图2给出了TOPSIS方法、随机失效方法与VIKOR方法相比网络效率偏差值的变化情况, 根据曲线的走势可以看出VIKOR方法优于TOPSIS方法、随机失效方法.当攻击排名28-45的节点时, TOPSIS方法接近于VIKOR方法表现出较好的性能.综上所述, VIKOR方法总体上比TOPSIS方法、随机失效方法更能准确地识别上海重要的物流仓储节点, 由此证明了本文所提方法的合理性.

图1 不同方法攻击下的物流仓储节点网络效率相对值变化 

Fig.1 The relative efficiency changes of logistics warehouse node network under different attack methods

图2 VIKOR方法与TOPSIS、随机失效方法的网络效率偏差值变化   

Fig.2 The variation of network efficiency deviation between VIKOR method and TOPSIS and random failure method

4 结论

本文基于复杂网络理论和多属性决策方法, 考虑轨道交通网的拓扑结构特征, 结合相关研究成果, 将VIKOR方法引入到物流仓储节点的选址, 从局部属性、传播属性、全局属性和拓扑属性四个方面综合描述网络节点的重要性, 排序结果符合实际情况.此外, 采用网络效率分析, 将VIKOR方法与TOPSIS方法和随机失效方法进行了比较, 仿真实验结果表明VIKOR方法具有更好的准确性和应用性.

将VIKOR方法应用于物流仓储节点的选址, 不仅拓展了该方法的应用领域, 也为选择仓储节点的地址提供了新的分析工具.对于VIKOR方法的进一步优化, 并在不同类型的复杂网络中应用, 值得进一步探索.