（运筹学与控制论专业论文）加权网络模型及其在实际网络中的应用.pdf

2 0 0 7 年上海大学硕士学位论文 摘要 现实世界的许多系统都可以用图来表示，图的结点代表构成系统中的个体， 结点之问的连线代表个体之间的相互作用。所谓复杂网络就是具有复杂拓扑结构 和动力行为的大规模网络，它是由大量的结点通过连线的相互连接而构成的图。 大量的自然和人造系统的结构都可以用网络来表示。典型的例子有大型的信息网 络( 如因特网、电话网、万维网) ，交通网络( 如铁路航线、飞机航线) ，生物网络( 如 基因调控网、蛋白质相互作用网络) 以及各种社会网络( 如科学家合作网) 。为了研 究这些系统的结构和特征，各种模型相继提出，例如随机图模型( e r 模型) ，小 世界模型( w s 模型) ，无标度网络模型( b a 模型) 等。但是，大部分模型都是简单 图，即两结点间只有一条连线或者没有连线。我们可以用邻接矩阵 a = a 。】，i , j ( 1 ，n ) 来表示它们的拓扑性质，a “= l 表示两结点问有连线， 口。= 0 表示没有连线。然而，实际的网络除了具有复杂的网络拓扑结构外，它的 各条连线上的容量和密度是不相同的，即它的每条连线上都有一个权重。于是人 们又引进了加权网络，它可以用矩阵w = 【w e 】，f ，j l ，) 来表示，其中是 i ，连线上的权重。 连线上的权重为复杂网络中结点之间的关系和相互作用提供了更加细致的 刻画，而权重及其分布会对网络的拓扑性质和功能产生重要影响；加权网络可以 更好地解释网络的构造和组织原则，从而有效地研究网络的新特征。所以加权网 络已经成为复杂网络研究的一个重要领域。 本文利用马氏链的方法计算了加权网络模型的强度分布，并且提出了一个加 权网络的新模型以及研究了该模型在社会网络中的应用。 第一部分，简要地介绍了复杂网络的基本内容和本课题的研究背景，并对本 文研究内容做了扼要阐述。 第二部分，比较详细地介绍了加权网络的研究现状，对各种加权网络的模型 和加权网络在实际网络中的应用做了简要论述。 第三部分，用m a r k o v 链的方法对加权网络的强度分布进行了研究。经计算， b b v 模型和中科大模型强度分布的结果与用平均场方法所得的结论是一致的。 第四部分，根据演员合作网络的实证研究，提出了一个可重复连线的网络模 型。通过计算机模拟和理论推导，该模型更符合社会网络的实际情况。 2 0 0 7 年上海大学硕士学位论文 本文的结论部分对本文做了概括性的总结，并对加权网络今后的工作重点做 出了展望。 关键词：加权网络；演员合作网络；可重复连线模型；马氏链；强度分布 2 0 0 7 年上海大学硕士学位论文 a b s t r a c t m a n ys y s t e m si n r e a lw o r l dc a bb ee x p r e s s e db yg r a p h s ，t h en o d e so fg r a p h , t h e n o d e si ng r a p hr e p r e s e n ti n d i v i d u a l si nt h es y s t e m , t h ee d g eb e t w e e nt w on o d e s r e p r e s e n t st h er e l a t i o nb e t w e e nt w oi n d i v i d u a l s w h a ti sc a l l e dc o m p l e xn e t w o r ki s t h el a r g en e t w o r kh a v i n gc o m p l e xt o p o l o g ya n dd y n a m i c s t h es t r u c t u r e so fl o t so f n a t u r a la n dm a n u a ls y s t e m sc a l le x p r e s s e db yc o m p l e xn e t w o r k s f o re x a m p l e ， i n f o r m a t i o nn e t w o r k s ( e g i n t e r a c t , t e l e p h o n en e t w o r k s ，w w w ) ；t r a f f i cn e t w o r k s ( e g r a i l w a y , a i r l i n e ) ；b i o l o g i c a ln e t w o r k s ( e g ，g e n er e g u l a t i o nn e t w o r ka n dp r o t e i n r e l a t i o nn e t w o r k ) a n da l lk i n d so fs o c i a ln e t w o r k s ( e g s c i e n t i s tc o l l a b o r a t i o n ) t o r e s e a r c ht h e s en e t w o r k s s t r u c t u r ea n dc h a r a c t e r i s t i c ，a 1 1k i n d so fm o d e l sa r e c o n s t r u c t e d , f o re x a m p l e ，r a n d o mg r a p hm o d e l ( e rm o d e l ) ，s m a l lw o r l dm o d e l ( w s m o d e l ) ，s c a l e - f r e em o d e l ( b am o d e l ) t h e s em o d e l sa r es i m p l eg r a p h s ，n a m e l yt h e n u m b e ro fl i n kb e t w e e nt w on o d e si se i t h e r0o r1 w ec a nu 8 eaa d j a c e n t m a t r i x a = 【a “】， l ，n t oe x p r e s st h e i rt o p o l o g y ；l f a j j = l ，t h e r ei sal i n k b e t w e e nt w on o d e s ；i f a = 0 ，t h e r ei sn o t h o w e v e r ，b e s i d e sr e a ln e t w o r k sh a v e c o m p l e xt o p o l o g i c a ls t r u c t u r e ，e a c hl i n k sh a sd i f f e r e n td e n s i t ya n dc a p a c i t y , n a m e l y e a c hl i n k sh a saw e i g h t ，8 0 w e i g h t e dn e t w o r ki si n t r o d u c e d w ec a nu s ea m a t r i x w = w t 】，( 1 ，n t od e s c r i b ei t ：w 。i s t h ew e i g h to nt h ee d g e b e t w e e ni a b dj w e i g h to nt h ee d g ep r o v i d em o r ed e t a i l e de x p l a n a t i o n s f o rt h er e l a t i o na n d i n t e r a c t i o nb e t w e e nt h en o d e s ，h o w e v e rw e i g h ta n di t sd i s t r i b u t i o nw i l lp r o d u c e i m p o r t a n te f f e c tt oq u a l i t ya n df u n c t i o no fn e t w o r k s w e i g h t e dn e t w o r k sc a be x p l a i n t h es t r u c t u r ea n do r g a n i z a t i o no ft h en e t w o r kb e t t e rt or e s e a r c ht h ec h a r a c t e ro ft h e n e t w o r v s ow e i g h t e dn e t w o r ki sav e r yi m p o r t a n tf i e l do ft h er e s e a r c ho fc o m p l e x n e t w o r k i nt h i sp a p e r , t h ec o m p u t a t i o no ft h ew e i i g h t e dn e t w o r k s s t r e n g t hd i s t r i b u t i o nb y m a r k o vm e t h o d ，t h em o d e l so ft h ew e i g h t e dn e t w o r ka n di t sa p p l i c a t i o no ns o c i a l n e t w o r k sa r er e s e a r c h e d i nt h ef i r s tp a r t ，w eb r i e f l yi n t r o d u c et h eb a s i cc o n t e n ta b o u tc o m p l e xn e t w o r k sa n d t h eb a c k g r o u n do f o u rr e s e a r c ht o p i c ，a n db r i e f l yi n t r o d u c et h er e s e a r c ho f t h i sp a p e r ； i nt h es e c o n dp a r t , w ei n 仃o d u c ei n d e t a i lt h er e s e a r c hd e v e l o p m e n to fw e i g h t e d r i ! 竺：兰圭童查兰堡主兰笪丝苎 n e t w o r k s a n d 栅o d u eb r i e f l ya l lk i n do f w e i g h t e dn e t w o r km o d e l sa n dt h e 毗i l i t yi n t h er e a lw o r l d i nt h et h i r dp a r t , t h es t r e n g t hd i s t r i b u t i o no fw e i g h t e dn e t w o r kw h i c hi sc o m p u t e d b ym a r k o v - c h a i nm e t h o di ss t u d i e d b yc o m p u t i n g ，t h er e s u l t s o fb b vm o d e la n d u s t cm o d e la g r e ew e l lw i t hw h i c ha r eg o tb yt h em e r n f i e l dm e t h o d i i lt h ef o r t hp a r t a c c o r d i n gt ot h eo ft h ea c t o r sc o l l a b o r a t i o nn e t w o r k , ar e p e a t a b l e l i n k e dm o d e la r ep o s e d b ys i m u l a t i o na n dt h e o r e t i cp r e d i c t i o n , t h i sm o d e l t a l l i e sw i t h a c t u a ls i t u a t i o n i nt l ec o n c l u s i o ns e c t i o n ，a l lt o p i c si nd i s c u s s i o na r eb r i e f l ys u m m a r i z e da n dt h e p o s s i b l er e s e a r c ht o p i c sa b o u tw e i g h t e dn e t w o r k s i nt h ef u t u r ea r ep o i n t e do u t k e y w o r d s ：w e i g h t e dn e t w o r k ；t h ea c t o r sc o l l a b o r a t i o nn e t w o r k ；r e p e a t a b l el i n k e d m o d e l ；m a r k o vc h a i n ；s t r e n g t hd i s t r i b u t i o n i v 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研 究工作，除了文中特别加以标注和致谢的地方外，论文中不包 含其他人已发表或撰写过的研究成果参与同一工作的其他 同志对本研究所做的任何贡献均已在论文中作了明确的说 明并表示了谢意 签名：茹款日期：岬( ，) 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规 定，即：学校有权保留论文及送交论文复印件，允许论文被 查阅和借阅；学校可以公布论文的全部或部分内容 ( 保密的论文解密后应遵守此规定) 签名：垂希议 导师签名： 袁蕾汤 日期：呻- 5 j 2 0 0 7 年上海大学硕士学位论文 第一章绪论 网络是由结点( | ) 和连线( 占) 构成的集合，是对现实世界各种系统中普遍存 在的网状结构的一种数学抽象，其中网络结点表示构成系统的元素，两结点之间 的连线表示元素之间的相互作用。科研人员通常把各种具有复杂结构与功能的大 规模随机演化网络统称为复杂网络。近年来，复杂网络引起了国际学术界的普遍 关注，已成为数学、统计物理学、计算机科学、系统科学、生命科学以及社会学 等多个学科的研究热点 i - 4 。科学家致力于探索复杂系统的拓扑结构，演化规律 和动力学行为。 1 1 复杂网络的基本内容 在现实世界中，网络形式的系统随处可见，例如：因特网i s l ，万维网 6 1 ，交 通网络【7 1 ，生物网络 1 0 , 1 1 , 1 2 1 等等。 数学中最初以图论的形式展开对网络的研究。e u l e r 在1 7 3 5 年提出了著名的 七桥问题，这是网络理论的第一个严格证明；到二十世纪五十年代，网络研究已 经成为一个重要的知识实体。 匈牙利数学家e r d o s 和r 6 n y i l l 3 j 4 1 首先引进了随机图的严格定义并对其展开 了系统的研究。此后，随机图理论成为对无明确设计原理的大规模网络( 即复杂 网络) 进行建模的基本工具。尽管随机图理论能够很好地解释一部分现实网络的 结构及其具有的功能，譬如对网络上逾渗问题的成功解决；但是，绝大部分的实 际网络( 如因特网和万维网) 都具有时间演化行为，具有一定的自组织机制，不能 仅仅依靠纯粹的随机性来构造。二十世纪五十年代后，随着混沌、分形和非平衡 态物理等新兴学科的创立及其迅速发展，人们对现实世界的理论认识达到了一个 全新的广度和深度；更为重要的是，由于计算机技术的飞速发展，计算能力的提 高，使得对大规模网络数据的采集和分析成为可能，为二十世纪九十年代末复杂 网络研究的突破性进展提供了强有力的分析和计算工具。 基于计算机仿真和大规模的实际网络数据库的支持，1 9 9 8 年w a t t s 和 s w o g a t z 【“1 提出s m a l l w o r l d ( d x 世界) 网络模型；1 9 9 9 年，b a r a b f i s i 和a l l 州 “1 提 出s c a l e f l e e ( 无标度) 网络模型。与随机图模型相比，这两种网络模型较好地解释 2 0 0 7 年上海大学硕士学位论文 了一些实际网络( 如因特网和科学家合作网) 的自组织形成机制，理论结果和实际 数据比较吻合。 1 1 1 刻画复杂网络的常用测度 为了研究复杂网络的结构和功能，人们引进了刻画网络结构的几个常用测 度：度分布( d e g r e ed i s t r i b u t i o n ) 、平均路径长度( a v e r a g ep a t hl e n g t l l ) 和群集系数 ( c l u s t e d n gc o e f f i c i e n t ) - 度分布p ( k ) ：网络中随机选择的一个结点具有t 条连线的概率。度分布能够 表征网络的许多重要结构特征。 平均路径长度f ：网络中两个结点的距离定义为连接它们的最短路径的连线 数。平均路径长度，是网络中所有结点对的距离的算术平均值。平均路径长度度 量了网络的连通性。 群集系数：反映网络的群聚程度。在网络中选出的结点i 上，有k ，条连线使 它与其它。个结点相连接。它们之间最多可能有毛( 墨一1 ) 2 条连线。向个结点之 间实际有的连线数互与t ( 毛一i ) 2 之比就是结点的群集系数值： 嘲= 蒜 ( 1 1 1 ) 整个网络的群集系数c 为所有结点c ( f ) 的平均值，即c 2 吉；c ( f ) 。 1 1 2 三个重要的复杂网络模型 豫随机网络：1 9 6 0 年前后，e r d 6 s 和雕n y j 应用概率论方法研究图论问题，提出 了e r 随机图模型 1 3 , 1 4 。 e r d f s 和r 6 n y i 将随机图定义为：具有个结点，条连线的图，这珂条连 线是从( 一d 2 连线中随机选取的，这样的图一共有c 品( 。) ，2 种，其中每一种 图出现的概率都是相同的，这些图构成了一个概率空间。这种随机图称为 g ( n ，订 随机图的另种定义：给定个结点，每对结点之间以概率p 连接，总连 线数疗是一个随机变量，期望值为e ( n ) = v ( 一1 ) 2 。设g 。是一个有个结点， 2 0 0 7 年上海大学硕士学位论文 ”条连线的图，所以g 。获得的概率为：p ( g o ) = ( 1 一p ) 学”。这种随机图称 为g ( n ，力。 小世界网络：随机图和规则网络能够刻画一部分实际网络的拓扑结构，但实证研 究发现n ”】，许多生物网络、技术网络和社会网络却介于这两种网络之间，即不 但具有较短的平均路径长度，而且具有较高的群集系数。1 9 9 8 年，w a t t s 和 s t r o g a t z ”1 提出小世界网络( s m a l l - w o r l dn e t w o r k s ) 模型( w s 模型) ： 1 从规则网络开始：从具有个结点的环形网络开始，其中每一结点都与 初始的x 个邻点相连。 2 随机化：以概率p 随机为网络的每条连线重新布线，同时保证没有自连 线和重复连线。这一过程引进了p n k 2 条长距离连线，它们连接那些不同于邻 点的一部分结点。随着p 的改变，网络会在规则网络( p = o ) 和随机目f l ( p = 1 ) 之 间变化。 无标度网络：近年来，随着实际网络数据库容量的增加以及计算机能力和存储能 力的提高，使得人们对大规模网络的实证研究成为可能。1 9 9 9 年，a l b e r t ，j e o n g 和b a r a b t t s i t e l 发现实际网络的度分布不是p o i s s o n 分布，而是重尾特征的幂律分 布。这个特性称为无标度性( s c a l e f r e an a t u r e ) ；同年，b a r a b g s i 和a l b e r t n 6 1 提出 了b a 模型： 1 增长：开始于较少的结点数量0 ，在每个时间间隔增添一个具有 朋( n o ) 条连线的新结点，与肌个已存在于网络中的旧结点相连。 2 择优连接：假设新结点n 连接到旧结点i 的概率兀取决于结点i 的度数 k j ，即 k ，2 南 o 1 2 ) 经过t 步时间，b a 模型演化成具有n ；所。+ ，个结点和r a t 条连线的网络。 2 0 0 7 年上海大学硕士学位论文 1 2 加权网络的产生背景 至今提出的大部分网络模型都是无权网络，邻接矩阵( a d j a c e n tm a t r i x ) 的元素 非0 即1 ，即结点之间的连线只有存在或不存在两种情况。显然，无权网络只能 给出结点之间的相互作用存在与否的定性描述，这种定性描述反映了相互作用最 重要的信息。但是在许多情况下，除了复杂的拓扑结构外，它的每条连线上的容 量和密度是不相同的，结点之间的关系或相互作用强度的差异起着至关重要的作 用。例如，神经网络中连线的权重对于网络功能的实现至关重要；食物链网 络中捕食关系及其强度的多样性”】，以及新陈代谢反应速率之间的差别是维持 生态系统和新陈代谢稳定的重要因素；在社会系统中，相互作用强度对网络 上的疾病传播等过程会产生重要影响j ；i n t e r a c t 网络上的带宽呻1 ，航空网中两 个机场间航班的数量或者可容纳的客流量n 。9 】，科学家合作网和演员合作网中的 合作次数等 2 1 - 2 6 都是研究这些系统的重要因素。因此，无权网络中仅用一条连 线表示连接的存在与否不能准确地反映实际网络的细致结构及其功能，这就需要 引入连线上的权重( w e i g h to f l i n k ) 来刻画连接的差异性，从而形成加权网络。 2 0 0 4 年，b a h a t 等人嗍分别研究了科学家合作网( 社会网络) 和全球航空网( 交 通网络) 。针对这两种类型的网络，作者结合网络的拓扑结构和连线上的权重引 进了一些统计量，用来描述系统中结点间关系的密切度；同时这些量可以描述出 权重和网络拓扑结构的关系，从而揭示真实加权网络的复杂结构。以下给出的是 这两个特殊加权网络的数据： w a n ( w o r i d - w i d ea i r p o r tn e t w o r k ) ：分析了2 0 0 2 年全球航空网数据库 ( w w w i a t a o r g ) q 5 直航航线和航线上可容纳的客流。在这个网络中，= 3 8 8 0 ( 代 表机场) ，e = 1 8 8 1 0 ( 代表航线) 。网络的平均度( k ) = 2 可n = 9 7 0 ，且最大度数 是3 1 8 。平均最短路径( 表示网络中任意两个结点间连线的平均数) ( d = 4 3 7 ，远 小于网络的规模。网络的度分布p ( k ) = k - r f ( k k x ) ，这里，兰2 0 ，( k k ，) 是指 数截断函数 2 7 , 2 9 。 s c n ( s c i e n t i s tc o l l a b o r a t i o nn e t w o r k ) ：分析了1 9 9 5 年至1 9 9 8 年在e p r i n t a r c h i v e 上发表过文章的科学家之间的合作 碉( h t t p ：x x x 1 a n l g o v ) 。网络中结点表 示科学家，连线表示两个科学家之间合作发表过文章。网络中n = 1 2 7 2 2 ，平均 2 0 0 7 年上海大学硕士学位论文 度( 女) = 6 2 8 。网络的拓扑结构和其它类似的科学家合作网已经在文献【2 l 】【2 2 】【2 9 】 做过研究。 对于科学家合作网，b a r r a t 等人引用了n e w m a n 等对权重的定义2 1 捌：合作 者i 和，的密切程度 = 莓等州一。 ：m 这里指数p 表示所有的文章，n 。表示文章p 的作者数量，若作者i 参与写作了文 章p ，那么彤= 1 ；否则彤= 0 。 我们习惯用邻接矩阵a = 【4 。】来表示无权网络的性质，当结点，和结点，相连 时，元素= l ，否则就为o ；而结点f 的度t = ，d 口。当引入加权网络后，我 们用矩阵w = 【w ，。】来表示；并且引进了结点强度的概念： j ，= 口 ( 1 2 2 ) 可见结点强度是连接该结点所有连线上权重的和。在w a n 中，结点强度表 示一个机场所能处理的所有客流量；而对于s c n 来说，某个结点的强度就表示 该科学家发表的文章数目。这个量表示了一个结点在网络中的重要性。通过图 1 1 ，图1 2 ，我们发现这两种网络中结点强度s 的分布p ( s ) 与结点度t 的分布p ( _ i ) 是非常相似的。 权重代表了复杂系统中连线上的容量和密度，它可以帮助我们更好地去分析 现实网络的结构和组织原则。加权网络中强度和度有什么样的关系，该用什么样 的模型来解释加权网络的结构和性质等等，都需要我们进一步地解释和研究。 i 伽n m k 村，q 哪时 2 0 0 7 年上海大学硕士学位论文 图1 1 科学家合作罔中度和强度的分布度表示每个科学家合作的人数，强度 表示科学家合作发表的文章由图可知，度和强度都是幂律分布的 ；醯删”嘲 图1 2 全球航空网中度和强度分布图。度为某机场的直航航线，强度为机场 所能分配的客流由图可知，度k 和强度j 都遵循幂律分布 1 3 本文研究的问题及成果 由于加权网络的研究内容非常广泛，涉及的学科众多，我们选择了加权网络 的模型和加权网络强度分布的计算作为本文的主要研究方向。 本文对加权网络作了以下两个方面的研究：( 1 ) 用马氏链的方法计算b b v 和 中科大加权网络模型的强度分布；( 2 ) 结合演员合作网络，提出了一个特殊的加 权网络模型一可重复连线的模型，该模型更符合社会网络的性质。具体工作如下： 1 3 1 马氏链方法在加权网络中的应用 这是本文第三章的主要工作。对于b b v 模型和中科大模型，科学家使用动 力学( 平均场) 方法给出了模型强度分布的解析解溉”l 。但人们在处理更复杂的模 型时，并不能准确地给出强度分布的解析解。史定华等人啪1 提出了应用非齐次 马氏链计算复杂网络度分布的方法。我们运用这种方法，从马氏链的转移概率矩 阵出发，根据矩形迭代算法，计算了b b v 模型和中科大模型的强度分布；与动 力学方法得到的结果比较后，我们得出用马氏链计算b b v 模型和中科大模型强 度分布是非常有效的。 2 0 0 7 年上海大学硕士学位论文 1 3 2 可重复连线模型 这是本文第四章的主要工作。该模型是一种特殊的加权网络模型。通过分析 演员合作网络的数据库，发现网络度分布p ( | | ) 七- ， k ，说 明具有较大权重的连线倾向于连接具有较大度的结点：反之，七麓 0 时，口依赖于m 的现象在z t z h 模 型中仍然存在；只有当p = 0 时，a 与搠是无关的。 3 ac o m p r e h e n s i v ew e i g h t e de v o l v i n gn e t w o r km o d e l ( c h u n gg u a n gl i ，g u a n r o n gc h e r t ，2 0 0 4 ) 蚓 本文提出了一个观点：实际网络中的连接和加权并不一定是择优的，也可能 是随机的。例如科学家合作网络( s o 田：一个学生作为加入某个研究领域的新成 员，肯定会先与自己的导师合作，而不是同他不认识的但知名度高的学者合作。 在这种情况下，新结点选择连线的结点是均匀分布的，即随机连接；如果两个人 合作成功的次数较多，他们就会继续合作下去来增加他们的论文数量，即择优加 权；但是，这种择优加权有的时候是不成立的。比如，某个人转到另外一所大学， 他会加入该领域中新的合作组，而停止或减少了以前的合作，因此这里可以认为 是随机加权。 模型的构造：初始图是具有0 个结点的全连通图。在每个时间步t ： 【l 】以概率口加入一个强度为l 的新结点栉：该结点以概率择优连接到 一个已存椭结胁l 其择譬醉加矿南拟胖1 - 醐地选铲 个旧结点与之连接； 1 2 1 以概率l 一口不增加新结点，只增加一条权重为1 的新连线；该连线 建立在两个已存在的结点i ，之间。这两个结点按以下的规则选择：以概率卵， 加州2 泰黜阶糕黻川解1 - 椭枞龇阶徽黻。 结论：通过计算机模拟，该模型中结点的度，强度以及边上的权重都是幂律 分布的。 4 b b v 模型( 2 0 0 4 ) ”1 该模型是加权网络的经典模型，它是在拓扑结构增长和权重动力学机制的基 础上建立的。 模型的构造：该模型的初始图是具有。个结点的全连通图，且每条连线上 2 0 0 7 年上海大学硕士学位论文 的权重为w o 。 【1 】每个时间步t 加入一个新结点”，它与m 个旧结点相连，且结点f 被 连接到的概率为 k t 2 袁 亿2 。3 且每条新连线上的权重为w 0 ； 2 1 由于引进了一条新的连线( n , i ) ，网络中连线上的权重发生了改变， 我们考虑连线( f ，力，_ ，v ( 0 上权重的重新分布： w f w 口+ w ，这里= 万孚 ( 2 2 4 ) 所以，s js ，+ 占+ w 0 ，这里占是常数。 结论：通过计算机模拟和平均场方法计算，模型中p ( s ) ，p ( k ) ，p ( w ) 都遵 循幂律分布：，( 们一w ，y w = 2 + 否1 ；尸( ) k ，p ( s ) s 一，= 口= 筹o1 ；口上十 因此b b v 模型可以生成幂律衰减指数介于 2 ，3 】之问的无标度网络。当万= 0 时， b b v 网络的拓扑结构与b a 模型的完全相同，此时y = 3 ：当占斗0 0 时，= 2 。 同时，这里给出了结点强度与度之间的函数关系s ( k ) 4 _ i ，其中a ， 口= l ：即结点度和强度的关系是线性的。这只符合社会网的情况( 如科学家合作 网络) ，无法解释大型交通网( 如全球机场网络) 中度和强度的非线性关系。 5 中科大模型( g e n e r a ld y n a m i c so f t o p o l o g ya n dt r a f f i c0 1 1w e i g h t e d t e c h n o l o g i c a ln e t w o r k2 0 0 5 ) 3 。1 该模型是中科大组提出的，因此我们简称其为中科大模型，这是一个加权技 术网络的t r a f f i c d r i v e n 增长模型。前几个模型都引进了度或者强度的择优机理， 这会产生s c a l e f r e e 性质，但是在这些模型中择优机理仅仅描述了新加结点和旧 结点之间的关系；而实际上，旧结点之间也存在着这种机理。 模型的构造：初始图是具有。个结点的全连通图，且每条连线上的权重为 。在每个时间步t ： 【1 】强度动力学：所有的连接( 存在或没有的) 都按照以下方式更新它们的 2 0 0 7 年上海大学硕士学位论文 权重： 嘞寸1 k , 4 “豢 叫， 嘞寸 以概率1 一 u 。j 其鸭2 最，形州吨 为每一步所增加的权重的平均值；如果 阡巩 1 ，我们就按阡巩= l 来计算。 1 2 1 拓扑结构增长：一个新结点 加入到网络中，它与坍个旧结点相连。 其中结点f 被选择连接的概率： 队2 寺2 麸 q 2 6 且每条新连线上的权重为w o 。 结论：该模型中，连线上的权重分布p ( w ) ，结点的度分布p ( k ) 以及强度分 布尸( j ) 都是幂律分布，尸( 七) _ i ，尸( j ) 一j 一；其中结点强度分布的衰减指数 是口- 2 + 赤。 以下两个模型是科大研究组在这个模型上的推广： a 加权网络的双向选择模型( am u t u a ls e l e c t i o nm o d e lf o rw e i g h t e dn e t w o r k s 2 0 0 5 年8 b ) t 堋 模型的构造：模型开始于0 个独立的结点： 1 1 拓扑结构增长：每个时间步f 加入一个新的结点拧，它与研n o 个已 存在的结点连接，结点f 被选择到的概率为： 矿嚣s j 2 删 每条新连线上的权重为w o 。 2 1 双向选择动力学( m u t u a ls e l e c t i o nd y n a m i c s ) ：每个旧结点i 以概率 n 矿爱s i i 2 2 8 与1 日结点_ ，相连。 结论：模型中结点的度分布p ( 七) ，强度分布尸( s ) 和连线的权重分布p ( w ) 都 2 0 0 7 年上海大学硕士学位论文 遵循幂律性质，而且度 和强度s 之间的关系为s 扩，口 1 ；该模型仅能描述 负向相关匹配( d i s a s s o r t a t i v e ) 网络，即仅能描述技术和生物网络，无法描述正向 相关匹配( a s s o r t a t i v e ) 网络，如社会网络。 b 关于正向相关匹配和负向相关匹配加权网络的双向选择模型( m u t u a l a t t r a c t i o nm o d e lf o rb o t ha s s o r t a f i v ea n dd i s a s s o r t a t i v ew e i g h t e dn e t w o r k s ) 删 模型的构造：模型开始于0 个独立的结点，每个结点的初始吸引度为a 。 在每个时间步f 加入一个独立的结点行；该系统中每个已存在的结点f 与m 个旧结 点连接，结点，被选择的概率为： s + a n j 叫5 意乏丽 g 2 9 一 这种连线方式发生在网络的整体结构中，但是并无法保证新连线的增加或连线权 重的加强；只有当两个结点互相选择的时候，新连线或者连线上的权重才增加； 按这种过程进行下去，直到达到所需的网络规模。为保证孤立点能被选到，这里 a 0 。 结论：该模型中结点的度分布e ( k ) 、强度分布p ( s ) 和连线上的权重分布 p ( w ) 都遵循幂律性质，其模拟结果与理论计算一致。该模型是由脚和初始吸引 度彳控制的，会产生加权网络的可调节匹配方式。 2 3 加权网络在实际中的应用 加权网络引入了结点之间相互作用的强度，刻画了连接的多样性，增加了网 络的抽象刻画能力。同时，连线上权重的引入也极大地丰富了网络的统计特性， 除了结点的连接度外，我们也注意到了连线上的权重和结点强度的统计特性。许 多实证表明，加权网络表现出了丰富的统计特性和幂律行为。以下简要地介绍一 些典型的实际系统和相应的分析结果： 【1 】生物网络 在细胞网络、基因相互作用网络、蛋白质相互作用网络以及其它的细胞分子 调控行为中，拓扑结构起着重要作用。最近有研究表明，相互作用的强度也非常 关键。 2 0 0 7 年上海大学硕士学位论文 e a l m a a s 等人把e c o l im e t a b o l i s m 中的新陈代谢反应看作加权网络进行 了研究n 0 1 ，其中把从代谢物i 斗，的流量看作权重。研究发现，流量具有高 度的非均匀性，在理想的培养条件下，连接上的权重( 流量) 的分布符合幂律分布： 10 2 p ( 们( w + ) ”，其中w o = o 0 0 0 3 ，口- - 1 5 。令】，( t ，1 ) = 丢f l - ) ，；9 表 i “乙| 0 “ 示通过化学反应，产生( 或消耗) 代谢物i 的质量：如果所有反应消耗或产生代谢 l 物i 的量一样，那么r ( k ，i ) ；如果只有一个反应控制着y ( 女，0 ，那么 丘 】，( 女，d = c o n a t 。我们通过计算y ( j | ，d 可以观察到在单个代谢物的层面上权重分布 的非均匀性。在该网络中，对出度和入度相同的结点计算了连线上权重的差异性， 1 发现y ( 女，i ) k “”，这是一种介于】，( ，力= c o n s t 和y ( k ，力之间的中间状态， 再 这说明一个代谢物参与化学反应的数量越多( 被消耗或产生) ，其中一个反应承载 着大部分流量的可能性越高。 1 2 1 社会网络： 科学家合作网，电影演员合作网，e m a i l 网络以及人际关系网等等都是典型 的社会网络，其中许多网络的拓扑性质，如科学家合作网已经得到了深入的研究。 在无权的科学家合作网中，结点代表的是科学家，如果两个科学家至少合作过一 次，则对应的结点之间连线。但在实际情况中，许多科学家之间合作过多次，无 权网中的连线只能给出他们之间的定性关系，不能说明他们之间联系的密切度， 因此需要用加权网络中的权重来区分密切程度的差异。 以科学家合作网为例，n e w m a n 给出了科学家合作网的基本统计性质叫丑】， 定义科学家合作网的权重坳= 。酽彤( 拧，一1 ) ，其中p 表示数据库里的所有文 章，如果f 是文章p 的作者之一，那么酽= l ，若否彤= 0 ，胛，表示文章p 的作 者数。归一化因子n 。一1 考虑了合作者的多少对合作关系的影响。从平均效果来 看，合作者较少的作者之间合作更加密切，这与实际情况也是一致的。 b a r r a t 等也研究了科学家合作网嗍。研究发现，结点强度的分布p ( s ) 与度分 布p ( ) 的情况类似，都有重尾现象( h e a v yt a i l ) 。结点强度的平均值与度的关系表 2 0 0 7 年上海大学硕士学位论文 现为线性关系j