复杂网络理论及其应用研究概述

复杂网络理论及其应用研究概述

刘　涛,陈　忠,陈晓荣

(上海交通大学安泰管理学院,上海　200030)

Ξ

摘　要:从统计特性、结构模型和网络上的动力学行为三个层次简述复杂网络相关研究,并着重介绍了网络上的传播行为,认为它代表了复杂网络在社会经济系统中的重要应用。关键词:复杂网络;小世界;无标度网络;疾病传播中图分类号:O173　　　文献标识码:A

1　引言

结构决定功能是系统科学的基本观点[1]。如果我们将系统内部的各个元素作为节点,元素之间的关系视为连接,那么系统就构成了一个网络,例如神经系统可以看作大量神经细胞通过神经纤维相互连接形成的网络、计算机网络可以看作是计算机通过通信介质如光缆、双绞线、同轴电缆等相互连接形成的网络,类似的还有电力网络、社

[2,3]

会关系网络、交通网络等等。强调系统的结构并从结构角度分析系统的功能正是复杂网络的研究思路,所不同的是这些抽象出来的真实网络的拓扑结构性质不同于以前研究的网络,且节点众多,故称其为复杂网络(complexnetworks)。近年来,大量关于复杂网络的文章在Science、

Nature、PRL、PNAS等国际一流的刊物上发表,从一个侧

处在于首先从统计角度考察网络中大规模节点及其连接

之间的性质,这些性质的不同意味着不同的网络内部结构,而网络内部结构的不同导致系统功能有所差异。所以,对这些统计性质的描述和理解是我们进行复杂网络相关研究的第一步,下面简述之。

2.1　平均路径长度(Theaveragepathlength)

网络研究中,一般定义两节点间的距离为连接两者的最短路径的边的数目;网络的直径为任意两点间的最大距离;网络的平均路径长度l则是所有节点对之间距离的平均值,它描述了网络中节点间的分离程度,即网络有多小。复杂网络研究中一个重要的发现是绝大多数大规模真实网络的平均路径长度比想象的小得多,称之为“小世界效

[2]应”。这一提法来源于著名的Milgram“小世界”试验[4],试验要求参与者把一封信传给他们熟悉的人之一,使这封信最终传到指定的人,籍此来探明熟人网络中路径长度的分布,结果表明平均传过人数仅为六,这一试验也正是流行的“六度分离”概念的起源[5]。

面反映了复杂网络已经成为国际学术界一个新兴的研究

热点。

复杂网络的研究可以简单概括为三方面密切相关却又依次深入的内容:通过实证方法度量网络的统计性质;构建相应的网络模型来理解这些统计性质何以如此;在已知网络结构特征及其形成规则的基础上,预测网络系统的行为[3]。

2.2　聚集系数(Theclusteringcoefficient)

聚集系数C用来描述网络中节点的聚集情况,即网络有多紧密,比如在社会网络中,你朋友的朋友可能也是你的朋友或者你的两个朋友可能彼此也是朋友。其计算方法为:假设节点i通过ki条边与其它ki个节点相连接,如果这ki个节点都相互连接,它们之间应该存在ki(ki-1)󰃗2条边,而这ki个节点之间实际存在的边数只有Ei的话,则它与ki(ki-1)󰃗2之比就是节点i的聚集系数。网络

2　复杂网络的统计性质

用网络的观点描述客观世界起源于1736年德国数学

家Eular解决哥尼斯堡七桥问题。复杂网络研究的不同之

Ξ收稿日期:2005203225

基金项目:国家自然科学基金资助项目(70401019);高等学校博士点科研基金资助项目(2002048020)

作者简介:刘涛(19782),男,湖北襄樊人,上海交通大学安泰管理学院博士研究生,研究方向:复杂网络,金融复杂性;陈忠(19432),男,上海交通大学安泰管理学院教授,博士生导师,研究方向:复杂性理论,智能管理;陈晓荣(19722),女,上海交通大学安泰管理学院讲师,博士,研究方向:复杂网络。

