第3卷第1期
2006年3月复杂系统与复杂性科学 COMPLEXSYSTEMSANDCOMPLEXITYSCIE
NCEVol.3No.1Mar.2006
文章编号:1672-3813(2006)01-0079-06
复杂网络理论及其在航空网络中的应用
俞桂杰,彭语冰,褚衍昌
(中国民航大学管理学院,天津300300)
摘要:复杂网络理论是对复杂系统的高度抽象,它突出强调了系统的拓扑特征,其
中许多性质如小世界性质、无标度性质等等已经得到了广泛的研究。本文从复杂
网络的统计特性、结构模型以及在航空网络中的应用3个层次系统回顾了复杂网
络的基本理论和应用现状,期望对航空网络规划问题的研究起到一定的借鉴作用。
关键词:复杂网络;小世界网络;无标度网络;航空网络
中图分类号:N94;F560文献标识码:A
ComplexNetworksTheoryandItsApplicationinAirYUGui2jie,PENGYu22(SchoolofManagement,Civil300300,China)
Abstract:isabstractedfromcomplexsystems.Itemphasizesonthetopologiesofms.propertiessuchassmall2worldcharacteristics,scale2freecharacteristicsarealreadythorresearched.Inthispaper,webrieflyreviewthestudiesaboutcomplexnetworksfromthreelevels,statisticalpropertiesstructuremodelanditsapplicationsespeciallyintheairnetworks.
Keywords:complexnetworks;small2worldnetworks;scale2freenetworks;airnetworks
1 引言
从1736年德国数学家Euler解决哥尼斯堡七桥问题开始,人们就发现现实世界中的许多复杂系统从拓扑结构的角度看都可以抽象为网络。至于用什么样的网络拓扑结构才能比较准确地描述出真实的系统,这个问题的研究大致经历了3个阶段:规则网络、随机网络(ER模型)和复杂网络(小世界网络和无标度网络)[1]。
从1998年至今,大量关于复杂网络的文章在Science、Nature、PRL等国际一流的刊物上发表,已经成为国际学术界一个新兴的研究热点。
目前,国内外的研究工作主要集中在以下几个方面[2]:1)通过实证方法来度量网络的静态统计特征;2)基于对实际网络形成机理的理解和解释,构建出具有和实际网络相同或类似性质的复杂网络模型;3)复杂网络上的动力学研究,即预测网络系统的行为,包括网络容错性和攻击鲁棒性,以及网络上的传播、同步等
各种动力学过程。
本文首先对复杂网络的理论研究现状作简单描述,然后对复杂网络在航空网络中的应用研究作了系统的综述,并提出一些有待解决的问题。
收稿日期:2006-04-25
作者简介:俞桂杰(1980-),男,福建人,在读硕士研究生,主要研究方向为民航航线网络规划。
复杂系统与复杂性科学・8
0・2006年3月2 复杂网络的静态统计量
2.1 度和度分布(degree°ree2distribution)
节点度k就是该点所连接的边数,可用分布函数p(k)来描述具有相同度k的节点的出现概率。度是描述网络局部特性的基本参数;度分布函数则反映了网络系统的宏观统计特征。
2.2 簇系数(或称集群系数,clusteringcoefficient)
节点的簇系数被定义为它所有相邻节点之间的实际连接数目占可能的最大连接边数目的比例,网络的簇系数C则是所有节点簇系数的平均值。
2.3 平均路径长度(或称平均距离,averagepathlength)
网络中任意两点间的距离被定义为连接两点的最短路所包含的边的数目,把所有节点对的距离求平均,就得到了网络的平均路径长度L。
2.4 度的相关性(assortativity)
[3]Newman把它称为“匹配模式(AssortativeMatching)”,即考察度值大的点倾向于和度值大的(或是小
的)点连接。具体的方法是,通过任意一条边都可以找到两个顶点,进而得到两个度值,这样通过所有的边我们就得到了两个序列,分析这两个序列的相关性即可。
2.5 介数(betweenness)
节点的介数定义为[4]:,,[5,6]数较大的节点;类似地,可以定义边的介数,,这对
上述5,,复杂网络还存在着大量其他的统计指标,例如混合模式[7],。限于篇幅,本文不再赘述。3 复杂网络的拓扑模型及其特性
3.1 Small2world网络
[9]Watt和Strogatz(WS)发现,对于规则网络,以概率p断开一个顶点,并重新连接,当p=0时就是规则
网络,p=1则为随机网络,对于0
表1 不同网络拓扑模型的统计特征比较
规则网络
C
L
p(k)随机网络较小,C=/N较小,L～lnN服从泊松分布
(n,p),n是节点数,
p是边的概率。WS小世界网络BA无标度网络较大,C=较大,L～Nδ(k-k0)-较大(与N无关)较小,L～N/2k服从指数分布(n,k,p),n是节点数,每个节点与自己的第k个邻居建立无向连接,p是较小,C～(lnN)2/N[13]较小,L～lnN服从幂律分布p(k)～k-γ(n0,m,t),n0是初始节点数;
m(m≤n0)是新节点所带的边数;t表模型涉及
的参数每条边被重置的概率。
1)初始化时,n个初始节点均匀分布示接入的新节点个数。1)初始化,引入n0个孤立节点;2)
模型的算法-从n个孤立点开始对任意一对顶点,以
概率p连接。在圆周上,每个节点与自己的第k个邻居建立连接;2)对每条初始化后
的边,以概率p用一条随机边取代。对下面步骤执行t次:把带有m条边的新节点v连向网络中已有的m个节点,节点i与v连接的概率是:p
(ki)=ki/kj。
注:资料来源:笔者根据文献[2,13]所做的总结。
第3卷第1期 俞桂杰,等:复杂网络理论及其在航空网络中的应用・8
1・
3.2 Scale2free网络
[14]Barabasi和Albert(BA)研究了www和新陈代谢网等大型网络,发现决定真实网络演化的两个基本因
素是增长(growth)和择优连接(preferentialattachment),这两个因素会导致网络的节点度遵从幂律分布,这就是无标度特性,对局部环境受到的随机攻击,它能表现出良好的鲁棒性(Robustness),但遇到针对网络中枢
[2,14]纽点的攻击,就显得比较脆弱。因此,无标度网络是复杂网络研究的重点,具有很大应用潜力,如可以利
[2,5,11]用来预防交通堵塞,防止黑客侵入互联网、消除电力网灾变和阻止致命流行病的传播等等。
4 复杂网络在航空网络中的应用
4.1 航空网络的特征描述
航空网络是指在一定区域内由若干条航线按照某种方式连接组成的复杂系统,包括机场、航线和飞机等要素。如果把机场看作节点,连接机场的航线看作边,机场的吞吐量看作点权,航线上的运量(或航程)看作边权,这样就可以把航空网络抽象为一个复杂加权网络。航空网络除了具有绝大多数复杂加权网络的共性特征外,还拥有自己的特征:
1)网络的规模不大,节点个数一般是从几百个到几千个(至多),而网络规模的大小会影响对现有网络特征的准确分析和判断。
2)航空网络是多维的,而且交通流的主体(旅客),这点
[15]明显区别于地面交通网络。
3)网络是双向的、加权的,,权值都相差悬殊。
4),这是因为航空网络的节点间的连接就是两个机场间的航班,,这和其它领域的网络不同,而且航空网络在发生大枢纽点堵塞而导致网络瘫痪时,,即把该枢纽点移除或隔离了就能解决问题。
5)航空网络不仅包括机场网络,更包括航空公司的航线网络,而且在航空网络构造中,航空公司的主体作用更明显。因此,两种网络应该结合研究,才能找到更适合实际运营的网络模型。
4.2 利用复杂网络理论研究航空网络的意义
在航空网络领域内的许多问题,比如:
1)Hub点的确定一直是航空网络设计的重点和难点。
2)新机场选址以及和原有网络的航线连接问题。
3)轮辐式航线网络(Hub2and2SpokeNetworks)明显具有无标度特性,其虽然具有成本上的节约和效率上的提高,然而也会带来系统安全和稳定性方面的问题,目前世界上至少有150个枢纽机场都出现机场严重堵塞现象,经常面临着航班延误问题。
等等这些问题都可以依靠复杂网络的相关理论来解决,在此基础上,将网络交通流模型与复杂网络特性相结合进行研究,探讨未来航空网络的一般演化规律,最终目标是形成描述航空网络演化一般规律的数学刻画,为未来航空网络的发展提供决策上的支持。这就说明了利用复杂网络理论研究航空网络是可行的而且必要的。
4.3 复杂网络理论在航空网络研究中的应用研究
目前,国内外有关复杂网络的应用研究领域主要有:生命科学领域的各种网络、Internet、社会关
[2,4,16]系网络等,但在航空网络方面的研究成果还相对较少,主要集中在两大方面:
1)描述世界或各国范围内的现有机场网络的静态统计量以及各统计量与度k之间的(非线性)函数关系,下面列举几篇这方面的研究文献:
[17,18]R.Guimera和L.A.N.Amaral作了针对2002年世界机场网络的研究,得出了两个重要结论:(1)世
界范围的机场网络具有小世界网络的特征,度分布和介数BC分布都服从幂律分布;(2)节点度最大的城市[2,11,12][2]
复杂系统与复杂性科学・82・2006年3月不一定就是枢纽城市(介数最大的)。这第两个结论无法按现有的网络模型来解释,因此他们又提出了一个基于地缘政治限制的新模型,即在一个国家内只有个别的门户机场能和国外机场连接,其它机场就只能在国内连接,由此考虑其对机场网络增长的影响,结果很好地解决了上述现象。
[19-21]华中师大的蔡勖等连续研究了中国和美国的机场网络的拓扑结构特征,得到了相似的结论:具有
小世界性质,而且有向和无向的机场网络的度分布都服从两阶段不同指数的幂函数分布,即所谓的双帕雷托律;每个机场的出度和入度正相关,而无向网络中某个机场的度与周围机场的度的平均值则表现出明显的线性负相关(反方向变化);如果把航线上一天或一周的航班看作是边权,则它的分布也呈幂律分布,而且,边权大小与航线两端机场的度(机场的航线条数)成比例;每个子簇(即把一个机场和它周围所连接的机场看作是一个子簇)的平均路径与它的连接密度成反比。
[22]此后印度的GaneshBagler应用类似的统计分析方法,研究了印度国内的机场网络(ANI),得出了类
似中国机场网络的结论,并和世界范围的机场网络(WAN)的特征作比较,刻画出发展中国家特有的航空网络演化历程。
表2 航空网络结构的实证结果
机场数
2002年世界
2003年中国
2003年美国
2004年印度[1**********]9航线数[***********]max(k)318101--9.7018.2014.005.CLp(k)～k-a中的a0.6200.7336184.3702.2.26021.450 5.5351.567 4.3362.2
注:资料来源于笔者根据文献[]2),可视为复杂网络研究中最基础的一步。当然,正是通过分析现实世界中网络统计特征并提炼出它们的共性,才有了小世界网络和无标度网络理论的提出。对更多的实际机场网络数据的分析可能发现其它新的共性,借此来构建新的更符合实际特性的网络模型。
在寻找并构建合适的网络模型方面,Barrat、Barthelemy和Vespignani(BBV)在2004年做了一系列很有
[23-25]影响力的工作,他们最早提出了基于交通流驱动的加权演化模型(见图1):从N0个点的完全网开始演
化,新点n以Si/6jSj
的概率和节点i相连结,边权变化为Δwij=wij
si
。这样,可以同时获得点权、点度和边
权的幂律分布,这与绝大部分真实网络(包括WAN)比较符合,但BBV模型无法解释真实网络所具有大的簇系数、非相称混合性问题以及度权非线性相关等其他特性。
对于上述问题的改善,国内的汪秉宏等学者所做的尝试性研究比较成功,他们在BBV模型的基础上考虑两个机制:一是拓扑生长,二是强度耦合的同步。即用相乘作用机制将新点的加入和老点的演化统一化(见图2),模型规则大致分为两部分,如下:[26]
图1 BBV模型图2 汪秉宏等人的模型
第3卷第1期 俞桂杰,等:复杂网络理论及其在航空网络中的应用・8
3・ (1)新点加入:每一时间步加入一个新点,和已有网络中的老点连m条边,偏好概率为Si/
系进行分配,若某两点被分到了1,他们之间有边则边权+1,否则两点之间连接一条新边。6jSj。(2)老点的演化:每一时步,已有的网络内总的流量的增长为整数W(可以看成是W个1),按照相乘关
他们从实现网络的功能的角度对模型的解释为:新加进的点由于相乘作用机制,和权大的点之间的流量大,所以偏好于和权大的点相连,这样可以尽可能地分担其它点和新点之间的流量。正是后者这种机制导致网络的交通流量和网络的几何结构特征的相互作用,使模型结果与实际数据符合得很好,仅用一个参数,即边权的总增量W进行调控,同时给出网络连接度分布的幂函数律、网络强度分布的幂函数律、网络权重分布的幂函数律,以及高聚集性和非相称混合性等5大特征,较好地刻画了真实网络的无尺度性质和小世界效应。该模型很适合于构造各种交通负荷增长速率的技术网络,对于交通运输网络尤其是航空网络的研究具有很好的参考作用。当然也有需要改进之处[27]:例如,对网络交通流,模型只考虑随机性没有考虑确定性因素,这不符合航空网络结构具有相对的时空稳定性的特征。
国际上对航空网络最系统的研究开始于2003年12月进行的由美国航空与航天管理局(NASA)下属的
[28,29]兰利研究中心和美国宇航研究所(NIA)合作组织的有关未来航空网络拓朴结构的专题研讨会。他们分
别应用了地理信息系统(GIS)、复杂网络、图论、仿真、数学规划和基于主体的建模方法(ABM)6种理论方法来研究包括航空网络在内的交通网络的拓扑结构,发现GIS系统能与其它方法相结合库和地图定位平台,组合成空间决策支持系统(SDSS)。,,进一步的研究还发现::界和无标度特征,;制,和FLEXJET公司实际运营为例,提出了与轮2优势,而且在空中飞行的飞机过多容易引发安全问题。[29],其优点是小飞机运营能方便利用上千个空闲的通用航空机场;缺点是无法利用枢纽机场和大型飞机运营的规模经济
5 结束语和展望
由于复杂网络的部分理论研究尚未成熟,例如,LunLi等人
动复杂网络的研究。
从文献[28,29]的分析可以看出:目前,复杂网络已经成为分析现有航空网络,构造未来航空网络的有利工具,但仍有很多极具挑战性的问题需要解决,主要表现在以下3大方面:
1)网络的结构特征方面:应用现有的复杂网络理论是否已经把网络的结构特征描述清楚了?是否有更多的网络统计特征尚未被发现?航空网络的拓扑结构应该是什么样的才是最理想的?如果我们要设计出混合型网络(包含轮辐式网络和城市对网络等),那么需要体现出哪些网络特征?不同拓扑结构特性以及网络规模是如何对Hub点位置产生影响的?究竟什么样的网络结构才能使航空公司、国家、世界等层次上的航空网络都体现出无标度特性?航空网络本质上是空间加权网络,如何衡量节点城市的空间地理位置、政治环境等重要因素对网络结构的影响和变化?
2)网络的模型演化方面:在机场容量或航线流量有限制的情况下,择优连接机制会受到多大影响?如何综合考虑度、距离、成本等因素计算已有节点被新节点选择的概率?网络在t时刻的状态如何用精确的解析表达式来预测?如何通过构建系统的目标解析函数来优化系统性能?
3)网络的鲁棒性和可靠性方面:未来高度复杂的网络应该能应付突发事件的发生,航空网络能容许多少的不确定性?即网络应该有多大的控制能力?网络演化到何种程度会引起Hub点发生变化?
等等这些问题的涌现表明:这是一项很有吸引力、难度也很大的研究课题。因此,如何进一步深化理论[30]认为目前关于无标度网络的定义含糊不清,缺乏精确的数学证明等等。因此,需要从更深层次的理论高度以及理论与实际相结合的方向来进一步推
复杂系统与复杂性科学・8
4・2006年3月的研究,并把研究成果尽快地应用于航空网络中去,这正是该领域深入研究的迫切要求和进一步发展的推动力所在。
参考文献:
[1]周涛,柏文洁,汪秉宏,等.复杂网络研究概论[J].物理,2005,34(1):31-36.
[2]BoccalettiS,LatoraV,MorenoY,etal.Complexnetworks:structureanddynamics[J].PhysRep,2006,424:175-308.
[3]NewmanMEJ.Modelsofthesmallworld[J].JStatPhys,2000,101:819-841.
[4]NewmanMEJ.Thestructureandfunctionofcomplexnetworks[J].SIAMReview,2003,45(2):167-256.
[5]BarabasiAL,BonabeauE.Scale2freenetworks[J].ScientificAmerican,2003,5(1):60-69.
[6]解㑇,汪小帆.复杂网络中的社团结构分析算法研究综述[J].复杂系统与复杂性科学,2005,2(2):1-12.
[7]NewmanMEJ.Propertiesofhighlyclusterednetworks[J].PhysRevE,2003,68:026121.
[8]TaoZhou,Bing2HongWang,Pin2QunJiang.Adeterministicsupersmall2worldnetworkofintegers[J].2004,arXiv:cond2mat/
0405258.
[9]WattsDJ,StrogatzSH.Collectivedynamicsofsmallworldnetworks[J].Nature,1998,393:440-442.
[10]StrogatzSH.Exploringcomplexnetworks[J].Nature,2001,410:268-276.
[11]HethcoteHW.Themathematicsofinfectiousdiseases[J].SIAMReview,2000,42:599-653.
[12]JeongH,TomborB,AlbertR,etal.Thelarge2scaleorganizationofmetabolicnetworks[J].407:651-654.
[13]SzaboG,AlavaM,KerteszJ.Structuraltransitionsinscale2freeorks[J056102.
[14]BarabasiAL,AlbertR.EmergenceofscalinginrandomnetwJ1999,.
[15]MichaelT.Gastner,NewmanMEJ.ThespatialwJB,2006,49:247-252.
[16]NewmanMEJ.ScientificI:andfundamentalresults[J].PhysRevE,2001,64:
016131.
[17]GuimeraR,A,etal.Theworld2wideairtransportationnetwork:anomalouscentrality,communitystructure,
andcities’globalJ].PNAS,2005,102(31):7794-7799.
[18]GuimeraR,AmaralLAN.Modelingtheworld2wideairportnetwork[J].EurPhysJB,2004,38:381-385.
[19]LiW,CaiX.StatisticalanalysisofairportnetworkofChina[J].PhysRevE,2004,69:046106.
[20]ChiLi2Ping,WangRu,SuHang,etal.StructuralpropertiesofUSflightnetwork[J].ChinPhysLett,2003,20:1393-1396.
[21]WangRu,CaiXu.Hierarchicalstructure,disassortativityandinformationmeasuresoftheUS[J].ChinPhysLett,2005,22:2715
-2718.
[22]BaglerG.AnalysisoftheairportnetworkofIndiaasacomplexweightednetwork[J].2004,arXiv:cond2mat/0409773.
[23]BarratA,BarthélemyM,Pastor2SatorrasR,etal.Thearchitectureofcomplexweightednetworks[J].PNAS,2004,101:3747-
3752.
[24]BarratA,BarthélemyM,VespignaniA.Modelingtheevolutionofweightednetworks[J].PhysRevE,2004,70:066149.
[25]BarratA,BarthélemyM,VespignaniA.Weightedevolvingnetworks2couplingtopologyandweightsdynamics[J].PhysRevLett,
2004,92:228701.
[26]Wen2XuWang,Bing2HongWang,BoHu,etal.Generaldynamicsoftopologyandtrafficonweightedtechnologicalnetworks[J].
PhysRevLett,2005,94:188702.
[27]方锦清.无标度复杂网络的研究面对的挑战[A].第二届全国复杂网络会议论文[C].武汉,2005.
[28]AlexandrovN.Transportationnetworktopologies[Z].NASA/TM-2004-213259,2004.
[29]KubyM,TierneyS,RobertsT,etal.Acomparisonofgeographicinformationsystems,complexnetworks,andothermodelsfor
analyzingtransportationnetworktopologies[Z].NASA/CR-2005-213522,2005.
[30]LunLi,AldersonD,TanakaR,etal.Towardsatheoryofscale2freegraphs:definition,properties,andimplications[J].2004,
arXiv:cond2mat/0501169.
第3卷第1期
2006年3月复杂系统与复杂性科学 COMPLEXSYSTEMSANDCOMPLEXITYSCIE
NCEVol.3No.1Mar.2006
文章编号:1672-3813(2006)01-0079-06
复杂网络理论及其在航空网络中的应用
俞桂杰,彭语冰,褚衍昌
(中国民航大学管理学院,天津300300)
摘要:复杂网络理论是对复杂系统的高度抽象,它突出强调了系统的拓扑特征,其
中许多性质如小世界性质、无标度性质等等已经得到了广泛的研究。本文从复杂
网络的统计特性、结构模型以及在航空网络中的应用3个层次系统回顾了复杂网
络的基本理论和应用现状,期望对航空网络规划问题的研究起到一定的借鉴作用。
关键词:复杂网络;小世界网络;无标度网络;航空网络
中图分类号:N94;F560文献标识码:A
ComplexNetworksTheoryandItsApplicationinAirYUGui2jie,PENGYu22(SchoolofManagement,Civil300300,China)
Abstract:isabstractedfromcomplexsystems.Itemphasizesonthetopologiesofms.propertiessuchassmall2worldcharacteristics,scale2freecharacteristicsarealreadythorresearched.Inthispaper,webrieflyreviewthestudiesaboutcomplexnetworksfromthreelevels,statisticalpropertiesstructuremodelanditsapplicationsespeciallyintheairnetworks.
Keywords:complexnetworks;small2worldnetworks;scale2freenetworks;airnetworks
1 引言
从1736年德国数学家Euler解决哥尼斯堡七桥问题开始,人们就发现现实世界中的许多复杂系统从拓扑结构的角度看都可以抽象为网络。至于用什么样的网络拓扑结构才能比较准确地描述出真实的系统,这个问题的研究大致经历了3个阶段:规则网络、随机网络(ER模型)和复杂网络(小世界网络和无标度网络)[1]。
从1998年至今,大量关于复杂网络的文章在Science、Nature、PRL等国际一流的刊物上发表,已经成为国际学术界一个新兴的研究热点。
目前,国内外的研究工作主要集中在以下几个方面[2]:1)通过实证方法来度量网络的静态统计特征;2)基于对实际网络形成机理的理解和解释,构建出具有和实际网络相同或类似性质的复杂网络模型;3)复杂网络上的动力学研究,即预测网络系统的行为,包括网络容错性和攻击鲁棒性,以及网络上的传播、同步等
各种动力学过程。
本文首先对复杂网络的理论研究现状作简单描述,然后对复杂网络在航空网络中的应用研究作了系统的综述,并提出一些有待解决的问题。
收稿日期:2006-04-25
作者简介:俞桂杰(1980-),男,福建人,在读硕士研究生,主要研究方向为民航航线网络规划。
复杂系统与复杂性科学・8
0・2006年3月2 复杂网络的静态统计量
2.1 度和度分布(degree°ree2distribution)
节点度k就是该点所连接的边数,可用分布函数p(k)来描述具有相同度k的节点的出现概率。度是描述网络局部特性的基本参数;度分布函数则反映了网络系统的宏观统计特征。
2.2 簇系数(或称集群系数,clusteringcoefficient)
节点的簇系数被定义为它所有相邻节点之间的实际连接数目占可能的最大连接边数目的比例,网络的簇系数C则是所有节点簇系数的平均值。
2.3 平均路径长度(或称平均距离,averagepathlength)
网络中任意两点间的距离被定义为连接两点的最短路所包含的边的数目,把所有节点对的距离求平均,就得到了网络的平均路径长度L。
2.4 度的相关性(assortativity)
[3]Newman把它称为“匹配模式(AssortativeMatching)”,即考察度值大的点倾向于和度值大的(或是小
的)点连接。具体的方法是,通过任意一条边都可以找到两个顶点,进而得到两个度值,这样通过所有的边我们就得到了两个序列,分析这两个序列的相关性即可。
2.5 介数(betweenness)
节点的介数定义为[4]:,,[5,6]数较大的节点;类似地,可以定义边的介数,,这对
上述5,,复杂网络还存在着大量其他的统计指标,例如混合模式[7],。限于篇幅,本文不再赘述。3 复杂网络的拓扑模型及其特性
3.1 Small2world网络
[9]Watt和Strogatz(WS)发现,对于规则网络,以概率p断开一个顶点,并重新连接,当p=0时就是规则
网络,p=1则为随机网络,对于0
表1 不同网络拓扑模型的统计特征比较
规则网络
C
L
p(k)随机网络较小,C=/N较小,L～lnN服从泊松分布
(n,p),n是节点数,
p是边的概率。WS小世界网络BA无标度网络较大,C=较大,L～Nδ(k-k0)-较大(与N无关)较小,L～N/2k服从指数分布(n,k,p),n是节点数,每个节点与自己的第k个邻居建立无向连接,p是较小,C～(lnN)2/N[13]较小,L～lnN服从幂律分布p(k)～k-γ(n0,m,t),n0是初始节点数;
m(m≤n0)是新节点所带的边数;t表模型涉及
的参数每条边被重置的概率。
1)初始化时,n个初始节点均匀分布示接入的新节点个数。1)初始化,引入n0个孤立节点;2)
模型的算法-从n个孤立点开始对任意一对顶点,以
概率p连接。在圆周上,每个节点与自己的第k个邻居建立连接;2)对每条初始化后
的边,以概率p用一条随机边取代。对下面步骤执行t次:把带有m条边的新节点v连向网络中已有的m个节点,节点i与v连接的概率是:p
(ki)=ki/kj。
注:资料来源:笔者根据文献[2,13]所做的总结。
第3卷第1期 俞桂杰,等:复杂网络理论及其在航空网络中的应用・8
1・
3.2 Scale2free网络
[14]Barabasi和Albert(BA)研究了www和新陈代谢网等大型网络,发现决定真实网络演化的两个基本因
素是增长(growth)和择优连接(preferentialattachment),这两个因素会导致网络的节点度遵从幂律分布,这就是无标度特性,对局部环境受到的随机攻击,它能表现出良好的鲁棒性(Robustness),但遇到针对网络中枢
[2,14]纽点的攻击,就显得比较脆弱。因此,无标度网络是复杂网络研究的重点,具有很大应用潜力,如可以利
[2,5,11]用来预防交通堵塞,防止黑客侵入互联网、消除电力网灾变和阻止致命流行病的传播等等。
4 复杂网络在航空网络中的应用
4.1 航空网络的特征描述
航空网络是指在一定区域内由若干条航线按照某种方式连接组成的复杂系统,包括机场、航线和飞机等要素。如果把机场看作节点,连接机场的航线看作边,机场的吞吐量看作点权,航线上的运量(或航程)看作边权,这样就可以把航空网络抽象为一个复杂加权网络。航空网络除了具有绝大多数复杂加权网络的共性特征外,还拥有自己的特征:
1)网络的规模不大,节点个数一般是从几百个到几千个(至多),而网络规模的大小会影响对现有网络特征的准确分析和判断。
2)航空网络是多维的,而且交通流的主体(旅客),这点
[15]明显区别于地面交通网络。
3)网络是双向的、加权的,,权值都相差悬殊。
4),这是因为航空网络的节点间的连接就是两个机场间的航班,,这和其它领域的网络不同,而且航空网络在发生大枢纽点堵塞而导致网络瘫痪时,,即把该枢纽点移除或隔离了就能解决问题。
5)航空网络不仅包括机场网络,更包括航空公司的航线网络,而且在航空网络构造中,航空公司的主体作用更明显。因此,两种网络应该结合研究,才能找到更适合实际运营的网络模型。
4.2 利用复杂网络理论研究航空网络的意义
在航空网络领域内的许多问题,比如:
1)Hub点的确定一直是航空网络设计的重点和难点。
2)新机场选址以及和原有网络的航线连接问题。
3)轮辐式航线网络(Hub2and2SpokeNetworks)明显具有无标度特性,其虽然具有成本上的节约和效率上的提高,然而也会带来系统安全和稳定性方面的问题,目前世界上至少有150个枢纽机场都出现机场严重堵塞现象,经常面临着航班延误问题。
等等这些问题都可以依靠复杂网络的相关理论来解决,在此基础上,将网络交通流模型与复杂网络特性相结合进行研究,探讨未来航空网络的一般演化规律,最终目标是形成描述航空网络演化一般规律的数学刻画,为未来航空网络的发展提供决策上的支持。这就说明了利用复杂网络理论研究航空网络是可行的而且必要的。
4.3 复杂网络理论在航空网络研究中的应用研究
目前,国内外有关复杂网络的应用研究领域主要有:生命科学领域的各种网络、Internet、社会关
[2,4,16]系网络等,但在航空网络方面的研究成果还相对较少,主要集中在两大方面:
1)描述世界或各国范围内的现有机场网络的静态统计量以及各统计量与度k之间的(非线性)函数关系,下面列举几篇这方面的研究文献:
[17,18]R.Guimera和L.A.N.Amaral作了针对2002年世界机场网络的研究,得出了两个重要结论:(1)世
界范围的机场网络具有小世界网络的特征,度分布和介数BC分布都服从幂律分布;(2)节点度最大的城市[2,11,12][2]
复杂系统与复杂性科学・82・2006年3月不一定就是枢纽城市(介数最大的)。这第两个结论无法按现有的网络模型来解释,因此他们又提出了一个基于地缘政治限制的新模型,即在一个国家内只有个别的门户机场能和国外机场连接,其它机场就只能在国内连接,由此考虑其对机场网络增长的影响,结果很好地解决了上述现象。
[19-21]华中师大的蔡勖等连续研究了中国和美国的机场网络的拓扑结构特征,得到了相似的结论:具有
小世界性质,而且有向和无向的机场网络的度分布都服从两阶段不同指数的幂函数分布,即所谓的双帕雷托律;每个机场的出度和入度正相关,而无向网络中某个机场的度与周围机场的度的平均值则表现出明显的线性负相关(反方向变化);如果把航线上一天或一周的航班看作是边权,则它的分布也呈幂律分布,而且,边权大小与航线两端机场的度(机场的航线条数)成比例;每个子簇(即把一个机场和它周围所连接的机场看作是一个子簇)的平均路径与它的连接密度成反比。
[22]此后印度的GaneshBagler应用类似的统计分析方法,研究了印度国内的机场网络(ANI),得出了类
似中国机场网络的结论,并和世界范围的机场网络(WAN)的特征作比较,刻画出发展中国家特有的航空网络演化历程。
表2 航空网络结构的实证结果
机场数
2002年世界
2003年中国
2003年美国
2004年印度[1**********]9航线数[***********]max(k)318101--9.7018.2014.005.CLp(k)～k-a中的a0.6200.7336184.3702.2.26021.450 5.5351.567 4.3362.2
注:资料来源于笔者根据文献[]2),可视为复杂网络研究中最基础的一步。当然,正是通过分析现实世界中网络统计特征并提炼出它们的共性,才有了小世界网络和无标度网络理论的提出。对更多的实际机场网络数据的分析可能发现其它新的共性,借此来构建新的更符合实际特性的网络模型。
在寻找并构建合适的网络模型方面,Barrat、Barthelemy和Vespignani(BBV)在2004年做了一系列很有
[23-25]影响力的工作,他们最早提出了基于交通流驱动的加权演化模型(见图1):从N0个点的完全网开始演
化,新点n以Si/6jSj
的概率和节点i相连结,边权变化为Δwij=wij
si
。这样,可以同时获得点权、点度和边
权的幂律分布,这与绝大部分真实网络(包括WAN)比较符合,但BBV模型无法解释真实网络所具有大的簇系数、非相称混合性问题以及度权非线性相关等其他特性。
对于上述问题的改善,国内的汪秉宏等学者所做的尝试性研究比较成功,他们在BBV模型的基础上考虑两个机制:一是拓扑生长,二是强度耦合的同步。即用相乘作用机制将新点的加入和老点的演化统一化(见图2),模型规则大致分为两部分,如下:[26]
图1 BBV模型图2 汪秉宏等人的模型
第3卷第1期 俞桂杰,等:复杂网络理论及其在航空网络中的应用・8
3・ (1)新点加入:每一时间步加入一个新点,和已有网络中的老点连m条边,偏好概率为Si/
系进行分配,若某两点被分到了1,他们之间有边则边权+1,否则两点之间连接一条新边。6jSj。(2)老点的演化:每一时步,已有的网络内总的流量的增长为整数W(可以看成是W个1),按照相乘关
他们从实现网络的功能的角度对模型的解释为:新加进的点由于相乘作用机制,和权大的点之间的流量大,所以偏好于和权大的点相连,这样可以尽可能地分担其它点和新点之间的流量。正是后者这种机制导致网络的交通流量和网络的几何结构特征的相互作用,使模型结果与实际数据符合得很好,仅用一个参数,即边权的总增量W进行调控,同时给出网络连接度分布的幂函数律、网络强度分布的幂函数律、网络权重分布的幂函数律,以及高聚集性和非相称混合性等5大特征,较好地刻画了真实网络的无尺度性质和小世界效应。该模型很适合于构造各种交通负荷增长速率的技术网络,对于交通运输网络尤其是航空网络的研究具有很好的参考作用。当然也有需要改进之处[27]:例如,对网络交通流,模型只考虑随机性没有考虑确定性因素,这不符合航空网络结构具有相对的时空稳定性的特征。
国际上对航空网络最系统的研究开始于2003年12月进行的由美国航空与航天管理局(NASA)下属的
[28,29]兰利研究中心和美国宇航研究所(NIA)合作组织的有关未来航空网络拓朴结构的专题研讨会。他们分
别应用了地理信息系统(GIS)、复杂网络、图论、仿真、数学规划和基于主体的建模方法(ABM)6种理论方法来研究包括航空网络在内的交通网络的拓扑结构,发现GIS系统能与其它方法相结合库和地图定位平台,组合成空间决策支持系统(SDSS)。,,进一步的研究还发现::界和无标度特征,;制,和FLEXJET公司实际运营为例,提出了与轮2优势,而且在空中飞行的飞机过多容易引发安全问题。[29],其优点是小飞机运营能方便利用上千个空闲的通用航空机场;缺点是无法利用枢纽机场和大型飞机运营的规模经济
5 结束语和展望
由于复杂网络的部分理论研究尚未成熟,例如,LunLi等人
动复杂网络的研究。
从文献[28,29]的分析可以看出:目前,复杂网络已经成为分析现有航空网络,构造未来航空网络的有利工具,但仍有很多极具挑战性的问题需要解决,主要表现在以下3大方面:
1)网络的结构特征方面:应用现有的复杂网络理论是否已经把网络的结构特征描述清楚了?是否有更多的网络统计特征尚未被发现?航空网络的拓扑结构应该是什么样的才是最理想的?如果我们要设计出混合型网络(包含轮辐式网络和城市对网络等),那么需要体现出哪些网络特征?不同拓扑结构特性以及网络规模是如何对Hub点位置产生影响的?究竟什么样的网络结构才能使航空公司、国家、世界等层次上的航空网络都体现出无标度特性?航空网络本质上是空间加权网络,如何衡量节点城市的空间地理位置、政治环境等重要因素对网络结构的影响和变化?
2)网络的模型演化方面:在机场容量或航线流量有限制的情况下,择优连接机制会受到多大影响?如何综合考虑度、距离、成本等因素计算已有节点被新节点选择的概率?网络在t时刻的状态如何用精确的解析表达式来预测?如何通过构建系统的目标解析函数来优化系统性能?
3)网络的鲁棒性和可靠性方面:未来高度复杂的网络应该能应付突发事件的发生,航空网络能容许多少的不确定性?即网络应该有多大的控制能力?网络演化到何种程度会引起Hub点发生变化?
等等这些问题的涌现表明:这是一项很有吸引力、难度也很大的研究课题。因此,如何进一步深化理论[30]认为目前关于无标度网络的定义含糊不清,缺乏精确的数学证明等等。因此,需要从更深层次的理论高度以及理论与实际相结合的方向来进一步推
复杂系统与复杂性科学・8
4・2006年3月的研究,并把研究成果尽快地应用于航空网络中去,这正是该领域深入研究的迫切要求和进一步发展的推动力所在。
参考文献:
[1]周涛,柏文洁,汪秉宏,等.复杂网络研究概论[J].物理,2005,34(1):31-36.
[2]BoccalettiS,LatoraV,MorenoY,etal.Complexnetworks:structureanddynamics[J].PhysRep,2006,424:175-308.
[3]NewmanMEJ.Modelsofthesmallworld[J].JStatPhys,2000,101:819-841.
[4]NewmanMEJ.Thestructureandfunctionofcomplexnetworks[J].SIAMReview,2003,45(2):167-256.
[5]BarabasiAL,BonabeauE.Scale2freenetworks[J].ScientificAmerican,2003,5(1):60-69.
[6]解㑇,汪小帆.复杂网络中的社团结构分析算法研究综述[J].复杂系统与复杂性科学,2005,2(2):1-12.
[7]NewmanMEJ.Propertiesofhighlyclusterednetworks[J].PhysRevE,2003,68:026121.
[8]TaoZhou,Bing2HongWang,Pin2QunJiang.Adeterministicsupersmall2worldnetworkofintegers[J].2004,arXiv:cond2mat/
0405258.
[9]WattsDJ,StrogatzSH.Collectivedynamicsofsmallworldnetworks[J].Nature,1998,393:440-442.
[10]StrogatzSH.Exploringcomplexnetworks[J].Nature,2001,410:268-276.
[11]HethcoteHW.Themathematicsofinfectiousdiseases[J].SIAMReview,2000,42:599-653.
[12]JeongH,TomborB,AlbertR,etal.Thelarge2scaleorganizationofmetabolicnetworks[J].407:651-654.
[13]SzaboG,AlavaM,KerteszJ.Structuraltransitionsinscale2freeorks[J056102.
[14]BarabasiAL,AlbertR.EmergenceofscalinginrandomnetwJ1999,.
[15]MichaelT.Gastner,NewmanMEJ.ThespatialwJB,2006,49:247-252.
[16]NewmanMEJ.ScientificI:andfundamentalresults[J].PhysRevE,2001,64:
016131.
[17]GuimeraR,A,etal.Theworld2wideairtransportationnetwork:anomalouscentrality,communitystructure,
andcities’globalJ].PNAS,2005,102(31):7794-7799.
[18]GuimeraR,AmaralLAN.Modelingtheworld2wideairportnetwork[J].EurPhysJB,2004,38:381-385.
[19]LiW,CaiX.StatisticalanalysisofairportnetworkofChina[J].PhysRevE,2004,69:046106.
[20]ChiLi2Ping,WangRu,SuHang,etal.StructuralpropertiesofUSflightnetwork[J].ChinPhysLett,2003,20:1393-1396.
[21]WangRu,CaiXu.Hierarchicalstructure,disassortativityandinformationmeasuresoftheUS[J].ChinPhysLett,2005,22:2715
-2718.
[22]BaglerG.AnalysisoftheairportnetworkofIndiaasacomplexweightednetwork[J].2004,arXiv:cond2mat/0409773.
[23]BarratA,BarthélemyM,Pastor2SatorrasR,etal.Thearchitectureofcomplexweightednetworks[J].PNAS,2004,101:3747-
3752.
[24]BarratA,BarthélemyM,VespignaniA.Modelingtheevolutionofweightednetworks[J].PhysRevE,2004,70:066149.
[25]BarratA,BarthélemyM,VespignaniA.Weightedevolvingnetworks2couplingtopologyandweightsdynamics[J].PhysRevLett,
2004,92:228701.
[26]Wen2XuWang,Bing2HongWang,BoHu,etal.Generaldynamicsoftopologyandtrafficonweightedtechnologicalnetworks[J].
PhysRevLett,2005,94:188702.
[27]方锦清.无标度复杂网络的研究面对的挑战[A].第二届全国复杂网络会议论文[C].武汉,2005.
[28]AlexandrovN.Transportationnetworktopologies[Z].NASA/TM-2004-213259,2004.
[29]KubyM,TierneyS,RobertsT,etal.Acomparisonofgeographicinformationsystems,complexnetworks,andothermodelsfor
analyzingtransportationnetworktopologies[Z].NASA/CR-2005-213522,2005.
[30]LunLi,AldersonD,TanakaR,etal.Towardsatheoryofscale2freegraphs:definition,properties,andimplications[J].2004,
arXiv:cond2mat/0501169.