（理论物理专业论文）复杂网络输运性质的研究.pdf

薛育华：复杂网络输运性质的研究 摘要 从社会网络到自然和技术网络，网络上的输运都是网络研究的中心问题。例如， 流行病的传播、谣言和交通运输是社会网络上输运问题的典型代表，英特网上信息 包的传递则是技术网络的输运问题。根据网络流在节点是否守恒，我们大致可以把 输运网络分为两类：一类是遵从物质守恒原理的，另一类则不遵从物质守恒原理。 例如，网络上的流行病传播过程中流过节点的流是不守恒的，流行病传播的过程是 一个个节点被感染的过程；相比之下，在交通运输网络中除了源点和汇点其它各个 节点的流都是守恒的。 网络的拓扑结构对于网络输运有着重要的影响。相比传统的随机网络而言，无 标度网络得到了更多的关注，因为不仅无标度网络独特的拓扑结构，而且无标度网 络的拓扑结构更接近实际网络，例如很多社会网络和科技网络都具有无标度的特 性。无标度网络的度分布为p ( k ) 一k ，其中k 是节点的度。无标度网络的度分布 为幂率分布表明该网络中存在度很大的节点，同时网路中绝大多数的节点的度都比 较小。同无标度网络相比，随机网络的节点之间则以同一概率相连接，也就是说节 点的度分布存在一个中心值。网络的拓扑结构决定了网络上的输运行为，例如人们 开始关注网络的拓扑结构对流行病传播的速率和模式的影响；对于网络流，在无标 度网络上的一种反常的输运已经被研究，发现无标度网络比随机网络有着更加高的 输运效率；运用重正化群方法，发现了生物网路上输运的无标度行为。发现交通网 络输运的效率可以通过阻断某条街道来提高。 网路的一种重要的拓扑性质是度相关性。如果网络中度大的节点偏向于连接度 大的节点，度小的节点偏向于连接度小的节点，那么该网络具有正的度关联系数。 如果网络中度大的节点偏向于和度小的节点相连，那么该网络具有负的度关联系 数。我们在很多实际的网络中发现了这种拓扑性质：一般来说，社会网络的度关联 性为正，而技术网络和生物网络的度关联性为负。度关联性这种结构对于网络的输 运起着重要的作用。如对于流行病的传播，已经证明在具有证的度关联系数的网络 三 扬、i 1 人硕_ ：学何论文 没有流行病传播闽值。但是这种网络拓扑结构对于网络流的作用还不清楚。理解和 掌握这一拓扑结构对于网络流的作用，不仅对传统的交通运输和生物网络的研究有 帮助，而且对网络的设计也有一定的指导作用。综上所述我们提出两个问题：度 度关联系数是提高还是降低了网络的输运效率? 能否通过改变度关联系数来提高 网络的输运效率? 在这篇论文中，我们主要研究了无标度网络和随机网络的输运行为和度相关性 之间的关系。我们通过研究发现无标度网络的输运效率可以通过网络的度相关性来 控制，但是这一方法对随机网络却不适用。另外，我们还研究了无标度电导网络的 累计分布函数的幂率尾。我们发现幕率尾的无标度指数和度关联系数之间存在着一 定的关系。运用分支过程的方法，我们做了理论上的解析。我们的结果表明度小的 节点在网络的输运中起了重要的作用。我们认为无标度网络上表现出来的和度关联 系数相关的特殊输运行为，来源于无标度网络度分布的不均匀性。我们的研究提供 了一种新的改变无标度网络输运效率的方法，同时希望我们的研究能为高效率的输 运网络的设计提供帮助。 这篇论文的第一章我对复杂网络这门学科做了简单的介绍。第二章我解释了几 个关于复杂网络的重要的概念，还介绍了一些图论的基本知识。这些知识的了解， 对我们下面章节的理解有着重要的作用。第三章，我们给出了几个复杂网络个基本 模型。第四章是我的科研的主要内容。在这一章的第二节中，我给出了网络流的表 达公式和计算方法；在第三节中，详细讲述了如何构建度一度完全不相关的网络和度 度有相关性的网络；第四、第五节是本章的主要内容，我分别研究了无标度网络和 随机网络的输运特性；在第六节我给出了两个实证系统；最后我在第七节做了总结 和讨论。 关键词 ：输运过程，无标度网络，随机网络，度分布，j 下同类性，负同类型， 度相关性，网络流，效率 薛育华：复杂网络输运性质_ 的研究 3 一 a b s t r a c t u n d e r s t a n d i n gt r a n s p o r tp r o c e s so nn e t w o r k si sac e n t r a lp r o b l e mi nm a n yf i e l d s ， r a n g i n gf r o mt h es o c i a ln e t w o r k st ot h en a t u r a lo rt e c h n i q u en e t w o r k s f o re x a m p l e ， e p i d e m i cs p r e a d i n g ，r u m o r s a n dt r a n s p o r t a t i o na r et y p i c a lp h e n o m e n ao ft r a n s p o r t r e l a t e dt os o c i a ln e t w o r k s ，w h i l ei n f o r m a t i o np a c k e t sd e l i v e r i n go nt h ei n t e r n e ti sf o r t e c h n i c a ln e t w o r k s w ec a ng e n e r a l l yc l a s s i f yt r a n s p o r to nn e t w o r k si n t ot w oc a t e g o r i e s a c c o r d i n gt ow h e t h e rt h en e t w o r kf l o wc o n s e r v a t i o ni s o b s e r v e df o re a c hn o d eo f n e t w o r k s ：t h ec o n t a m i n a t i o np r o c e s sa n dt h en e t w o r kf l o wp r o c e s s f o re x a m p l e ，f o rt h e e p i d e m i cs p r e a d i n go nn e t w o r k s ，t h e r ei sn of l o wc o n s e r v a t i o na n dt h et r a n s p o r tp r o c e s s i st h ec o n t a m i n a t i o no fe a c hn o d e o nt h e 。o t h e rh a n d ，e x c e p tf o rt h es o u r c ea n ds i n k n o d e s ，t h en e t w o r kf l o wf o re a c hn o d ei nt h et r a n s p o r t a t i o nn e t w o r ki sc o n s e r v e d t h en e t w o r kt o p o l o g yh a sap r o f o u n d i m p l i c a t i o no nt h et r a n s p o r tp r o c e s s c o m p a r e dw i t ht h et r a d i t i o n a lr a n d o mn e t w o r k s ，s c a l e f r e en e t w o r k sh a v eb e e ni nt h e c e n t e ro fa t t e n t i o n ，s i n c et h e yn o to n l yh a v et h eu n i q u ep r o p e r t i e so fs t r u c t u r et o p o l o g y b u ta l s op r o v i d eam o r ea c c u r a t em o d e lo fr e a lw o r l dn e t w o r k s ，s u c ha ss o c i a ln e t w o r k s o rn a t u r a lt e c h n i q u en e t w o r k s t h es c a l e f r e en e t w o r k sa r ec h a r a c t e r i z e db yt h e p o w e r - l a wd i s t r i b u t i o no fd e g r e e s ：以后) k 7w h e r eki st h en u m b e ro fl i n k sa t t a c h e dt o t h en o d e t h ep o w e r - l a wd i s t r i b u t i o no fd e g r e e sm e a n st h a ts c a l e - f r e en e t w o r k sa l e d i s t i n g u i s h e db yt h ee x i s t e n c eo fh u b sw h i c hh a v ea nu n u s u a l l yl a r g en u m b e ro f c o n n e c t i o n s ，w h e r e a sm o s to ft h en o d e sh a v ev e r yf e wl i n k s i nc o n t r a s t ，f o rr a n d o m n e t w o r k st h en o d e sa r ec o n n e c t e dt oe a c ho t h e rb yac o n s t a n tp r o b a b i l i t y , w h i c hm e a n s e a c hi n d i v i d u a lw i l lh a v ea l la p p r o x f f n a t e l ya v e r a g en u m b e ro fc o n n e c t i o n s t h e s e t o p o l o g i c a l n e t w o r ks t r u c t u r e sd e t e r m i n et h et r a n s p o r tb e h a v i o r so nn e t w o r k s f o r e x a m p l e ，t h e r eh a sb e e nab u n to fa c t i v i t yt ou n d e r s t a n de f f e c t so ft h en e t w o r kt o p o l o g y o nt h er a t ea n dp a t t e r n so fd i s e a s es p r e a d f o rt h en e t w o r kf l o w s ，a na n o m a l o u st r a n s p o r t 一4 。扬州1 人学硕十! 学位论文 i ns c a l e - f r e en e t w o r k sh a sb e e no b s e r v e d ，a n df o u n dt h a tt r a n s p o r ti ns c a l e - f r e en e t w o r k s i sf o u n dm o r ee f f i c i e n tt h a nt h a t i nr a n d o mn e t w o r k s s c a l i n gt h e o r yo ft r a n s p o r ti n c o m p l e xb i o l o g i c a ln e t w o r k sh a sb e e np r o p o s e dt h r o u g ht h er e n o r m a l i z a t i o na p p r o a c h e f f i c i e n c yi nt r a n s p o r t a t i o nn e t w o r k sc a nb ei m p r o v e db yb l o c k i n go fc e r t a i ns t r e e t s o n eo ft h em o s ti m p o r t a n tt o p o l o g i c a lf e a t u r e si nt h en e t w o r ks t r u c t u r ei st h e t e n d e n c yo fv e r t i c e so fac e r t a i nd e g r e e st ob ec o n n e c t e dw i t ho t h e rv e r t i c e sw i t hs i m i l a r d e g r e e ( a s s o r t a t i v i t y ) o rd i s s i m i l a rd e g r e e ( d i s s o r t a t i v i t y ) m a n yr e a ln e t w o r k se x h i b i tt h i s d e g r e ec o r r e l a t i o n sa m o n gt h e i r n o d e s i n g e n e r a l ，s o c i a ln e t w o r k sa p p e a rt ob e a s s o r t a t i v ew h i l et e c h n i c a lo rn a t u r a lb i o l o g yn e t w o r k sd i s p l a yt h ed i s s o r t a t i v eb e h a v i o r s u c hc o r r e l a t i o n sp l a ya l li m p o r t a n tr o l ei nt h et r a n s p o r tp r o c e s so nt h en e t w o r k s f o rt h e e p i d e m i cs p r e a d i n g ，l a c ko fa ne p i d e m i ct h r e s h o l dh a sb e e nv e r i f i e di na s s o r t a t i v e n e t w o r k s h o w e v e r , i n 弧en e t w o r kf l o wp r o c e s s ，t h er o l eo fs u c ht o p o l o g i c a lv e r t e x c o r r e l a t i o ni sn o tc l e a r u n d e r s t a n d i n go ft h en e t w o r kf l o wi nt h ed e g r e ec o r r e l a t e d n e t w o r k si si m p o r t a n tn o to n l yt ot h et r a d i t i o n a lt r a n s p o r t a t i o nn e t w o r k sa n dt h e b i o l o g i c a ln e t w o r k s ，b u ta l s ot ot h ed e s i g n m e n to ft h en e t w o r k - b a s e dn e wm a t e r i a l s t h u s ，t h ei n t e r e s t i n gq u e s t i o n sa r e t h ed e g r e e d e g r e ec o r r e l a t i o n si m p r o v 6 o rd e t e r i o r a t e t h en e t w o r kt r a n s p o r te f f i c i e n c y 7 c a nt h en e t w o r kt r a n s p o r te f f i c i e n c yb eo p t i m i z e db y t u n i n gt h ed e g r e ec o r r e l a t i o np r o p e r t i e s ? i nt h i st h e s i s ，w es t u d yt h er e l a t i o nb e t w e e nt h en e t w o r kt r a n s p o r tb e h a v i o r sa n dt h e d e g r e e d e g r e ec o r r e l a t i o n s o ns c a l e f r e en e t w o r k sa n do nr a n d o mn e t w o r k s v e r y i n t e r e s t i n g ，w ef i n dt h a tt h en e t w o r kt r a n s p o r te f f i c i e n c yo ns c a l e f r e en e t w o r k sc a nb e s i g n i f i c a n t l yc o n t r o l l e dt h r o u g ht u n i n gt h ed e g r e ec o r r e l a t i o n i nc o n t r a s t ，w ef i n dt h a t t h et r a n s p o r te f f i c i e n c yf o rr a n d o mn e t w o r k si sa l m o s ti r r e l e v a n tt ot h ed e g r e e c o r r e l a t i o n p r o p e r t i e s i na d d i t i o n ，w eh a v eo b s e r v e dap o w e r - l a wt a i lf o rt h ec u m u l a t i v ed i s t r i b u t i o n o fc o n d u c t a n c eo ns c a l e f r e en e t w o r k s a n dw ef i n dt h a tt h es c a l i n ge x p o n e n t so ft h e p o w e r - l a wt a i la r er e l a t e dt ot h ed e g r e e d e g r e ec o r r e l a t i o np r o p e r t i e sf o rt h es c a l e - f r e e n e t w o r k s w i t ha na p p r o a c ho fb r a n c h i n gp r o c e s s ，n e t w o r kc o n d u c t a n c ei sa n a l y t i c a l l y 薛育华：复杂网络输运性质的研究 5 d e r i v e di nt e r m so ft h et r a n s p o r tb a c k b o n et h e o r y o u rr e s u l t sr e v e a lt h a tn o d e sw i t h s m a l ld e g r e e sp l a yad o m i n a n tr o l ei nt h ep e r f o r m a n c eo fw h o l en e t w o r kt r a n s p o r t w e e l u c i d a t et h a tt h e s eu n i q u et r a n s p o r tb e h a v i o r so ns c a l e f r e en e t w o r k sw i t hr e g a r dt ot h e d e g r e e - d e g r e e c o r r e l a t i o n p r o p e r t y r e s u l tf r o mt h e h e t e r o g e n e i t y o ft h e d e g r e e d i s t r i b u t i o no ns c a l e f r e en e t w o r k s w eb e l i e v et h a to u rr e s u l t sp r o v i d ean e w a p p r o a c ht o c o n t r o lt h e t r a n s p o r te f f i c i e n c y f o rs c a l e - f r e en e t w o r k sa n d e x p e c t t h a to u r u n d e r s t a n d i n g sc a nc o n t r i b u t e t ot h ed e s i g n m e n to ft h eh i g hp e r f o r m a n c et r a n s p o r t n e t w o r k s t h i st h e s i sp r o c e e d sa sf o l l o w s if i r s tg i v eag e n e r a li n t r o d u c t i o nt oc o m p l e x n e t w o r k si nt h ec h a p t e ri i nc h a p t e ri i ，ii n t r o d u c es o m eb a s i ca n di m p o r t a n td e f i n i t i o n s o fn e t w o r ka n dg r a p h ，w h i c ha r ep r e r e q u i s i t e sf o ru n d e r s t a n d i n gl a t e rc h a p t e r s i nc h a p t e r i i i ，s o m eb a s i cm o d u l e so fc o m p l e xn e t w o r k si sp r e s e n t e d i nt h e l a s tc h a p t e r , c h a p t e ri v , ip r e s e n tm yc o n t r i b u t i o n so nt r a n s p o r tp r o c e s so fc o m p l e x n e t w o r k s i nt h i sc h a p t e r , if i r s tr e v i e wt h ef o r m u l a t i o n so fn e t w o r k sf l o w sa n dt h e n p r e s e n tt h em e t h o du s e dd u r i n go u rc a l c u l a t i o ni ns e c t i o ni i s e c o n d l y , i ns e c t i o ni i it h e d e t a i l s - f o rc o n s t r u c t i n gt l l f d e g r e e d e g r e ec o r r e l a t e d u n c o r r e l a t e dn e t w o r k sa r eg i v e n t h i r d l y , t r a n s p o r to nb o t hs c a l e f r e en e t w o r k sa n dr a n d o mn e t w o r k si ss i m u l a t e da n d f u r t h e ra n a l y t i c a u yd e r i v e du s i n gt h eb r a n c h i n gp r o c e s si nt h ef r a m e w o r ko ft r a n s p o r t b a c k b o n et h e o r yi ns e c t i o ni va n dvac o m p a r i s o nw i t ht w oe m p i r i c a ln e t w o r k si s f u r t h e rm a d ei ns e c t i o nv i f i n a l l y , i ns e c t i o nv i i ，ip r e s e n to u rc o n c l u s i o n sa n d u n d e r s t a n d i n g s 【k e y w o r d s l ：t r a n s p o r tp r o c e s s ， s c a l e f r e en e t w o r k s ，r a n d o mn e t w o r k s ，d e g r e e d i s t r i b u t i o n ，a s s o r t a t i v i t y , d i s a s s o r t a t i v i t y , d e g r e ec o r r e l a t i o n ，n e t w o r k f l o w , e f f i c i e n c y 5 4 _ 一 扬州人学颂十学位论文 扬州大学学位论文原创性声明和版权使用授权书 学位论文原创性声明 本人声明：所呈交的学位论文是在导师指导下独立进行研究工作所取得的研究 成果。除文中已经标明引用的内容外，本论文不包含其它个人或集体已经发表的研 究成果。对本文的研究做出贡献的个人和集体，均已在文中以明确方式标明。本声 明的法律结果由本人承担。 学位论文作者签名： 签字同期：年月 同 学位论文版权使用授权书 本人完全了解学校有关保留、使用学位论文的规定，即：学校有权保留并阳国 家有关部门或机构送交学位论文的复印件和电子文档，允许论文被查阅和借阅。本 人授权扬州大学可以将学位论文的全部或部分内容编入有关数据库进行检索，可以 采用影印、缩印或扫描等复制手段保存、汇编学位论文。同时授权中国科学技术信 息研究所将本学位论文收录到中国学位论文全文数据库，并通过网络向社会公 众提供信息服务。 学位论文作者签名：导师签名： 签字日期：年 月日签字同期：年月同 ( 本页为学位论文末页。如论文为密件可不授权，但论文原创必须声明。) 6 一 扬州人学硕 ：学位论文 第一章引言 在我们生活的自然界和人类社会中很多复杂系统可以用网络来描述。系统中的 个体我们用节点表示，个体和个体之间的相互作用关系我们用边来表示。例如在好 莱坞的演员合作网络中，网络的节点就是演员，如果两个演员参演过同一部电影 我们认为他们之问有相互作用，就可以在他们之l 、日j 连一条边。我们知道物理需要j j 数学来描述，对于各种各样的网络我们可以用数学中的图论来描述。用图论描述复 杂网络的时候我们只考虑了节点和边之j 、日j 的相互关系，没有具体的考虑节点和边的 位置，边的长短，边的具体形态等等。所以说我们把网络的这种不依赖节点的位置 和迈的具体形态而表现出来的性质叫做拓扑性质。第一个用图来解决实际问题的人 是欧拉( l e o n h a r d e u l a r ) 。在小镇哥尼斯堡( k 6 n i g s b e r g ) 被河流分成了四个区域，小镇 建有七座桥连接这四个区域。那么能否走遍这四个区域，并且每座桥都只走一次 昵? 这个就是著名的七桥问题。为了研究这一问题欧拉把四个区简化成四个几点， 七座桥认为是七条边，通过这种简化欧拉成功的证明了这个问题。欧拉的这种数学 抽象开创了一个数学分支图论。然而在这之后人们对网络的描述仅仅局限于用 一些规则图形来描述网络。2 0 世纪五十年代e r d r s 和r r n y i 为图论的发展做出了突 破性的工作。他们把随机理论运用到图论中去，创建了e r 随机网络模型【2 】。在e r 随 机网络模型中，每个节点以一定的概率连边。在之后的大约四十年的时间内，大家 一直用随机图来描述网络。 上世纪九十年代，由于算机运算速度的提高和互联网路的发展网络的研究有了 突破性的进展。上世纪6 0 年代人们仅仅运用图论的中的度分布、集群系数、 网络半径等概念来研究网络，而且网络的规模不大，基本上是在大脑的记忆范围之 内。e r d r s 和r r n y i 构建的随机网络模型度分布为泊松分布( p o i s s o nd e g r e e d i s t r i b u t i o n ) 并且集群系数很小，但是人们研究发现很多实际的网络集群系数很大， 并且网络半径很小。显然随机网络模型不能解释这种现象。1 9 9 8 美国c o m e l l 大学 理论和应用力学系的博士生w a r s 及其导师s t r o g a t z 教授基于上述两点构建了一个 薛育华：复杂网络输运性质的研究 三 小世界网络模型【3 圳。w a t t s 和s t r o g a t z ( w s ) 的模型吻合了实际网络的较大群系数和 较小的网络半径，但是w s 模型的度分布还是泊松分布。n o t r ed a m e 大学物理系的 b a r a b d s i 教授通过研究n o t r ed a m e 大学的局域网络( n d e d u ) 发现该网络度分命为幂 率分布，这种分布和e r 随机网络和w s 小世界网络的泊松分布完全不同。幂率分 稚表明网络中个别节点有很大的度，但是绝大多数节点的度较小。1 9 9 9 年b a r a b f i s i 教授及其博士生a l b e r t 构建了一个模型( b a m o d u l e ) 来解释这种幂率分布。该模型的 主要思想是增长( g r o w i n g ) 和优选( p r e f e r e n t i a la t t a c h m e n t ) ，他们的这一研究成果后来 在s c i e n c e 杂志上发表【5 】。随后研究发现人类社会和自然界很多网络的度分布为幂率 分，例如因特网和万维网【6 1 、电子邮件网络( e m a i ln e t w o r k ) f 7 1 、科研合作网 ( c o l l a b o r a t i o nn e t w o r k ) 8 - 1 0 】、蛋白质网络( p r o t e i nn e t w o r k ) 【l i 】、新陈代谢网络 ( m e t a b o l i cn e t w o r k ) f 1 2 】等。 上述两篇创造性的文章开创了复杂网络的研究。在过去的十几年中，作为近代 物理的一个新分支，复杂网络的研究变得越来越热烈。复杂网络的研究范围已经渗 透到各个领域，包括系统工程、生物、金融、经济管理、社会科学等领域。可以说 复杂网络的存在为人们研究自然和社会提供一种新的视角和方法。小到蛋白质网 ( 蛋白分子为节点，蛋白分子和蛋白分子之间的相互作用力为边。) ，大到世界航空 网( 飞机场为顶点，航线为边) ，都可以用复杂网络的方法去研究，可见复杂网络 的发展和研究为其它自然科学和社会科学的发展和深化提供了一种工具和思想。 目前，复杂网络研究的内容主要包括：网络的形成机制，网络演化的统计规律， 网络拓扑特性与模型，网络的演化动力学机制，复杂网络上的传播行为、相继故障、 搜索算法和社团结构，以及复杂网络的同步与控制等问题。对复杂网络的进一步了 解可以参考文献 1 3 1 9 1 。 8 一 扬州人学硕 ：尝俺论文 参考文献： 【1 】l a n a m a r a l ，a s c a l a ，m b a r t h _ e l e m y , a n dh e s t a n l e y ，p r o c e e d i n g so ft h e n a t i o n a la c a d e m yo fs c i e n c e su s a 9 7 ( 2 0 0 0 ) ，1114 9 2 】e r d 6 sp r 6 n y ia o nt h ee v o l u t i o no fr a n d o mg r a p h s p u b l m a t h i n s t h u n g a c a d s c i ，1 9 6 0 ，5 ：1 7 - 6 0 【3 】d j w a t t sa n ds h s t r o g a t z ，c o l l e c t i v ed y n a m i c so fs m a l lw o r l dn e t w o r k s ，n a t u r e 3 9 3 ( 19 9 8 ) ，4 4 0 【4 d j w a t t s ，s m a l lw o r l d ，p r i n c e t o nu n i v e r s i t yp r e s s ，p r i n c e t o n ，19 9 9 5 b a r a b a s ial ，a l b e r tr e m e r g e n c eo fs c a l i n gi nr a n d o mn e t w o r k s s c i e n c e ，19 9 9 ， 2 8 6 ( 5 4 3 9 ) ：5 0 9 - 5 1 2 【6 】r a l b e r t ，h j e o n g ，a n da - l b a r f i b f i s i ，i n t e r n e t ：d i a m e t e ro f t h ew o r l d w i d ew e b ， n a t u r e ( l o n d o n ) 4 0 1 ，13 0 ( 19 9 9 ) 【7 】h e b e l ，l - i m i e l s c h ，a n ds b o r n h o l d t ，s c a l e f r e et o p o l o g yo fe - m a i ln e t w o r k s ， p h y s r e v e6 6 ，0 3 5 10 3 ( 2 0 0 2 ) 【8 】m e j n e w m a n ，s c i e n t i f cc o l l a b o r a t i o nn e t w o r k s i n e t w o r k - c o n s t r u c t i o na n d f u n d a m e n t a lr e s u l t s ，p h y s r e v e6 4 ，0 1 6 1 3 1 ( 2 0 0 1 ) 【9 】m e j n e w m a n ，s c i e n t i f cc o l l a b o r a t i o nn e t w o r k s i i s h o r t e s tp a t h s ，w e i g h t e d n e t w o r k s ，a n dc e n t r a l i t y ，a h y s r e x , e6 4 ，0 1 6 1 3 2 ( 2 0 0 1 ) 【10 m e j n e w m a n ，t h es t r u c t u r eo fs c i e n t i f cc o l l a b o r a t i o nn e t w o r k s ，p r o c n a t l a c a d s c i 9 8 ，4 0 4 ( 2 0 01 ) 【11 】h j e o n g ，s p m a s o n , a l b a r a b 矗s i ，a n dz n o l t v a i ，l e t h a l i t ya n dc e n t r a l i t yi n p r o t e i nn e t w o r k s ，n a t u r e ( l o n d o n ) 4 11 ，41 ( 2 0 0 1 ) 12 h j e o n g ，b t o m b o r ，r a l b e r t ，z n o l t v a i ，a n da - l b a r a b 矗s i ，t h el a r g e - s c a l e o r g a n i z a t i o no fm e t a b o l i cn e t w o r k s ，n a t u r e ( l o n d o n ) 4 0 7 ，6 51 ( 2 0 0 0 ) 13 】l d aec o s t a ，ea r o d r i g u e s ，gt r a v i e s oa n dpr v i l l s ab o a s ，a d v a n c e si n p h y s i c s ，5 6 ( 1 ) ( 2 0 0 7 ) 16 7 薛育华：复杂网络输返性质的研究 竺 【1 4 】s b o c c a l e t t i a ，v l a t o r a ，y m o r e n o ，m c h a v e z ，d 一u h w a n g ，p h y s i c s r e p o r t s4 2 4 ( 2 0 0 6 ) 17 5 3 0 8 【15 】r a l b e r ta n da 一l b a r a b a s i ，r e v m o d p h y s ，7 4 ( 2 0 0 2 ) 4 7 【l6 】n e w m a n ，m e j t h e s t r u c t u r ea n df u n c t i o no fc o m p l e xn e t w o r k s s i a m r e v i e w4 5 ，16 7 - 2 2 5 ( 2 0 0 3 ) 【17 b a r a b 缸ial l i n k e d ：t h en e ws c i e n c eo fn e t w o r k s m a s s a c h u s e t t s ：p e r s u s p u b l i s h i n g ，2 0 0 2 【1 8 】何大韧，刘宗华，汪秉宏，复杂系统与复杂网，高等教育出版社。 【1 9 】汪小帆、李翔、陈关荣，复杂网络理论及其应用，清华大学出版社，北京， 2 0 0 6 。 1 0 _ 一 扬州人学硕十。学何论文 第二章复杂网络的统计描述 2 1 图 2 1 1 图的简介【l 】 从数学的观点看，我们可以用图来描述网络。图是由点集v 和边集e 构成。 我们用g 表示图，g = ( e ；矿) 。v 中的元素叫做顶点；e 中的元素叫做边，与v 中 的两个定点对应。我们用lel 表示边数，i 矿l 表示定点数。如果图中的任意一条边 的两个顶点i 和j 构成的边( ，) 和u ，f ) 表示不同的边则我们称这样的图为有向图，否 则为无向图。如果给每条边赋予一个权重，那么该网络称之为加权图，否则为无权 图。我们可以把无权图看成是每条边的权重为1 的等权网络。在图中没有重边和自 环的图称为简单图。图2 1 表示的是一个有向图，箭头的方向表示的是边的方向。 图2 2 表示的是一个无向图，边没有方向；在图中我们用线条的粗细来表示边的权 重，线条越粗表示边的权重越大，见图2 2 。 7 6 5 7 6 5 图2 1 有向图图2 2 无向图，加权图 2 1 2 图的基本概念【1 】 认识了图我们介绍一下图论中的几个重要概念，道路、最短道路、圈、连通、 度等。图g 中一个节点与边的交替序列为：w = yoe l1 ，le2 y 。一le 。y 。， ( 1 f ，z 时边q 的端点是屹1 ，1 ，) 这条序列称为g 中的一条路径”，若路径w 薛育华：复杂网络输运性质的研究 的边e 1 、e 2 、e n - i 、e 一均不同，称w 为g 中的一条“道路”。和y 。之间最短 的道路称为“最短道路”。一条闭道路称为“罔”。如果图g 中任意两顶点之间都至少 存在一条道路，则我们称图g 连通。若节点1 ，y ( g ) ，则g 中与1 ，顶点联结的边数 称为v 在图g 中的度，记为d e g ( v ) 或尼( v ) 。不难理解，尼( ，) = 2el ，其中l e j v g 为图g 中的边数。 2 1 3 图的存储【1 】 随着计算机速度的加快，存储容量的增大，对大型的矩阵进行计算成为了可 能，所以用矩阵来描述网络，对网络进行模