2系　统　工　程　　　　　　　　　　　　　　　　　　2005年

网络结构之间的差异[8],它包括两个方面——不同度数节点之间的相关性和节点度分布与其聚集系数之间的相关性。前者指的是网络中与高度数(或低度数)节点相连接的节点的度数偏向于高还是低;后者指的是高度数节点的聚集系数偏向于高还是低。实证表明,在社会网络(演员合作网络、公司董事网络、电子邮箱网络)中节点具有正的度的相关性,而节点度分布与其聚集系数之间却具有负的相关性;其它类型的网络(信息网络、技术网络、生物网络)则相反[9]。正因为如此,这两种相关性被认为是社会网络区别于其他类型网络的重要特征,在社会网络研究中引起了高度重视[10]。的聚集系数就是整个网络中所有节点的聚集系数的平均。显然,只有在全连通网络(每个节点都与其余所有的节点相连接)中,聚集系数才能等于1,一般均小于1。在完全随

-1

机网络中,C:N,然而实证结果却表明大部分大规模真实网络中的节点倾向于聚集在一起,尽管聚集系数C远远小于1,但都远比N-1大[2]。

2.3　度分布(Thedegreedistribution)

图论中节点i的度ki为节点i连接的边的总数目,所有节点i的度ki的平均值称为网络的平均度,定义为。网络中节点的度分布用分布函数p(k)来表示,其含义为一个任意选择的节点恰好有k条边的概率,也等于网络中度数为k的结点的个数占网络结点总个数的比值。

2.4　其它性质

上述三种统计特性是复杂网络研究的基础,随着研究的深入,人们逐渐发现真实网络还具有一些其它重要的统计性质,例如:

(1)网络弹性(NetworkResilience)网络的功能依赖其节点的连通性,我们称网络节点的删除对网络连通性的影响为网络弹性,其分析有两种方式——随机删除和有选择的删除,前者称为网络的鲁棒性分析,后者称为网络的脆弱性分析。Albert等人分别对度分布服从指数分布的随机网络模型和度分布服从幂律分布的BA网络模型进行了研究[6],结果显示:随机删除节点基本上不影响BA网络的平均路径长度,相反,有选择的删除节点后,BA网络的平均路径长度较随机网络的增长快得多。这表明,BA模型相对随机网络具有较强的鲁棒性和易受攻击性。出现上述现象的原因在于幂律分布网络中存在的少数具有很大度数的节点在网络连通中扮演着关键角色,一般也称它们为Hub节点。

(2)介数(betweeness)介数分为边介数和节点介数[7]。节点的介数为网络中所有的最短路径中经过该节点的数量比例;边的介数含义类似。介数反映了相应的节点或者边在整个网络中的作用和影响力,具有很强的现实意义。例如,在社会关系网络或技术网络中,介数的分布特征反映了不同人员、资源和技术在相应生产关系中的地位,这对于在网络中发现和保护关键资源和技术具有重要意义。

(3)度和聚集系数之间的相关性

网络中度和聚集系数之间的相关性被用来描述不同

3　复杂网络模型最简单的网络模型为规则网络,其特点是每个节点的近邻数目都相同,如一维链、二维晶格、完全图等。20

¨

世纪50年代末PaulErdos和AlfredRényi提出了一种完

[11]

全随机的网络模型,它由N个节点构成的图中以概率p随机连接任意两个节点而成,其平均度=p(N-1)≈pN;平均路径长度l:lnN󰃗ln();聚集系数C=p;当N很大时,节点度分布近似为泊松分布:P(k)≈

e

-

k󰃗k!.随机网络模型的提出是网络研究中的重

大成果,但它仍不能很好的刻画实际网络的性质,人们又相继提出了一些新的网络模型。

3.1　小世界网络(Small2worldnetworks)

实证结果表明,大多数的真实网络具有小世界性(较小的最短路径)和聚集性(相对较大的聚集系数)[2],见表1所示。然而,规则网络虽具有聚集性,平均最短路径却较大;随机图则正好相反,具有小世界性,但聚集系数却相当小。

