多层网络中心度在航空网络中的应用研究

2015-05-30 10:33毕京浩张瑞马夏夏
2015年3期

毕京浩 张瑞 马夏夏

摘要:利用多层复杂网络理论和方法,构建多层航空网络,说明其结构特性。将多层网络中心度应用于航空网络的研究,找出多层航空网络的多层中心节点。

关键词:多层网络;多层中心度;航空网络

一、引言

近年来,对于复杂网络的研究已经深入到各个领域,复杂网络理论在交通、电力、计算机、生物等领域应用广泛。国内对于复杂网络的研究多集中在单层的网络中,随着对于复杂网络理论研究的深入,国外学者开始关注多层复杂网络的研究。

多层网络是由多个网络或者交互的多个不同实体之间的复杂系统构成[1]。多层网络的每一层是不同行为、不同属性的抽象,它是复杂网络的延伸,它可以用来解决单层网络中不同网络或不同实体之间复杂的连接关系,使网络中的关系更加清晰可见。

单层网络用度、平均路径长度和介数等指标来描述单层网络的统计特性,多层网络也需要相应的指标来描述和衡量。Bródka P最先提出了多层网络中心度这个指标,并将它应用于多层社会网络的研究[2]。文中通过分析Web社交网络中的真实数据,将网络分为10层,并找出了社交网络的中心。本文拟将多层网络中心度应用于多层航空网络的研究,分析多层航空网络的邻居节点,并找出多层航空网络的中心。

二、多层航空网络的构建

1.航空网络的特征描述

航空网络是指在一定区域内由若干条航线按照某种方式连接组成的复杂系统,包括机场、航线和飞机等要素[3]。多层航空网络将机场看作节点,将机场之间的航线看作边,将不同的航空公司看作层,由于只考虑机场之间的连接关系,所以把多层航空网络抽象为多层非加权网络。

2.多层航空网络的构建

定义:定义多层航空网络为一个元组。V是一个非空节点集,每个节点代表一个机场;E是边集,它也是一个元组,对于两个元组,如果,那么它们位于不同的层,即;L是层集,每一层代表一个航空公司。

每个元组是在l层由节点x到节点y连接的一条边,即机场x和y之间的一条航线,任意两个节点之间只有一条边。由于机场间的航线是互通的,所以多层航空网络是一个无向网络,因此。

对于某一层l的节点集V和边集E,构成了一个简单的单层网络。

一个多层航空网络可以有一个多层图来表示。图1是代表一个三层的航空网络。图中有5个节点,在层和中,它们相互连接。对于层来说,存在5个连接关系:

图1多层航空网络示例

3.主要统计量

(1)邻居节点。多层网络是由多个单层网络组成,因此可以定义为两个不同邻居节点集。

a.单层邻居节点。只考虑多层航空网络中的一层,可以看作为单层网络,对应的即单层邻居节点。

Nx,1=y:x,y,l∈E

x是位于l层的一个节点,x∈V,l∈L。

b.多层邻居节点。多层邻居节点是在a1≤a≤L层与给定节点x相连接的节点集。

MNx,a=y:1:x,y,1∈E≥a

在图1中,节点x的多层邻居节点为:

MNx,1=y,z

MNx,2=y,u

MNx,3=z

(2)多层中心度。中心度代表着节点在网络中的重要性。多层中心度可以定义为节点x与对应的多层邻居节点之间的权重总和与层的数量和多层网络所有节点数的比值。

MCDx,a=y∈MNx,awx,y,lm-1L

wx,y,l是边x,y,l的权重,对于本文来讲,权重为1。

三、实证分析

1.多层航空网络特征描述。

本文选取的数据为欧洲四家航空公司的航线数据[4,5]。将位于不同城市的机场作为一个节点,机场之间的航线作为边,构造了一个多层无向非加权的航空网络。

多层航空网络中共有335个机场节点,974条边,如表1所示。其中,如果不考虑层的不同,共有207个节点。其中,有128个节点是重复的,重复的节点意味着不同的航空公司在同一城市均有机场。Lufthansa和Ryanair公司的机场数超过100,也拥有更多的航线。

表1每一层的节点数和边数

2.多层邻居节点

