（凝聚态物理专业论文）复杂网络的演化模型及应用.pdf

摘要 摘要 近年来，网络概念的提出及其研究己经成为揭示自然界及其人类社会 中各种复杂性系统的结构及功能的重要手段。网络的涉及面很广，例如， 互联网、w e b 网页、科学引文、人类性关系、细胞系统以及我们f 常用 于交流的语言系统等都是目前十分引入注目的网络结构例子。尽管组成 恻络的元素非常不同，各种不同网络系统电都有其自身的复杂性，但许 多嗍络系统却存在着某些代表普遍规律的共同性质：小世界特征、高聚 集性以及确定的连接度分布等。此外，在这样的网络中我们称之为节点 或元素的个体成员与这些成员间的相互作用常常会导致大规模的集体行 为，这些行为不能简单地从单个或几个节点的情况预测到，这样的集体 效应称为“涌现”行为。因而，要更好地揭示和理解复杂性网络的基本 性质和功能，我们需要对大量数据进行分析以及对系统中的大量元素进 行统计。当今，电子计算机的飞速发展以及统计物理在交叉学科中的应 用使得我们对包含大量元素和数据的网络系统的研究成为可能。事实上， 近年来许多著名的统计物理学家已经投身于这一领域的研究中并已取得 了重大突破。 论文中我们首先对近年来网络的研究进展做一综述，介绍复杂网络结 构的几个基本性质，即小世界特征、高聚集性以及确定的连接度分布尤 其是自由标度( s c a l e f r e e ) 度分布行为。本论文的主要工作分为三个部 分：第一部分主要对一由z h e n g 和e r g u n 提出的耦合网络模型进行计算 机模拟。结果表明网络问无耦合情况fz h e n g e r g u n 模型网络的度分布遵 从幂律且幂指数与d o r o g o v t e sm e n d e ss a m u k h i n 模型的结果一致：如果 进一步设定网络演化参数a ( 初始吸引子) 、m ( 新节点的连接数) 相等， 模拟结果的幂指数与b a 的理论结果一致即为3 。第二部分在 z h e n g - e r g u n 模型的基础上提出了一种推广网络模型，该模型考虑了藕合 网络中可能存在的三种主要连接方式：老节点之间的再生连接、新节点 与老节点间的直接连接以及两个网络中的交叉连接：基于这种推广模型， 我们建立了连接概率的动力学方程并对方程的解作了严格计算，最后给 出了网络中度分布函数的幂律渐近解并求出相关的幂指数。通过对模型 参数的适当设定，我们的模型可以给出已有相关的结果。最后是复杂网 络在汉字研究方面的实际应用。我们知道汉字是由笔画和字根的相互作 用组成，单个汉字| 1 = l j 的相互作用又形成汉字词组。从这种相互作用意义 华南理工大学硕士学位论文 上讲，语言可以被描述为由被连接的基本元素构成的复杂演化网络。汉 字基本元素相互作用形成单字和词组的方式并不象我们预期的那样随机 进行，而是由该元素的构字能力和构词能力决定。如果两个词组中出现 同一个汉字，就定义为构成词组间的一条连接。经验数据分析证实这样 形成的汉字词组网络具有令人惊讶的高集团系数和小平均路径，体现出 小世界特征且词组问2 度分离。这个结果比文献 6 4 的预测要小。词组连 接数分布与以往的研究产生偏离，它是包含三个不同区域的奇特分布， 这一点与s n d o r o g o v t s e v 和j f f m e n d e s 提出的语言演化网络存在明 显差异。 关键宇：网络演化，耦合网络模型，s c a l ef r e e 网络，s m a l lw o r l d 网络 p r e f e r e n t i a la t t a c h m e n t 优先粘贴 a b s t r a c t i nr e c e n t y e a r s ，n e t w o r k s h a y eb e c o m et h e k e y t ou n c o v c rt h e p a t t e r n s o f i n t e r a c t i o n si nm a n m a d es t r u c t u r e sa n di n c o m p l e xs y s t e m s i nn a t u r e i th a sb e e n d is c o v e r e dt h a t m a n y r e a ln e t w o r k s s y s t e m s ，w h i l es h o w i n gd i f f e r e n t l e v e l so f c o m p l e x i t yo f t h e i ro w n ，p o s s e s sn o v e lc o n l n l o ns t r u t t u r a lo rt o p e l o g i c a lp r o p e r t i e s ： t h es m a l l w o r l de f f e c t ，t h eh i g h - e l u s t e r i n g ，a n daw e l 卜d e f i n e dd e g r e ed i s t r i b u t i o n t h e s en e t w o r k si n c l u d e ，f o r e x a m p l e ，t h ei n t e r n e t ，w o r l d - w i d e - w e b ，s c i e n t i f i c c i t a t i o n s ，t h ew e bo fh u m a ns e x u a lc o n t a c t s ，c e l i s ，a n dl a n g u a g es y s t e m s i na n e t w or kt h ei n d i v i d u a lp a r t s c a l l e d “n o d e s ”o r “c o m p o n e n t s ”a n dt h ei n t e r a c t i o n s b e t w e e nt h e mo f t e nl e a dt ol a r g e - s c a l eb e h a v i o r sw h i c ha r en o te a s i l yt ob epr e d i c t e d f r o mt h ek n o w l e d g eo fo n l yt h eb e h a v i o ro fas i n g l eo raf e wn o d es s u c hc o l l e c t i v e e f f c c t sa r e c a l l e d “e m e r g e n t ”b e h a v i o r s t o u n d e r s t a n dt h e p r o p e r t i e s a n d f u n c t i o n a l i t i e so fn e t w o r k s ，s t u d yb a s e do nl a r g e - s c a l es y s t e m si sr e q u ir e d t h i sh a s b e c o m e f e a s i b l e r e c e n t l y d u et ot h e r a p i dd e v e l o p m e n t s o f c o m p u t e r s a n d i n t or d i s c i p l i n a r yp h y s i c s i nf a c t ，m a n ys t a t i s t i c a lp h y s i c i s t sh a v ed e v o t e di n t ot h i s f i e l da n dag r e a ta c h i e v e m e n th a sb e e nm a d e i nt h i sp a p e r ，w ef i r s tr e v i e wt h er e c e n tf a s tp r o g r e s si nt h es t u d yo fe v o i v i n g n e t w or k s w es u mu ps e v e r a li m p or t a n tf e a t u r e si n c l u d i n gt h es m a l l w o r l de f f e c t ， t h e h i g h c l u s t e r i n g ，a n d a w e l l - d e f i n e d ，e s p e c i a l l y ，t h e s c a l e 、f r e ed i s t r i b u t i o ao f d e g r e e s t h i sm a s t e rt h e s i sh a st h r e ep a r t s i nt h ef i r s tp a r tw es t u d yn u m er i o a l l yt h e m o d e lo fc o u p l e dg r o w i n gn e t w o r k s p r o p o s e db yz h e n ga n de r g u n t h er e s u l t s c o n f i r mt h a tt h i sn e t w o r kh a sap o w er l a wd i s t r i b u t i o no fd e g r e e sa n di tr e d u c e st oa p r e v i o u s n e t w o r km o d e lo fd o r o g o v t e s ，m e n d e s ，a n ds a m u k h i ni n t h e u n c o u p l i n g c a s e i fw es e tu pt h en e t w o r kp a r a m e t e r sa ( t h ei n i t i a la t t r a c t i v c h e s s ) b e i n ge q u a lt o i n f i i n k so fn e wn o d e ) ，t h ee x p o n e n to fd e g r e ed i s t r i b u t i o n so fz h e n g e r g u nm o d e l i sa b e u t3 ，w h i c hi sj u s tt h es a m ea st h ee x a c ts o l u t i o no fb am o d e l i nt h es e c o n d p a r t w e pr e p o s e d a g e n e r a l i z e d m o d e lo f g r o w i n g n e t w or k sb a s e do nt h e z h e n g e r g u nm o d e l w ec o n s i d e rt h r e ed i f f e r e n tw a y so fl i n k se x i s t i n g i n c o u p l e d g r o w i n gn e t w o r k s ，i e r e w i r e dl i n k si nt h eo l dn o d e s ，l i n k sb e t w e e n an e wn o d ea n d a no i dn o d e a n der o s s - l i n k sb e t w e e nt h et w on e t w o r k s ，b a s e do nt h is e x t e n s i v e m o d e lw ef i n d a d y n a m i ce q u a t i o no fp r o b a b i l i t y o fe o n n e c t i o n s t h es o l u t i o no f e q u a t i o n s h o w se x a c t l yt h e a s y m p t o t i cb e h a v i o ro fd e g r e ed i s t r i b u t i o n sf ort h e s e 兰亘堡圭奎兰堡圭竺堡丝苎 l i n k sw h i c h o b e y p o w e r l a wi nt h el i m i tk - m o r e o v e r w eo b t a i n t h e c o r r e s p o n d i n ge x p o n e n t s b yt u n i n gt h ep a r a m e t e r so ft h em o d e ip r o p e r l yw ec a ng e t r e s u l t sc o r r e s p o n d i n gt o p r e p r e s e n c e i nt h e i n s tp a r tw ea p p l yg r o w i n gn e t w o r kt o t h ec h i u e s ee h a r a c t e r sr e s e a r c h a sw ek n o wt h ec h i n e s ec h a r a c t e r sa r ec o n s i s to f s t r o k e ( 笔画) a n de t y m o n ( 字根) ，w h i l ec h i n e s ep h r a s e a r ec o n s i s to fi n t e r a c t i n g c h i n e s ec h ar a c t er s i nt h i s s e n s e ，l a n g u a g ec a l l b ed e s c r i b e da s c o m p l e xg r o w i n g n e t w o r kc o n s t r u c t e db y1 i n k e de l e m e n t s t h ew a yf o rt h e s ee l e m e n t st of o r mc h i n e s e c h a r a c t e ra n dp h r a s eisn o ti ns t o e h a s t i co n ea sw ee x p e c t ，b u ti naw a yd e p e n d i n go n t h e i ra b i l i t yo ff o r m i n gc h ar a c t e ra n dp h r a s e w ed e f i n eal i n kb e t w e e nt w oc h i n e s e p h r a s e sa ss i g n i f i c a t i v ec o o c c u r r e n c e so fa c h a r a c t eri nb o t ho ft h e m a c c o r d i n gt o t h ea n a l y s i so fe m p ir i c a ld a t a ，c h i n e s ep h r a s ew e bf o r m e dt h i sw a yh a v ee m e r g e n t “s m a l lw o r i d ”e f f e c t ，w i t ha m a z i n g l yl a r g ec l u s t e r i n gc o e f f i c l e n ta n ds m a l la v e r a g e s h o r t e s tp a t h ，a n d2 s e g r e g a t i o n s ，w h i c hi s s m a l l e rt h a nt h ep r e d i c t i o no fr e f 6 4 】， a m o n gp h r a s e t h ed e g r e ed is t r i b u t i o n sd e v i a t ef r o mt h er e s u l to fp r e - p r e s e n c e ， “t h es m a l l w o r l do fh u m a nl a n g u a g e ”s t u d i e db ys n d o r o g o v t s e va n dj f f m e n d e s ，a n de x h i b i tt h r e ed i f f e r e n tp e c u l j a rr e g i o n k e y w o r d s ：n e t w o r k e v o l u t i o n ，s c a l e f r e e n e t w o r k s ，s m a l l w o r l dn e t w o r k s p r e f e r e n t i a la t t a e h m e n t 华南理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进 行研究所取得的研究成果。除了文中特别加以标注引用的内容外， 本论文不包含任何其他个人或集体已经发表或撰写的成果作，锅。 对本文的研究做出重要贡献的个人和集体，均已在文中以明确方 式标明。本人完全意识到本声明的法律后果由本人承担。 作者签名：韦洛霞日期：2 0 0 4 年2 月1 0 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规 定，同意学校保留并向国家有关部门或机构送交论文的复印件和 电子版，允许论文被查阅和借阅。本人授权华南理工大学可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采 用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密口，在年解密后适用本授权书。 本学位论文属于 不保密团。 ( 请在以上相应方框内打“”) 作者签名：韦洛霞 导师签名：郏大防 日期：2 0 0 4 年2 月日 日期：2 0 0 4 年2 月日 第1 章绪论 第1 章绪论 1 1 网络研究的进展 进入2 1 世纪以来，随着i n t e m e t 的蓬勃发展，引发人类对以前极少涉及到的自然界 中复杂网络的兴趣，复杂网络是包含i n t e m e t 在内的各种类型相互作用事物的整体，在 自然界中大量存在。每一事物的出现和事物之间的相互联系具有相当的随机性，对于单 个事物我们无法通过它刻画出集体特征，但是对由单个事物构成的整体研究却可以得到 大量令人鼓舞的结果。 人们己经研究过的自然界中存在的复杂网络有互联网，数据通信网【i m ，神经网络、 代谢网络和生态网络【2 2 一，以及包括人类性行为网络、演员合作网络和文献引用网络b i m 在内的社会网络等等。不论是哪一种网络都被看作由节点和边构成，不同网络中作为研 究对象的节点指不同的实体，边反映单个实体间的联系，这种联系对i n t e m e t 是计算机 f 刚的物理连接，对于w o r l d - w i d ew e b 是网页间的超链接；而在神经系统中，我们又把 神经元n e r v ec e l l 看作节点，神经轴突a x o h 看作边，还有细胞网络中细胞为节点，细胞 之间的化学反应成为联系节点的边。 大量研究发现，网络的拓扑结构决定网络所具有的特性b ，1 0 , 1 7 , 2 6 , 3 1 , 3 3 j 3 , 4 8 , 5 j “j “1 0 s ， 这使得研究网络的拓扑结构有着不同寻常的重要意义。图结构的研究最早开始于1 7 3 6 年，e u l e r 用图论的方法解决了七桥问题，但是早期图论的观点和方法与我们今天所研 究的复杂网络图存在根本不同，它并不能解决我们所关心的复杂随机网络问题。在1 9 5 9 ， 1 9 6 0 和1 9 6 1 年，e r d 6 s p a n d r 6 n y i ，a 。发表了三篇有影响的文章【7 ：m ，w ，提出了随机网络 模型( e r 模型) ，并将概率理论应用于研究中，从而建立了一套用概率方法研究随机图 结构的理论。然而e r d s s ，p a n d r 6 n y i ，a 提出e r 模型与现实世界中的真实网络还存在 很大的不同，e r 随机网络模型的度( 边) 分布遵从p o i s s o n 规律，但大量经验研究结 果显示真实网络的度( 边) 分布遵从p o w e b l a w 分布【i ，1 4 _ 1 x “，同时具有较高的集团系 数和较小的最短路径，如w o r l d w i d e w e b ，生态网以及具有6 度分离n 崩的朋友网络和3 度分离的语言网络 6 。6 s 。1 9 9 8 年w a r s ，d ，j ，a n ds h s t r o g a t z 提出了w s 网络模型，第 一次构造出了与实际网络性质相一致的具有高集团系数和较小最短路径网络7 “，我们 称为小世界网络s m a l lw o r l d ，但是这种网络模型的度分布却不服从p o w e r - l a w 。1 9 9 9 年 b a m b f i s ia n d a l b e a 从一种新的更切合实际的观点出发提出了b a 模型，这种模型的构建 基于两个普遍的因素，一是生长( g r o w t h ) ，二是优先粘贴( p r e f e r e n t i a la t t a c h m e n t ) ， 基于这样两个普遍因素演化出一种具有幂律度分布p o w e r - l a w 特征的网络h j ，这种类 型的网络我们称之为s c a l ef r e e 网络( s f ) 。 近年来，复杂网络取得进展的方面主要集中在生物、医学、社会学等领域，研究的 已不再是经典随机网络问题，而是利用概率的方法汲取随机生长网络的各种宏观性质， 从而达到认识真实网络的目的。例如，研究通信网络和代谢网络的健壮性发现，代谢网 华南理工大学硕士学位论文 络中急剧的环境变化和大量的药物使用都不会对一个相当简单的组织生长造成影响，通 信网络局部遭受的攻击和故障也不会导致整个系统灾难h ”3 3 a a , $ 1 8 3 1 。复杂系统的这一稳定 性应归功于这种网络中节点的充分连接，文献 8 1 证明网络的这种容错性只属于s f 网络 所特有的。i n t e m e t 、社会网络、细胞网络等都是s f 网络，其度都具有出人意料的健壮 性。这种研究的意义在于如果我们知道那一种类型的网络更健壮，在设计网络拓扑结构 时就能够进行更好地选择，以提防因局部出现的问题而导致整个系统的崩溃。对于传染 病网络的研究可以知道那一类网络疾病不容易传播，起到对疾病控制的关键作用，这也 是当今复杂网络研究的一个重要动力。 最近两年，n e w m a n 等提出了复杂网络的层次模型m ，利用这种模型可以很好地描 述社会网络的行为，对认识网络的可搜索性、可传递性提供了方法b 2 a ”。 网络复杂性的研究国内属刚起步阶段，与国际上的研究比较明显滞后，从去年起我 国学术界普遍意识到这个问题，随后各方面积极推动下，复杂网络的研究已经开始。 1 2 真实网络研究的经验结果 1 2 1 信息类网络 信息网络包括各种类型的计算机网络、通信网络等是研究现代随机网络的起步点， 网络的主要目标在于节点间信息的传递和信息搜索，认识这种网络的结构对于提高网络 的鲁棒性r o b u s t n e s s 和可搜索性有重要意义。 a i n t e r n e t 我们首先来关注i n t e m e t ，因特网是地理位置不同的计算机网络通过公共的或专用 的通信线路连接起来，在开放的网络协议支持下实现资源共享及其他它网络应用。网络 通常采用的结构有星形网络、环形网络和树形网络，网络构形的不同决定了网络具有不 同的特性，因此网络的结构对系统的安全性、稳定性和可搜索性起到了关键的作用。对 i n t e m e t 结构的研究在不同层次上展开( 域问层次和路由器层次) ，得到两个不同的拓扑 结构h “，无论哪一种结构( 由大量路由器组成的域间层次和路由器层次) 度分布都服 从幂律的特征。这样以来，一个复杂的网络系统问题就可以用一条遵从幂律p ( k ) k 的 简单斜线描述，网络的特性通过一个幂指数y 反映。 从域层次上看，将域作为节点，两个域边界路由器间的一个连接作为一条边，两个 域间通常不止有一个连接存在，但这里只要存在至少一个连接就认为两个域间有一条连 接( 图1 1 ) 。这样的网络1 9 9 7 年1 1 月时有节点3 0 1 5 个，边5 1 5 6 条，最大度5 9 0 ，计 算出平均度k = 3 4 2 ，网络直径d = 9 ，平均路径长度f - 3 7 6 。1 9 9 8 年4 月时有节点3 5 3 0 个，边6 4 3 2 条，最大度7 4 5 ，平均度k = 3 6 5 ，网络直径d = ll ，平均路径长度= 3 7 7 。 1 9 9 8 年1 2 月时有节点4 3 8 9 个，边8 2 5 6 条，最大度9 7 9 ，平均度k = 3 7 6 ，网络直径d = 1 0 ， 平均路径长度f = 3 7 5 。三个不同时间的度分布都遵从幂律p ( 七) 七一，幂指数y 分别为 2 1 5 ，2 1 6 和2 2 吐 第l 章绪论 图1 - 1i n t e r n e t 在a s 级。每个域为一个节点，有四个不同的域。 在路由器层面上( 图1 2 ) 看，节点是路由器，边是路由器对之唰的物理连接。1 9 9 5 年的i n t e m e t 数据研究显示它拥有3 8 8 8 个节点，5 0 1 2 条边，平均度石= 2 5 7 ，度分布同 样遵从幂律p ( k ) 一k ，幂指数y 为2 4 8 t ”。 图1 - 2r o u t e 级的拓扑图。路由器为节点，每个域包含多个路由。 随着时间的推移，i n t e m e t 不断膨胀，网络中节点数急剧增加，今天的网络是什么 样子? 它还遵守j p ( 七) k 。这条规律吗? 文献 2 】绘出了表l - l 的结果自主系统a s 和路由器i r 两种不同层次构造的网络图都有一个特征最短路径且为各自的平均最短路 径，a s 网络具有较高的集团系数，i r 网络c 则较小，a s 具有强相关性的特点在i r 网络中却不存在。连接度分布仍然遵从幂律，在路由器i r 网络构形中幂指数v = 2 2 ， 尾部出现指数截断c u t o t i s ( t h ee x p o n e n t i a lc u t o f f s ) ，在包含大量路由器的a s 网络中 没有这一现象。 表1 1 不同的时间点不同级的i n t e r n e tm a p 的平均性质闭 b w o r l dw m e w e b w w w 环球信息网是为网络用户提供信息服务的最大信息网络，在此网络中聚集了 兰里望三查兰堡主堂垡笙苎 大量的网页和网页问的超链接，当我们把网页作为节点，网页间的超链接作为连接两个 节点的边就得到了一个由网页和超链接构成的逻辑网络( 图1 3 ) 。两个网页间存在一条 边的必要条件是至少有一条超链接，这样形成的网络是一个无向网络；由于超链接是从 图1 - 3w c v v 结构图 一个网页指向另外一个网页，因此也可以将网络看成有方向的，由网页节点和进入网页 节点的超链接构成一个i n - d e g r e e 网络，由网页节点和网页节点发出的超链接构成的 o u t - d e g r e e 网络。对于w w w 的结构有大量的研究【6 2 0 】，这些研究涉及w w w 的各个层 面，但都显示网络的度分布遵从p o w e r - l a w ，p ( 七) 一k 一。1 9 9 9 年w w w 包含3 2 5 7 2 9 个节点1 4 6 9 6 8 0 个边发现，i n - d e g r e e 的分布指数ym = 2 1 ，o u t d e g r e e 的分布指数 - 产2 4 5 ， 有向图的平均最短路径是1 9 ，与系统的节点数有关f f d ，f ) “o 3 5 + 2 0 6 1 9 n ，这就意 味着系统的尺度越大，搜索到一个节点要走过路径越长。 图1 4 通信网络的结构。 4 第1 章绪论 对整个w e b 全局结构的描述是基于】9 9 9 年5 月的网络数据 9 】，2 0 3 1 0 6 个节点， 1 4 6 6 l 矿个边，i n d e g r e e 和o u t d e g r e e 的平均值都是7 2 2 。到了1 9 9 9 年l o 月，w w w 中已经有2 7 1 1 0 6 个节点，2 1 3 0 1 0 6 个边，k 。= k 。= 7 8 5 ，有向网络和无向网络的 平均最短路径分别是f 。= 1 6 和l 。，= 7 。 c 通信网络 通信网络的范围相当广泛，普遍认为网络中相互通信的端点其类型并不一致，端点 间的通信方式也不尽相同，但是有一点共同的是其传输信息的目的，可以将不同类型的 节点组成网络，比如图l - 4 的卫星通信网络、有线电视网络和电话网络。 1 2 2 生物学网络 a 生态网络 自然界大量的生物种群之间存在着相互依赖的生存关系c 2 2 。2 4 ，捌，这种生存关系映可 以看作是种群之间的相互作用、某一种群以另一种群为食的捕食关系上。由生物种群形 成的食物链中，节点是不同的种群，边为两个种群间的捕食关系，图1 - 5 ，猫吃雀和鼠， 猫头鹰吃猫和老鼠。 围1 - 5 捕食链结构。 处于不同地区和不同环境下的生物种群在数量和种类上有着很大的不同，例如海洋 生物和沙漠地带的生物，w i l l i a m s 等对七个不同的食物链进行了研究b 1 发现，尽管他们 有相当大的差别，但是所有物种几乎都只有不超过3 种食物。同样类型的研究由m o n t a y a 和s o l 6 作出m 】，研究对象是有较全的物种也很好定义了的y t h a ne s t u a r y w e b ，s i l w o o d w e b 和t h el i t t l er o c kl a k ew e b 捕食网，发现这些捕食网络不是随机网络而具有小世界特征 1 2 2 】，也就是说具有高的集团系数同时平均最短路径小。相关参数列于表1 2 中。 此外，网络中节点间的相互作用度分布与随机网络的p o i s s o n 分布完全背离，但却 显示极度的倾斜，旦带一个肥尾，能较好地用幂律拟合，前两种网络的幂指数分别为 y = f 1 0 4 ，y = 1 1 0 。 华南理工大学硕士学位论文 表1 - 2 三种不同网络集团系数和平均最短路径【2 3 】 y t h a ne s t u a r yw e bs i l w o o dw e bt h el i t t l er o c kl a k ew e b n 1 3 4 1 5 4 1 8 2 8 7 0 4 7 5 2 6 0 5 c 0 2 2 0 1 50 3 5 2 4 33 4 02 2 2 b 代谢网络 代谢网络关注的目标同样是网络的拓扑构造和它呈现的行为m - 2 8 , 3 1 ) , 3 2 - 3 4 , 4 6 - 4 7 。什么是代谢网 络? 一个很普通的有机体代谢的例子是，在一个基本的化学系统中除了产生氨基酸、糖 和脂质这些基本元素外还有能量，能量用于将这些元素合成蛋白质和细胞结构。这里节 点是培养基( s u b s t r a t e ) ，如果两个培养基出现在同一个化学反应中，就认为它们之 s c a l o - f r e e 荽 量 图i - 6 代谢网络的基本结构和特征8 ”。 间有一个边。f e l la n d w a g n e r 和j e o n ge ta 1 进行了独立的研究得出一致的结果。f e l l a n d w a g n e r 的研究组合成了一系列的化学计算式，以这些方程描述在e c o l i 中能量代谢 s n d , 分子结构单元合成的主要途径 2 5 2 6 1 。在他们的研究中，共获得2 8 2 个节点，边无方 向，得到节点的平均度石= 7 ，从一个节点到另一个节点的平均最短路径e = 2 9 ，代谢网 络具有较高的集团系数，c = o 3 2 ，对比经典随机网络的结果c 。= = 。：“o ，0 2 5 ，远 小于真实代谢网络的参数o 3 2 。 j e o n g 等人认为代谢网是有向的，与文献 2 5 1 的理解有些不同，他们分析了包含4 3 第l 章绪论 种机体的有向代谓 网络m 】，图1 - 6 ，尺寸在2 0 0 到8 0 0 个节点之间，某培养基的i n c o m i n g l i n k s 是指它是代谢反应的产物，而o u t g o i n g 1 i n k s 指它在代谢反应中是离析物：“。研究结果发 现平均最短路径大约是3 ，这个结果与文献 2 5 的一致；平均i n c o m i n g d e g r e e 和 o u t g o i n g d e g r e e 在2 5 到4 0 之间，明显比文献 2 5 1 的7 要小。尽管这个网络很小，但仍 可以看到具有s c a l e f r e e 特征的度分布，幂律指数v = 2 2 。 c 蛋白质网络 基因重组系统可以看作是特大的定向网络，网络中节点是基因重组系统中的不同元 素，定向的边是由重整元素指向重整后的元素，图i 7 。蛋白质之间的相互作用是基因 功能的一个重要方面，了解蛋白质网络是了解基因网络的基础【2 9 , 3 1 , 3 4 , 4 3 - 4 t 4 5 , 12 2 , 1 * 1 。蛋白质网 络以蛋白质为节点，一种蛋白质到另一种蛋白质的相互作用是一条定向的边，在网络的 拓扑结构中会出现像捕食网中的环状单元，蛋白质对间可以出现一对反向边b 】。酵母蛋 白质网络可比拟为i n t e r n e t t z 4 1 ，包含n = 9 8 5 个节点和k = 8 9 9 条边，度分布的波动较大， 大部分节点的度都很少，只有个别节点具有较高的度，以l o g l o g 拟合度分布得到的是 一条直线，斜律为y = 2 5 。 图1 7p 5 3 网络。a ) - - i i , x 比拟为i n t e r n e t t | 1 2 “，b ) 、c ) 呈现s f 网络特性2 1 。 1 2 3 社会学网络 上世纪6 0 年代t r a v e r s 和m i l g r a m 作了一个试验，在b o s t o n ，m a s s a c h u s e t t s ，o m a h a 和n e b r a s k a 随机选出一些人，要他们直接发信给b o s t o n 的某个目标人，每一次转发他 的信给一个熟人，这个人被认为离目标更近。从每个发信人到目标收件人的平均路径是 6 ，这就是著名的6 度分离 1 t 9 l 。自然界中的许多网络具有类似社会网络的结构和性质， n e w m a n 等科学家从各种不同角度、利用各种不同方法对社会网络作了大量研究b - ”m “】， 得到许多有意义的结果。一种典型的社会网络是朋友网络，网络中人是节点，人之间的 各种相互作用关系是边，构成我们常说的社会关系网络。社会网络有许多类型，被关注 最多的是科学家协作网 5 6 - 5 9 , 6 8 ，8 9 , 9 ( 图1 8 ) 、演员协作网m ”, 7 9 1 、人类性关系网 6 2 , 2 1 l 。自从 计算机诞生以来对人类语言的研究变的尤其重要，实际中我们常需要计算机按照我们的 意愿处理语言信息，因此，对语言网络拓扑结构和性质的认识、语言随时闾演化动力学 华南理工大学硕士学位论文 方式的了解有助于语言信息的存储和加工m 6 4 ，6 5 。 p 叩e r 4 图1 - 8 科学家协作网络。科学家为节点，合作共同完成篇论文为一条边。 a 科学协作网 从事科学研究的科学工作者之间合作完成学术论著，形成一个以科学家为网络元素 的科学家协作网和以论著为基本组成的科学文献网络。在科学家协作网中科学家是节 点，如果两个科学家共同完成一篇论文，就在两个人间建立一条相互作用的边吼类似 地在文献网络中，文献为节点。在文献 5 7 1 中分别就两类网络( 以科学家为节点和以论 文为节点) 对来自三个不同数据库m e d l l n e ，s p i r e s 和n c s t r l 的数据进行研究，得 出的结果见表1 3 。它们都具有高聚集性，度分布都遵从p o w e r - l a w 。 表1 ，3 三种不同网络 b 演员协作网 如果两个演员出现在同一部影片中，两个演员节点问就建立一条边。文献 7 0 ，7 1 】 研究的演员协作网中包含2 2 52 2 6 个节点，节点的平均度i = 6 1 ，两个演员间的平均分离 第l 章绪论 即平均最短路径z = 3 6 5 ，集团系数c = o 7 9 比随机网络的结果6 1 2 2 5 2 2 6 ：0 0 0 0 2 7 大很多。 文献 7 9 研究的演员协作网包含节点数n = 2 1 22 5 0 ，得到的平均度是i = 2 8 7 8 ，网络的度 分布服从幂律特征，幂指数v - - 2 3 。 ! 黼蒸m c ) 图1 - 9 英语单词网络“。a ) 由四个简单句j o h n i s t a l l ，j o h n d r i n k s w a t e r ，m a r y i s b l o n d e m a r y d r i n k s w i n e 构成的模型网络。b ) 语言连线的图样，黑点是常用词，白点是非常用词 他们同时出现在一个句子中是一次连接。c ) 度分布。 0 人类性关系网络。 人类社会是有不同性别的男女个体组成的一个网络，性关系网是以不同性别的个体 间的性行为关系作为的网络节点间联系的纽带，也就是边。研究性关系网对于控制性疾 病的传播有着积极的意义。文献 6 2 的研究基于1 9 9 6 年瑞典的一个性行为调查，从4 7 8 1 个年龄在1 8 到7 4 岁之间的瑞典人中采样，获取了2 8 l o 个有效个体，在1 2 个月期间无 论是男性还是女性，性伴侣数目的累计分布按p o w e r - l a w 衰减，幂指数都是y = 2 4 t 6u ： 文献1 2 5 对做了类似的研究。 d 语言网络 人类语言是由许诸多语言元素按照一定的构成规则构造而成的，基本的语言元素非 常有限，用仅有的2 6 个英文字母可以构成所有的英文单词，单词的数目尽管多但也是 华南理工大学硕士学位论文 有限的，用这些有限的单词又可以构造出各种各样的词汇。不同时期会诞生出具有时代 意义的新词汇，词汇的演化是无限的，随着人类语言的进化发展，词汇量不断地丰富， 形成具有复杂性的语言网络，见图1 - 9 。c a n c h o 和s o k 认为，英语的词与词之问以一种非 随机的方式在句子中相互关联，以词为节点，两个词的相互作用表现在他们同时出现在 同一个句子中。这样构造出一个语言的复杂网络，这个快速增氏的网络具有鲁棒性。网 络中两个词之间的平均最短距离定义做的从一个词到另一个词的连接数d ，d 介于2 和3 之间；连接度按p o w e r l a w 分布”】。 文献【6 4 】从英语语言的概念上定义网络，两个单词如果表达同一个意思他们就存在 一个连接，这样形成的网络中有3 0 2 4 4 个单词，度平均是5 9 9 ，集团系数是o 5 3 远大于 随机网络的集团系数，单词间的平均分离为3 1 6 。文献 6 4 1 中 预测任何一种人类语言 词汇间的平均分离都是3 。 1 3 本章小结 近年来整个科学界普遍关注复杂网络包括i n t e m e t 、w w w 、生态网、代谢网、传染 疾病网、社会网络等的统计性质，这些性质主要有网络的小世界特性、度分布的特征， 我们看到这些特性在自然界许多真实网络中普遍存在“m 1 4 , 1 7 p l t 2 2 2 5 。4 , 4 t , 5 0 1 。社会网络与其他 大部分类型的网络包括技术网络和生物网络有着许多的共同点，但也存在两个重要的不 同，( 1 ) 社会网络存在相当程度的聚集性和传递性，( 2 ) 在近邻节点的度之间有确定的 相干性】。 1 0 第2 章复杂网络 第2 章复杂网络 2 1 复杂网络中的几个重要概念 经典图论对于网络拓扑的研究是从节点与节点的连接度、构成图的连通性等方面入 手分析随机网络的，而近年发展最快复杂网络是用概率的方法研究网络的生长演化。描 述生长随机网络的几个必要的物理量是度、度分布、集团系数、平均路径长度、连接度， 用这几个参数反映网络的性质。 2 1 1 度和度分布 一个节点所拥有的度( d e g r e e ) 是该节点与其他节点相关联的边数，度是描述一个网 络图的虽基本的术语。节点的度( d e g r e e ) 与节点的连接度( c o n n e c t i o n s ) 是两个不同概念， 在经典图论中连接度反映了一个图连通性的强弱。对节点度的认识要从三个不同的出发 点，网络中的节点可能主动连接到其他节点也可能被其他节点连接或者不论主次只要节 点间有相互作用就计连接，考虑到节点连