可见规则网络和随机网络并不能很好展现真实网络的性质,这说明现实世界既不是完全确定的也不是完全随机的。Watts和Strogatz在1998年提出了一个兼具小世界性和高聚集性的网络模型[12],它是复杂网络研究中的重大突破!他们通过将规则网络中的每条边以概率p随机连接到网络中的一个新节点上,构造出一种介于规则网络和随机网络之间的网络(简称WS网络),它同时具有较小的平均路径长度和较大的聚集系数,而规则网络和随机网络则分别是WS网络在p为0和1时的特例。模型构造过程如图1所示。

第6期　　　　　　　　　　　刘涛,陈忠等:复杂网络理论及其应用研究概述

表1　实际网络的Small2world现象[2]

NetworkWWW,sitelevelInternet,domainlevel

MovieactorsMEDLINEco2authorshipMath.co2authorshipE.coli,reactiongraphSilwoodParkfoodwebWorkds,synonyms

PowergridC.ElegansSize153,1273015～6209225,2261,520,2517097531515422,3114,941282

35.213.52～4.11

6118.13.928.34.7513.482.6714

l

lrand

C

Crand

3

3.13.7～3.763.654.69.52.623.404.518.72.65

3.356.36～6.18

2.994.918.21.983.233.8412.42.25

0.10780.18～0.30.790.0660.590.590.150.70.080.28

0.000230.0010.000271.1×10-5.4×10-0.090.030.00060.0050.05

5

5

　注:下标rand为随机网络模型下的计算,通过对比实际网络与相应随机网络(相同的节点数和边数)的性质,可以发现真实网络

具有小世界和较高聚集系数的性质。

图1　WS小世界网络模型的构造[12]

　　WS模型提出后,很多学者在此基础作了进一步改

进[13],其中应用最多的是Newman和Watts提出的所谓NW小世界模型[14]。NW模型不同于WS模型之初在于它不切断规则网络中的原始边,而是以概率p重新连接一对节点。NW模型的优点在于其简化了理论分析,因为

事实上,当p很WS模型可能存在孤立节点,但NW不会。

小而N很大的时候,这两个模型理论分析的结果是相同

的,现在我们统称它们为小世界模型。

3.2　无标度网络(Scale2freenetworks)

尽管小世界模型能很好的刻画现实世界的小世界性和高聚集性,但对小世界模型的理论分析表明其节点的度分布仍为指数分布形式[15]。实证结果却表明对于大多数大规模真实网络用幂率分布来描述它们的度分布更加精确[2],即P(k)∶k-Χ,见表2所示。

4系　统　工　程　　　　　　　　　　　　　　　　　　2005年

表2　实际网络的Scale2free现象[2]

NetworkWWW,siteInternet,routerMovieactorsCo2authors,SPIRESCo2authors,math.SexualcontactsMetabolic,E.coliProtein,S.cerev.

CitationPhonecallWords,co2occurrenceSize325,729150,000212,25056,62770,9752,8107781870783,33953×1060,902

7.42.398.573.1670.13

2.7

4.512.6628.78173120

Χout

2.452.42.31.22.53.42.22.4

Χin

2.12.42.31.22.53.42.22.432.12.7

lreallrandlpow

11.2114.5449.5

8.3212.83.652.128.2

4.777.474.011.956.53

3.23.322.

2.1

　注:下标out、in分别表示出度和入度的幂率分布指数,可见很多网络的度分布具有幂率特征。下标real、rand和pow分别表示真

实网络、随机网络模型和Scale2free网络模型中计算的平均路径长度。

　　幂率分布相对于指数分布其图形没有峰值,大多数节点仅有少量连接,而少数节点拥有大量连接,不存在随机网络中的特征标度,于是Barabási等人称这种度分布具有幂率特征的网络为Scale2free网络[16]。为解释Scale2

free网络的形成机制,Barabási和Albert提出了著名的BA模型[17],他们认为以前的网络模型没有考虑真实网络