图2是层1的多层邻居节点分布图。从图中可以看到,大部分的节点含有较少的多层邻居节点,多层邻居节点的数量超过12的节点数量平均为1~2个,说明Lufthansa公司所在机场的航线只有少数是比较密集的。如图3所示,超过70%的节点的邻居节点数少于10,超过30个邻居节点的节点不到10%。多层邻居节点的分布体现了多层航空网络的无标度性。

图2多层邻居节点图()

图3多层邻居节点分布统计()

图4为各层的邻居节点分布图,层1和层2分布相似,它们均含有较多的节点和边。每个层的邻居節点分布都符合无标度网络的性质。

图4多层邻居节点图()

图5为多层邻居节点条形图,邻居节点的数量以10个单位为分割。从图中可以看出,随着范围的递进,每层中的节点数量逐步在减少,在邻居节点数达到(21,30)的范围之后对应的节点数明显减少。统计结果显示,每一层的节点数在不同范围内呈现出相同的下降趋势,侧面反映出每个航空公司对于机场和航线的拓扑结构相似。

图5多层邻居节点条形图

3.多层中心度

多层中心度MCDx,a取决于多层邻居节点MNx,a,当MNx,a>0,MCDx,a>0。图6是第一层中各节点的多层中心度分布,从图中可以看出,节点多集中在多层中心度为0.02以下的区域,高于0.04的节点较少。节点中心度表明节点在多层网络中的重要程度。从图中可以看出,在第一层中只有少数的节点在多层航空网络中作用很大。

图6多層中心度分布图()

图7是各层节点的多层分布图,每一层的分布与第一层的分布类似。图中多个图形重叠的节点代表不同航空公司在该城市均有机场。从图中可以找出多层中心度较高的几个关键节点。表2是每一层节点的多层中心度的变化范围。

图7多层中心度分布图(a=1,2,3,4)

表2多层中心度范围

层号1234

最小值1.21E-31.21E-31.21E-31.21E-3

最大值9.59E-21.06E-11.06E-16.55E-2

表3给出了节点中心度大于0.5的几个节点的多层中心度。通过表3可以直观的看出多层中心度最大的为节点12,总共有8个节点的多层中心度大于0.5。结合多层航空网络,这8个节点对应的机场就相当于航空网络中几个重要的机场,节点12对应的机场即要找的多层航空网络的中心。

表3部分节点的多层中心度

节点多层中心度

1660.052

110.053

400.064

710.065

1080.067

20.096

380.096

120.106

四、结论与展望

通过分析多层航空网络的各节点的多层中心度,找出了多层航空网络的中心节点。未来的主要工作是结合实际情况研究该中心节点的实际意义,可从以下几个方面进行:

(1)在航空公司布局机场时,可优先考虑多层中心节点的布局,同时考虑多层中心度较大的其他节点,以便更好地发展业务;或者在已经布局了多层中心节点时,可提供更优质的服务来增强竞争力。

(2)对于航空网络脆弱性研究方面,优先考虑对多层中心节点提供保护措施。

(3)可以将多层中心度拓展应用于其他多层网络的计算。

(4)可以将现有算法进行优化,提高计算效率。(作者单位:济南大学管理学院)

参考文献:

[1]Kivel M, Arenas A, Barthelemy M, et al. Multilayer networks[J]. Journal of Complex Networks, 2014, 2(3): 203-271.

[2]Bródka P, Skibicki K, Kazienko P, et al. A degree centrality in multi-layered social network[C]//Computational Aspects of Social Networks (CASoN), 2011 International Conference on. IEEE, 2011: 237-242.

[3]俞桂杰, 彭语冰, 褚衍昌. 复杂网络理论及其在航空网络中的应用 [J]. 复杂系统与复杂性科学, 2006, 3(1): 79-84.

[4]Stark C, Breitkreutz B J, Reguly T, et al. BioGRID: a general repository for interaction datasets[J]. Nucleic acids research, 2006, 34(suppl 1): D535-D539.

[5]De Domenico M, Porter M A, Arenas A. MuxViz: a tool for multilayer analysis and visualization of networks[J]. Journal of Complex Networks, 2014: cnu038.