上都起作用而只会在某个局域世界里被遵守,通过将局域世界的概念引入BA模型对其作了推广,提出了所谓的局域世界演化网络模型[25],其度分布介于指数网络和无标度网络的度分布之间。该模型表明,随着局域世界的扩大,网络演化越不均匀,越接近于BA模型,即:局域世界的规模决定了网络演化的非均匀性。

(2)权重演化网络模型

上述研究均将网络看作无权网,然而现实网络大多为有权网,即网络节点之间的连接强度是有区别的。Yook等人提出了一种权重演化模型[26]:假定节点权重正比于节点的度数,也即度数大的节点拥有更大的权数。结果表明,其度分布也符合幂律特征。

(3)确定性网络模型

上述所有网络模型都引入了某种程度的随机性,那么是否一定要有随机性才能展现出小世界性和无标度特性呢?Barabási等人提出了一种具有层次结构的网络模型[27],它在确定性机制下也能表现出无标度特性,节点度分布为P(k):k-ln2ln3

的两个重要性质——增长性和择优连接性,前者意味着网络中不断有新的节点加入进来,后者则意味着新的节点进来后优先选择网络中度数大的节点进行连接。他们不仅给出了BA模型的生成算法并进行了模拟分析[17],而且还利用统计物理中的平均场方法给出了模型的解析解[18],结果表明:经过充分长时间的演化后,BA网络的度分布不再随时间变化,度分布稳定为指数为3的幂律分布。

BA模型的提出是复杂网络研究中的又一重大突破,

标志着人们对客观网络世界认识的深入。之后,许多学者对这一模型进行了改进,如非线性择优连接[19]、加速增长[20]、重绕边的局域事件[21]、逐渐老化[22]、适应性竞争[23]等等。需要注意的是,绝大多数而不是所有的真实网络都是Scale2free网络,如有的真实网络度分布为指数分布截断形式[24]等等。

。

4　复杂网络的应用

网络结构研究固然重要,但其最终目的是通过研究结构来了解和解释基于这些网络之上的系统运作方式,进而预测和控制网络系统的行为。一般将这种建立在网络上的系统动态性质称为网络上的动力学行为,其涉及面非常之广,如系统的渗流[28]、同步[29]、相变[30]、网络搜索[31]和网络导航[32]等等。上述研究理论性较强,有一类应用性很强

3.3　其它网络模型

除了经典的小世界模型、无标度网络模型之外,学者们也提出了一些其它的网络模型来描述真实世界的网络结构。

(1)局域世界演化模型

李翔和陈关荣认为择优连接机制不可能在整个网络

第6期　　　　　　　　　　　刘涛,陈忠等:复杂网络理论及其应用研究概述的网络行为研究已经日益引起人们的兴趣,如计算机病毒在计算机网络上的蔓延、传染病在人群中的流行、谣言在社会中的扩散等等,实际上它们都是一种服从某种规律的网络上的传播行为。传统的网络传播模型大都是基于规则网络的,复杂网络研究的深入使我们重新审视这一问题。下面我们着重介绍这类应用研究。

网络传播行为的研究最初且仍是主要的目的之一是为了了解疾病的传播机制。一般用节点表示疾病传染或感染的个体,如果两个个体之间可以通过某种方式直接发生传染与被传染关系,就认为这两个个体之间存在连接,这样就得到了传播网络的拓扑结构,进而可以建立相关模型来研究这种传播行为。显然,网络传播模型研究的关键是传播规则的制定和网络拓扑结构的选择。

经典的疾病传播模型为SIS模型和SIR模型[33],它们都将网络拓扑结构简单的假定为规则网络或者充分混合均匀网络,区别在于传播规则的不同。在SIS模型中,每个节点处于两种状态——健康易受感染的和已被感染而具有传染性的;在SIR模型中,节点还可以处于另一种“免疫”状态,这种状态下的节点既不会被感染也不会感染其它节点,相当于将它从传播网络中剔除掉。我们以SIS模型为例介绍其研究结果,首先随机选择网络中一个或若

5

干节点为染病节点,其余为健康节点,在每一时间步,染病节点的邻近节点以概率Α变成染病节点,Α称为传染率,同时每个染病节点都依某个事先设定的痊愈率Β变成健康节点,上述演化规则在整个网络中被同时执行。显然,传染率越大,痊愈率越小,疾病就越有可能感染更多的人,一般定义传染率和痊愈率的比值为传染强度Κ.研究表明,经典SIS模型存在一个传染强度阈值Κ≥Κc>0,如果Κc,疾病传染将一直持续下去达到一个稳定的范围,此时称染病节点数占总节点数的比例为疾病传染的波及范围;相反,如果Κ<

。Κc,疾病持续传染一段时间后最终将全部被治愈然而,将疾病接触网络简单抽象为规则均匀连接网络并不符合实际情况。Moore等人研究了小世界网络中的疾病传播行为[34],发现疾病在小世界网络中的传播阈值明显比在规则网络中小,相同的传染强度下,经历相同时间后,疾病在小世界网络中的传染范围明显大于其在规则网络中的传染范围,即:相对于规则网络,疾病在小世界网络中更适宜传染;Paster2Satorras等研究了在无标度网络上的传染行为[35],结果令人震惊:无论是规则网络还是小世界网络,总存在正的传染强度阈值,而无标度网络中疾病传染的阈值却非常接近于零,如图2所示。对SIR模型的分析也可以得到类似的结果[36]。

图2　规则网络、小世界网络、无标度网络的疾病传播波及范围与传染强度关系示意图

　　由于大量的实证研究表明真实世界网络既具有小世

界性又具有无标度特性,上述结论是相当令人沮丧的。所幸的是,生活中无论是疾病还是计算机病毒的传染强度都非常小(Κ=1),危害不至于太大。然而,一旦疾病或病毒的传染强度较大时就必须高度重视其危害,对其的控制措施也不能完全依赖于医疗卫生条件的提高,而只能采取隔离保护某些节点、强行切断相关连接进而中断传染途径的方法来改变传播网络的拓扑结构。事实上,我们也正是采用上述方法成功的战胜了2003年春夏之交席卷全国的SARS灾害。

疾病传播机制的研究并非问题的全部,我们的最终目

的是研究如何有效控制疾病传播。Pastor2Satorras等的研究表明,在资源有限的情况下,优先保护节点度数比较大的节点比随机选择节点进行保护效果要好得多[37]。然而实际应用中,节点的度,即:传染期间与某个体有可能接触的个体数目,往往是很难统计的。比如在对性传播疾病的研究中,研究人员只能通过问卷和口头询问的方式获知患病者或高危人群的情况,但他们回答的可信度很低,有鉴于此,一些学者依据上述思想提出了一些具有实际意义的

[38][39]

免疫策略,如“熟识者免疫”、“接触免疫”、“环状免[40]疫”等等。

网络传播行为的研究不仅在于分析疾病传播现象,而

6系　统　工　程　　　　　　　　　　　　　　　　　　2005年

络上的动力学行为三个逐次深入的层面简述了最近几年在国际学术界引起高度重视的复杂网络领域的相关研究。网络是许多复杂系统的结构形态[44],当前对于复杂网络研究的兴起正是自20世纪80年代中期兴起的复杂性科学研究的一个拓展。正因为如此,复杂网络的研究也已经受到了我国学术界的特别关注[45],分别于2004年4月在无锡、9月在杭州召开了全国范围的研讨班,掀起了复杂网络研究的热潮。总之,面对这一全新而富有前景的领域,我们应该把握机遇,结合相关研究领域将其深入开展下去,为推动我国社会和经济的持续发展作出应有的贡献!

且可以用来分析其它许多事物的传播行为。例如,我们可以将其应用于社会网络上传播行为的研究,基本思路如下:首先从复杂网络理论出发抽象出社会网络的拓扑结构,然后按照一定的传播规则分析其传播机制,最后分析如何通过一定措施影响这种传播。事实上,这类研究工作已经开展起来,如:知识或技术的扩散[41]、网络新产品的

[42][43]

扩散以及银行金融风险的传染等,它们既有联系又有区别,前两者的研究目的是为了促进传播;后者则是为了尽量避免传播。

5　小结

本文从复杂网络的统计特性、结构模型以及发生在网

参考文献:

[1]　许国志等.系统科学[M].上海:上海科技教育出版社,2000.[2]　AlbertR,BarabásiA2L.Statisticalmechanicsofcomplexnetwork[J].ReviewofModernPhysics,2002,74(Jan.):47～97.[3]　NewmanMEJ.Thestructureandfunctionofcomplexnetworks[J].SI～256.AMReview,2003,45:167[4]　～67.MilgramS.Thesmallworldproblem[J].PsychologyTody,1967,2:60[5]　GuareJ.Sixdegreesofseparation:aplay[Z].NewYork:Vintage,1990.

[6]　AlbertR,JeongH,Barabá～siA2L.Attackanderrortoleranceincomplexnerworks[J].Nature,2001,406:387

482.

[7]　GohK2I,OhE,KahngB,Ki.Rev.E,2003,mD.Betweennesscentralitycorrelationinsocialnetworks[J].Phys

67:017101.

[8]　NewmanMEJ.Assortativemixinginnetworks[J].Phys.Rev.Lett.,2002,:208701.

[9]　NewmanMEJ.Whysocialnetworksaredifferentfromothertypesofnetworks[J].Phy.Rev.E,2003,68:

036122.

[10]　JacksonMO,RogersBW.Searchintheformationoflargenetworks:howrandomaresociallygenerated

networks?[R].2004.

¨

[11]　Erdo～297.sP,RényiA.Onrandomgraphs[J].PublicationesMathematicae,1959,6:290

[12]　～442.WattsDJ,StrogatzSH.Collectivedynamicsof″small2world″networks[J].Nature,1998,393(June):440[13]　NewmanMEJ.Modelsofthesmallworld[J].J.Stat.Phys.,2000,101:819～841.

[14]　NewmanMEJ,WattsDJ.Renormalizationgroupanalysisofthesmall2.Lett.worldnetworkmodel[J].Phys

～346.A,1999,263:341

[15]　BarratA,WeightM.Onthepropertiesofsmall2.J.,2000,B13:547～560.worldnetworkmodels[J].Eur.Phys[16]　Barabá～59.siA2L,BonabeauE.Scale2freenetworks[J].ScientificAmerican,2003,(May):50[17]　BarabásiA2L,AlbertR.Emergenceofscalinginrandomnetworks[J].Science,1999,286(Oct.):509～512.[18]　BarabásiA2L,AlbertR,JeongH.Mean2fieldtheoryforscale2freerandomnetworks[J].PhysicaA,1999,272:

173～187.

[19]　KrapivskyPL,RednerS,LeyvrazF.Connectivityofgrowingrandomnetworks[J].Phys.Rev.Lett.,2000,85

(21):4629～4632.

[20]　DorogovtsevSN,MendesJFF.Scalingpropertiesofscale2freeevolvingnetworks:continuousapproach[J].

.Rev.E,2001,63:056125.Phys

[21]　AlbertR,Barabá.Rev.Lett.,siA2L.Topologyofevolvingnetworks:localeventsandniversality[J].Phys

2000,85(24):5234～5237.

[22]　DorogovtsevSN,MendesJFF,SamukhinAN.Structureofgrowingnetworkswithpreferentiallinking[J].

.Rev.Lett.,2000,85(21):4633～4636.Phys

[23]　BianconiG,Barabá.Lett.,2001,54:siA2L.Competitionandmultiscalinginevolvingnetworks[J].Eur.Phys

第6期　　　　　　　　　　　刘涛,陈忠等:复杂网络理论及其应用研究概述7

436～442.

[24]　AmaralLAN,ScalaA,BarthelemyM,StanleyHE.Classesofbehaviorofsmall2worldnetworks[A].Proc.

.Acad.Sci.USA97[C].2000:11149～11152.Natl

[25]　LiX,ChenGR.Alocal2～286.worldevolvingnetworkmodel[J].PhysicaA,2003,328:274[26]　YookSH,JeongH,Barabá.Rev.Lett.,2001,86(25);5835～siA2L.Weightedevolvingnetworks[J].Phys

5838.

[27]　Barabá～5.siA2L,RavaszE,VicsekT.Deterministicscale2freenetworks[J].PhysicaA,2001,299:559[28]　CohenR,Ben2AvrahamD,HavlinS.Percolationcriticalexponentsinscale2freenetworks[J].PhysicalReview

E,2002,66:036113.[29]　WangXF.Complexnetworks:topology,dynamicsandsynchronization[J].Int.J.BifurcationandChaos,

2002,12(5):885～916.

[30]　GoltsevAV,DorogovtsevSN,MendesJFF.Criticalphenomenainnetworks[J].Phys.Rev.E,2003,67:

026123.

[31]　Ki.Rev.E,2002,mBJ,YoonCN,HanSK,JeongH.Pathfindingstrategiesinscale2freenetworks[J].Phys

65:027103.

[32]　KleinbergJM.Navigationinasmallworld[J].Nature,2000,406:845.

[33]　HethcoteHW.Themathematicsofinfectiousdiseases[J].SI～653.AMReview,2000,42:599

[34]　.Rev.,2000,E61:5678MooreC,NewmanMEJ.Epidemicsandpercolationinsmall2worldnetworks[J].Phys

～5682.

[35]　Paster2SatorrasR,VespignaniA.Epidemicspreadinginscale2freenetworks[J].Phys.Rev.Lett.,2001,86:

3200～3203.

[36]　MorenoY,Pastor2SatorrasR,VespignaniA.Epidemicoutbreaksincomplexheterogen2eousnetworks[J].Eur.

.J.,2002,B26:521～529.Phys

[37]　Paster2SatorrasR,VespignaniA.I.Rev.E,2002,65:036104.mmunizationofcomplexnetworks[J].Phys[38]　CohenR,HavlinS,Ben2.Rev.AvrahamD.Efficientimmunizationofpopulationsandcomputers[J].Phys

Lett.,2003,91:247901.

[39]　KretzschmarM,VanDuynhovenYTHP,SeverijnenAJ.Modelingpreventionstrategiesforgonorrheaand

.,1996,114:306～317.chlamydiausingstochasticnetworksimulations[J].Am.J.Epidemiol

¨

[40]　.,2000,41:143～171.MüllerJ,SchonfischB,KirkilionisM.Ringvaccination[J].J.Math.Biol

[41]　CowanR,JonardN.Networkstructureandthediffusionofknowledge[J].JournalofEconomicDynamics&

～1575.Control,2004,28:1557

[42]　段文奇,陈忠,陈晓荣.基于复杂网络的新产品赠样目标优化策略[R].上海:上海交通大学管理学院,2005.

[43]　WangYS.Twopower2lawdistributionmodelingofbankingnetwork[R].Shanghai:ShanghaiJiaotong

University,2005.

[44]　StrogatzSH.Exploringcomplexnetworks[J].Nature,2001,410(March):268～276.[45]　方锦清,汪小帆,刘曾荣.略论复杂性问题和非线性复杂网络系统的研究[J].科技导报,2004,(2):9～12.

ABriefReviewofComplexNetworksandItsApplication

LIUTao,CHENZhong,CHENXiao2rong

(AetnaSchoolofManagement,ShanghaiJiaotongUniversity,Shanghai200030,China)

Abstract:Inthispaperwebrieflyreviewthestudiesaboutcomplexnetworksfromthreelevels,statisticalproperties,structuremodelanddynamicalbehavior.

Inspecially,weintroducethebehaviorofthespreadofinfectionover

.networks,andwethinkitveryimportantinsocialandeconomicsystems

Keywords:ComplexNetworks;Small2world;Scale2freeNetworks;TheSpreadofInfection