（理论物理专业论文）复杂网络上自组织临界现象及opinion演化动力学研究.pdf

博士学位论文 d o c t o r a l d i s s e r t a t i o n 摘要 自然科学和社会科学领域中的许多复杂系统都可以用复杂网络加以描述。大量的实证 研究表明，真实网络中呈现出区别于规则网络和随机网络的特性，如小世界特性、无标度 特性、层级结构特性等等。因此，对于复杂网络的拓扑特性的清晰认识将为研究复杂网络 的动力学研究奠定基础。在本文中我们侧重研究复杂网络的拓扑结构和复杂网络上动力学 行为之间的相互关系，从而由动力学角度探寻复杂网络拓扑特性的涌现机制。 具有创新性研究的成果，有以下五个方面： 1 分析了复杂网络拓扑结构对分形维数的影响。首先，采用s h a n k e r 定义的分形维 数方法研究了真实网络的分形维数。然后，研究了小世界网络的捷径( s h o r t c u t s ) 对分形 维数的影响，通过非线性拟合给出了网络的分形维数d ，与捷径数( p ) 之间的函数关系。最 后，分析了规则格子尺寸对其分形维数的影响。这里，分形维数的定义可以推广到规则格 子中，且分形维数的计算是精确解。 2 首次提出利用列车运营情况的加权方法，研究了中国铁路网。首先，在l 空间中 分析了中国铁路网节点度分布以及节点度关联特性。然后，依据中国铁路网上实际列车运 营情况，对中国铁路网中的节点和边进行加权。其中，每列列车对其停靠的每一个车站的 贡献都是其停靠的所有车站数目的倒数。这里权重的定义弥补了抽象空间( l 空间和p 空 间) 中对网络拓扑分析的不足。 3 复杂网络节点异质性对复杂网络上动力学行为的影响。分析了静态无标度网 络上b a k - s n e p p e n 模型进化动力学。其中，静态无标度网络构造模型中可调参数反映 了网络中节点异质性的强弱。乜越大，网络的异质性越强。研究发现网络的临界平均适 应度( ，) 。随着a 的增加而减小。另一方面，网络的( ，) o 雪崩指数，- 随着可调参数q 的变化 而呈现阶梯下降，结合静态无标度网络上疾病传播动力学行为，将无标度网路分为三 类：随机类、线性类和物理类。最后，分析了规则格子、小世界网络和无标度网络上改 进d e f f u a n t 模型演化动力学，我们发现系统稳态o p i n i o n 瓯随着信任参数变化呈现出分叉 现象。通过分析较小团簇的o p i n i o n 及节点度与信任参数e 的关系，发现小世界网络和无标 度网络上o p i n i o n 达到一致态的形成过程具有明显差异，这在复杂网络的同步现象中也有所 博士学位论文 d o c t o r a l d i s s 日n 1 0 i n 呈现。 4 小世界网络捷径对o p i n i o n 形成动力学的影响。类比于统计物理中的i s i n g 模型， 研究y d , 世界网络上二态o p i n i o n 演化动力学。通过分析系统的o p i n i o n 磁化强度、空间关 联特性以及时间关联特性，发现小世界网络中的捷径具有增强系统长程关联的作用，从而 促使系统演化到一致态。通过有限尺寸效应分析，发现从一维环开始生成的小世界网络 上o p i n i o n 相变是赝相变。 5 自适应网络上社团结构的涌现。构造了一个简单的自适应网络演化模型。如果 网络中两活动节点的o p i n i o n 之差大于信任参数e ，连接这两节点的边将断开；反之。节点 之间的连边促使两节点的o p i n i o n 俺 彼此靠近。靠近强度依赖于收敛参数p 。网络中断边的 重绕依据局域重绕连接和全局重绕连接两种方式。这反映了网络的拓扑结构演化动力学 与网络上节点状态演化动力学之间的相互作用。通过模拟研究，发现全局重绕增强网络 上o p i n i o n 演化到一致态的相变能力；而局域重绕连接增强网络社团结构的涌现。局域重绕 连接概率越强，网络中社团的模块强度越大。 关键词： 复杂网络；分形维数；自组织临界性；o p i n i o n 动力学；异质性；分叉现象：自 适应网络：社团结构 n 博士学位论文 d o c m i u l ld i s s e r t a t i o n a b s t r a c t m a n yc o m p l e xs y s t e m sa r i s i n gf r o mn a t u r ea n dh u m a ns o c i e t yc a nb ed e s c r i b e da s c o m p l e xn e t w o r k s al o to fe x p e r i m e n t a lw o r k ss h o wt h a tr e a lc o m p l e xn e t w o r k ss h a r es o m e d i s t i n c t i v ec h a r a c t e r i s t i cp r o p e r t i e s ，s u c h 舾t h es m a l l - w o r l de f f e c t ，s c a l e - f r e ep r o p e r t ya n d t h eh i e r a r c h i c a ls t r u c t u r e ，w h i c hd i f f e rf r o mt h er a n d o mn e t w o r ka n dt h er e g u l a rl a t t i c e t h et o p o l o g ys t r u c t u r eo fc o m p l e xn e t w o r k sh a sb e e ns t u d i e d ，w h i c hi sh e l p f u lf o ru st o s e a r c h t h ed y n a m i c so fa n do nc o m p l e xn e t w o r k s i nt h i sp a p e r ，w ef o c u so i lt h ei n t e r a c t i o n b e t w e e nt h ec o m p l e xn e t w o r ks t r u c t u r ea n dt h ed y n a m i c so nc o m p l e xn e t w o r k s ，a n ds t u d y t h ee m e r g e n c eo fs o m ed i s t i n c t i v ec h a r a c t e r i s t i cp r o p e r t i e si nc o m p l e xn e t w o r k sf r o mt h e v i e w p o i n to fd y n a m i c s 耽er e s u l t so f i n n o v a t i v er e s e a r c ha r es h o w na sf o l l o w s ： 1 t oa n a l y z et h ee f f e c t so | c o m p l e xn e t w o r ks t r u c t u r eo r bf r a c t a td i m e n s i o n f i r s t l y , t h ef r a c t a ld i m e n s i o n so fr e a lc o m p l e xn e t w o r k sa r es t u d i e db ym e a n so fs h a r t k e r sd e f m i - t i o n s e c o n d l y , t h ee f f e c to ft h es h o r t c u t si ns m a l l - w o r l dn e t w o r ko nt h ef r a c t a ld i m e n s i o n i ss h o w nt h r o u g ht h er e l a t i o nb e t w e e nt h ef r a c t a ld i m e n s i o nd ，a n dt h es h o r t c u t s ( n p ) ， w h i c hi sg i v e nb yt h em e t h o do fn o n l i n e a rf i t t i n g f i n a l l y , t h ee f f e c to ft h er e g u l a rl a t t i c e s i z eno ni t sf r a c t a ld i m e n s i o ni sa n a l y z e dt h r o u g he x a c tc a l c u l a t i o n 2t os t u d yt h ec h i n ar a i l w a yn e t w o r k ( c r n ) b yp r o 即s i n gt h ew e i g h t e dm e t h o d b a s e do nt h et r a i n s r e a lk i n e m a t i c s f i r s t l y , t h ed e g r e ed i s t r i b u t i o na n dt h ed e g r e e - d e g r e e c o r r e l a t i o no fc r ni ns p a c ela r es t u d i e d t h e n ，t h ew e i g h t e dp r o p e r t yo fc r ni sa n a l y z e d a c c o r d i n gt ot h et r a i n s r e a lk i n e m a t i c s t h ec o n t r i b u t i o no ft r a i njt ot e r m i n a ls t a t i o ni i s1 n j ( i ) ，w h e r e 吩( i ) i st h en u m b e ro fs t a t i o n st h a tt r a i njp a s s e s h e r e ，t h ed e f i n i t i o no f w e i g h tm a k e su pt h es h o r t a g eo fn e t w o r kt o p o l o g ya n a l y s i si nt h ea b s t r a c ts p a c e ( s p a b e s la n dp ) 3 t oa n a l y z eh o wt h eh e t e r o g e n e i t yo fc o m p l e xn e t w o r k sa f f e c t st h ed y n a m i c st h a t 博士学位论文 d o c t o r a l d l s s e r t a t i o n o c c u r 8o nc o m p l e xn e t w o r k s w ea n a l y z et h eb a k - s n e p p e ne v o l u t i o nm o d e lo ns t a t i cs c a l e - f r e en e t w o r k s ，w h e r eat u n a b l ep a r a m e t e rqi sd e f i n e dt od e s c r i b et h eh e t e r o g e n e o u sp r o p - e r t yo fc o m p l e xn e t w o r k t h el a r g e rai s ，t h em o r eh e t e r o g e n e o u st h en e t w o r ki s o u r s t u d ys h o w st h a tt h ec r i t i c a la v e r a g ef i t n e s s ( ，) 。d e c r e a s e sw i t h 口i n c r e a s i n g o nt h eo t h e r h a n d ，t h ee x p o n e n t7 o ft h e ( f ) oa v a l a n c h ed e c r e a s e si naf o r mo fs t a i r - c a s ew i t h 口i n c r e a s - i n g c o m b i n i n ge p i d e m i cs p r e a d i n gd y n a m i c so nt h es t a t i cs c a l e - f r e en e t w o r k sa n dt h e7 - e x p o n e n t ，t h es c a l ef r e en e t w o r k sc a nb ed i v i d e di n t ot h r e ec l a s s e s ：r a n d o mc l a s s ，f i n e a l c l a s sa n dp h y s i c a lc l a s s t h e n ，e x t e n d e dd e f f u a n tm o d e l so nr e g u l a rl a t t i c e ，s m a l l - w o r l d n e t w o r k sa n ds c a l e - f r e en e t w o r k s 扣es t u d i e d ，w h e r et h eb i f u r c a t i o np h e n o m e n ai sf o u n d ， t h r o u g ha n a l y z i n gt h er e l a t i o n s h i pb e t w e e nt h eo p i n i o n ，d e g r e ea n dt h eei nt h em i n o r i t y c l u s t e r s ，w ef i n dt h ef o r m a t i o np r o c e s so fo p i n i o ni ns m a l l - w o r l dn e t w o r k si sd i f f e r e n tf r o m t h a ti ns c a l e - f r e en e t w o r k s ，w h i c hi 8a l s of o u n di nt h es y n c h r o n i z a t i o np h e n o m e n ai nb o t h n e t w o r k s 彳t oa n a l y z et h ee f f e c to yt h es h o r t c u t si ns m a l l - w o r l dn e t w o r ko nt h eo p i n i o ny o r m a t i o nd y n a m i c s a c c o r d i n gt ot h ei s i n gm o d e li ns t a t i s t i c a lp h y s i c s ，w ei n v e s t i g a t et h e b i n a r yo p i n i o nf o r m a t i o nd y n a m i co ns m a l l - w o r l dn e t w o r k t h em a g n e t i z a t i o n ，s p a t i a l c o r r e l a t i o na n dt e m p o r a lc o r r e l a t i o na l es t u d i e d o u rr e s u l t ss h o wt h a tt h es h o r t c u t se n - h a n c et h ea b i l i t yo fl o n g - r a n g ei n t e r a c t i o n sw h i c hc a nd r i v et h es y s t e mt o w a r d sr e a c h i n g t h ec o n s e n s u ss t a t e o nt h eo t h e rh a n d ，t h ep h a s et r a n s i t i o ni nt h es m a l l - w o r l dn e t w o r k w h i c hi sb u i l to no n ed i m e n s i o ns u b s t r a t ei sap s e u d oo n e s t oa n a l y z et h ee m e r g e n c eo lc o m m u n i t yi nt h ea d a p t i v en e t w o r k as i m p l ea d a p - t i v en e t w o r km o d e li sp r o p o s e d t h ee d g eb e t w e e na c t i v ev e r t i c e si 8b r o k e nw h e nt h e d i f f e r e n c eb e t w e e nt w ov e r t i c e s o p i n i o ni sg r e a t e rt h a nt h ec o n i i d e n c ep a r a m e t e re ；o t h e r - w i s e ，e a c ho p i n i o nm o v e sp a r t l yi nf a v o ro f t h ed i r e c t i o no ft h eo t h e r t h er e w i r i n go ft h e b r o k e ne d g ef o l l o w st h er u l e so ft h er e w i r i n go fl o c a la t t a c h m e n t ( r l a ) a n dt h er e w i r i n go f g l o b a lr e w i r i n g ( r g a ) a l l i sm e n t i o n e da b o v es h o w st h ei n t e r a c t i o nb e t w e e nt h ed y n a m i c s o fc o m p l e xn e t w o r ks t r u c t u r ea n dt h ed y n a m i c so nc o m p l e xn e t w o r k t h r o u g hs i m u l a t i o n s ， w ef i n dt h a tt h er g ae n h a n c e st h ea b i l i t yo ft h es y s t e mr e a c h i n gt h ep h a s et r a n s i t i o n ， 博士学位论文 d o c t o r a ld i s s 目湖i o n a n dt h er l ae n h a n c e st h ef o r m a t i o no fc o m m u n i t ys t r u c t u r ei nc o m p l e xn e t ：_ w o r k s k e yw o r d s ：c o m p l e xn e t w o r k ；f r a c t a ld i m e n s i o n ；s e l f - o r g a n i z e dc r i t i c a l i t y ；o p i n i o nd y - n a m i c s ；h e t e r o g e n e i t y ；b i f u r c a t i o np h e n o m e n a ；s e l f - a d a p t i v en e t w o r k ；c o m m u n i t ys t r u c - t u r e 。 v 博士学位论文 d o c t o r a l d i s s 】日溯1 0 n 华中师范大学 学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作所取得 的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或集体已经发表 或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在文中以明确方式标 吼黧篓麟 学位论文作者签名：，f 疋p年了扩日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权保留并 向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权华 中师范大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影 印、缩印或扫描等复制 学位论文作者签名 日唧p 年月钼 编本学位论文。 指导教师签名： 日期：年月 日警影 本人已经认真阅读”c a l i s 高校学位论文全文数据库发布章程”，同意将本人的学位论 文提交”c a l i s 高校学位论文全文数据库”中全文发布，并可按”章程”中的规定享受相关权 益。同意论文提交后滞 学位论文作者签名 日旷 s 。月p 日 口一年；口二年发布。 指导教师签名： 日期：年月日 博士学位论文 i x ) c t o r a ld i s s 日疆幻删 1 绪论 1 1 复杂系统的网络描述 研究系统的粗粒化以及研究系统在结构或动力学层次上的普适性是复杂性科学领域中 开展研究工作的两个重要方向。众所周知，在统计物理中，研究多体相互作用系统中群体 现象的涌现机制仍是传统的研究兴趣之一。复杂网络作为一门交叉学科，越来越得到不同 学科的关注。复杂系统的网络化有利于我们利用纯粹的统计粗粒化方法分析，得到系统的 重要信息。其中，由于不必过细考虑系统内部详尽的特征，在抽象网络表象下对不同系统 的分析研究，有利于比较不同的复杂系统，也更容易得到这些系统的共性。 网络是由许多相互作用的组元组成的一个集合，其中组元称为节点，组元之间的相互 作用体现在节点之间存在的连线( 边) 。在自然科学和社会科学领域中，大量系统都可以 用这种粗粒化的方法来描述。例如，网络理论在因特网上的应用f l ，2 1 。我们不可能知道因 特网的详尽性质，但是可以通过统计分析的方法研究因特网的拓扑结构和功能特性。这 样，因特网的许多特征也可以很好地在网络理论表象中得以呈现。 1 7 3 6 年，瑞士数学家欧拉( l e o n h a r de u l e r ) 发表了哥尼斯堡( k o n i g s b e r g ) 七桥问题 ( 考虑是否存在一条环形路径，使得这条路径通过普鲁士国的哥尼斯堡城市中的七座桥， 并且每座桥只允许经过一次) 的解。如图1 1 1 。自此，图论得到了激动人心的发展并为一 系列实际问题提供了答案。例如，如何用最少的颜色对地图上不同区域进行着色，其中相 l 博士学住论文 d o c t o r a ld i s s e r t a t i o n 邻区域着不同的颜色：如何最大效率地把1 3 个人安排到n 个工作岗位上。随着数学图论的发 展，对网络的研究开始渐渐地渗透到不同的领域，例如社会科学。社会网络分析，始于二 十世纪二十年代。关注社会实体之间的关系上，例如不同群体之间的通信交流，国家之间 的贸易关系，企业之间的经济往来等。 b 图1 - 1 1 ：欧拉七桥问题简图。 d 近一二十年来，复杂网络是网络领域一个新的研究方向它是网络理论发展中的一个 里程碑。这一研究方向的迅猛发展，始于自然和科学杂志上两篇里程碑式论文。 这两篇论文分别是1 9 9 8 年w a t t s 和s t r o g a t z 在自然杂志上发表的 小世界网络的群体 动力学【3 1 和1 9 9 9 年b a r a b 五s i 和a l b e r t 在 科学杂志上发表的 多亿时，复 杂网络上的动力学起主导地位，这时复杂网络的拓扑结构可以近似认为是固定不变的； 当凡 的尺度内研究复杂网络上动力学行为。事实上，这一方向的研究是复杂的， 因为真实网络上一些特性的表征往往是有不只一种动力学发生在这个网络上。因此，在对 复杂网络上的动力学进行研究时，还要对不同的动力学行为进行演化时间标度分析，从而 简化到复杂网络上只有一种动力学过程。例如在因特网中只考虑病毒的传播、在社会网络 中只考虑o p i n i o n 形成动力学。 最后，值得强调的是，本论文中，对复杂网络拓扑结构及其动力学研究的动因有：一 是复杂网络拓扑结构如何影响发生其上的动力学过程，例如复杂网络的异质性和捷径如何 影响o p i n i o n 动力学的演化；二是复杂网络上的动力学又如何促使我们对复杂网络拓扑结 构的更深刻认识，例如火车运行情况对中国铁路网权重的重定义；三是复杂网络的拓扑结 构及其上的动力学又是如何相互影响的，例如社会系统中社团结构的涌现机制。 5 博士学位论文 d o c t o r a ld i s s e r t a t i o n 1 3 本文纲要 本论文重点研究了复杂网络的拓扑结构对不同的动力学过程的影响，尤其是复杂网络 的异质性和小世界网络上的捷径对o p i n i o n 演化动力学的作用。另外，利用中国铁路网络 上火车运营情况的加权方法对铁路网进行加权。本文每章专注一个研究专题。整体而言， 这些不同的研究专题统属于复杂系统拓扑结构及其动力学的相互作用这一研究方向。 第二章，首先简要回顾图论的基础知识，例如图的基本概念、图的分类，以及图的基 本测量量。然后介绍复杂网络拓扑结构特征，例如小世界特性、无标度特性以及鲁棒性。 最后两节介绍一些真实复杂网络的拓扑结构分析和复杂网络的几个著名模型。 第三章，我们着重对几种真实网络进行实证分析，研究这些网络的分形特性以及对中 国铁路网拓扑结构的分析。利用中国铁路上列车的运行情况对中国铁路网进行加权来弥补 抽象空间( l 空间和p 空间) 中拓扑分析的不足。 第四章，研究了复杂网络上自组织临界动力学行为。在本章前两节中。介绍什么是自 组织临界性以及几个与自组织临界性有关的著名模型。然后，分析研究复杂网络的异质性 对b a k - s n e p p e n 进化动力学模型演化的影响。复杂网络的异质性对临界的平均适应度起到 压低效应。另外，通过分析雪崩指数，把复杂网络可分为随机类、线性类和物理类三类。 第五章，进一步研究了复杂网络异质性对o p i n i o n 演化动力学的影响。首先，简单介 绍社会动力学的研究简史。第二节，介绍社会动力学中几个著名的o p i n i o n 模型。在第三 节中，研究了复杂网络对改进连续o p i n i o n 动力学的影响，以及o p i n i o n 演化过程中分叉现 象的呈现。最后分析了小世界网络和无标度网络i - o p i n i o n 演化到一致态( t h ee o l l s e l l s l l b s t a t e ) 的不同演化过程。 第六章，研究小世界网络的捷径对二态o p i n i o n 演化动力学的影响。其中，重 点研究t o p i n i o n 演化的磁化强度、o p i n i o n o p i n i o n 关联函数，发现o p i n i o n 演化到一 致相不仅与小世界网络的捷径有关，还与复杂网络的维度有关。小世界网络上存 在o p i n i o n - o p i n i o n 长程关联特性，而一维环上没有长程关联特性。小世界网络中的捷径 使得op i l i o n 演化长程关联。最后，分析了o p i n i o n 演化的时间序列分析和有限尺寸效应 分析，发现基于一维环构造的小世界网络上s z n a j d 模型的o p i n i o n 演化相变是赝相变。 第七章，研究了自适应网络上的d e f f u a n t 模型的演化动力学，这是对复杂网络的拓扑 6 博士学位论文 d d c r o r a i ，d i s s 目n - 灯1 0 i n 结构和o p i n i o n 动力学相互作用的研究。重点研究了自适应系统中社团结构的涌现现象， 以便更真实地重构真实的社会系统。研究发现全局重绕连接增强网络o p i n i o n 演化到一致态 的能力，局域重绕连接促使网络社团结构的涌现。 最后，在第八章中，给出本文的小结和今后的工作展望。 7 博士学位论文 d o c t o l 呲d i s s e r t a t i o n 2 复杂网络拓扑结构概述 本章，重点回顾网络拓扑结构的特性以及模型研究。首先，介绍图论的基础知识，包 括图的基本定义、分类以及基本的测量量。这是开展复杂网络研究的基础和数学工具。随 后，回顾几个具有代表性的真实网络的拓扑结构。最后，介绍复杂网络发展中几个著名的 网络模型。 2 1 图论基础知识 图论是应用数学研究的一个分支，它研究的对象是图，研究节点n o d e ，v e r t e x ) 和 边( e d g e ，l i n e ) 组成的图形的数学理论和方法【2 0 】。图论是对复杂网络进行处理研究的基本 框架。4 2 1 1 图的定义 数学上，图是对有相互作用的一个实体集的抽象描述。其中，实体集中一个个相互作 用的实体抽象为节点，而节点之间的相互作用体现在用条线将这两个节点连接起来， 连接节点之间的线称为边。一般而言，一个图可由一个有序偶集g ：= ( k e ) 来表示， 其中子集v = 臼1 ，忱，哪 表示节点集，子集e 是由节点集y 中两个节点饥和的有序 对他，u ，) 组成。有序对( 仇，) 表示图中存在条边从节点仇指向节点，每一个有序对就 是子集e 的元素。因此，称子集e 为图的边集。节点集y 的大小表示图g 的阶，或图的 9 博士学位论文 d o c l d r a l d i s s e k r a t i o n 大小。在图g 的边集e 中，如果节点对他，吩) 和节点对( 叼，仇) 表示同一条边，称此时的 图g 为无向图。反之，称之为有向图。见图2 1 1 ( a ) 和( b ) 。 另外，也可以用一个n 的邻接矩阵a = 【叼) 来描述阶图。其中，n 邻接 矩阵的矩阵元可表示为： f1 ， 叼2 t0 ： ( 仇，吩) e ， ( 优，) ge ( 2 ，1 1 ) 对于无向图，邻接矩阵a 是对称的。这里，不考虑图中的自连接和多重边的情况。自连接 是一条边两端连接的是同一个节点，多重边是两个节点之间存在不止一条边。因此阶图 中存在的最大边数是n ( n 一1 ) 2 ，此时的图称为简单图( s i m p l eg r a p h ) 。如果图中实际存 在的边数可以与最大边数相差不多，称此时的图为密集图。如果图中实际存在的边数限制 在图中节点数的线性关系，称此时的图为稀疏图。 值得关注的是权重图( 如图2 1 i ( c ) ) ，即图中每一条边都附有一个数字值来表征这 条边连接强度，这个数字称为所在边的权重，简称边权。不同的网络中，边权的意义不 同。社会熟人网络中，边权表示两个人的熟悉程度；万维网中，边权表示两个网页之间 超连接的强度。_ 般而言，权重图可以用一个三元集g = ( v e ，w ) 来表示。其中节点 集y 和边集e 在前文中已经阐述。子集w 中任一元素桃f 依附于边池，”，) 上，它表示图中 边池，) 的权重。当图中所有的边权都一样时，把每条边的权重重新标度为l ，不再考虑 权重，从而过渡到无权网络。这时，图的三元表示法可以简化为二元表示法。另一方面， 也可以用邻接矩阵的方法表述权重网络，此时邻接矩阵称为权重矩阵，记为w = f 毗，) 。 其中，元素咄，表示从节点仇到节点的边的权重，毗，= 0 表示不存在从节点饥到节点的 边。在权重网络中，可以研究节点的权重黾= u 、权重分布和权重关联、含权的最短 j e v 路径、权重聚集系数和模块性。 另外，如果图中节点由两种不同性质的节点组成，而图中的每一条边的两端连接的节 点是属于不同性质的节点，这样的图称为二分图。例如图书馆中读者和藏书之间的关系， 如果一名读者借阅了某一本书。那么这名读者和这本书之间存在一条连线表示借阅关系。 当然，一名读者可以借阅多本书，某一本书可以被多名读者借阅。这样，在构建图书馆借 阅关系图时，读者和藏书是两种性质不同的节点，而表示借阅关系的连线就是借阅关系图 1 0 博士学位论文 d o c t o r a ld i s s j 琅1 灯1 0 n w q 垒 ，) 囱w e i 斧g h t e 蜘粼 e m c e s d ) 123 45 谗b 琶 图2 1 1 ：几种常见类型的网络。a ) 无向无权网络，也称简单图：b ) 有向网络；c ) 含 权网络：d ) 二分图及其映射为简单图。 中的边，它的两端分别连着读者和读者所借阅的图书。另一方面，可以把二分图通过关系 映射成两个子图，其中每一个子图中只包含一种性质的节点，如图2 1 1 ( d ) 。图书借阅关 系网络可以映射为读者关系图和图书关系图。在读者关系图中，如果两个读者借阅的书相 同，表明他们之间有着某种意义上的兴趣；而在图书关系图中，如果两本书同时被多个人 借阅，表明这两本书之间存在某种意义上的相同点，例如研究内容或研究方法等。图2 1 1 直观地描述了以上几种不同类型图。 2 1 2 图的基本测量量 l 、节点度、节点度分布和节点度关联 在无向图中，一个节点饥的所有邻居的数目称为节点仇的节点度k i = a i j 如果是 j 有向图，节点的节点度可分为入度( 后讯) 和出度( 后。m ) 一个节点仇的入度定义为图中所 有由其他节点指向节点仇的边数，即七争= a j i ；而出度定义为图中所有由节点耽指向其 歹 他节点的边数，即掣= 那么。节点仉总的节点度为此节点的入度和出度之和， j 即稿= 麓靠+ 垆。把图中节点的节点度排成一列称为该图的节点度序列。 图中最基本的测量量之一就是节点度分布p ( 七) ，它表征在图中随机选取一个节点的节 点度为七的概率。在有向图中，节点度分布又分为入度分布户( 尼机) 和出度分布p ( 彬) 。在 1 1 七 博士学位论文 d o c t o r a ld i s s 】日h 盯i o n 无向图中，可以从节点度分布p ( k ) 或网络中节点度的阶矩来获得图的拓扑信息。图的节 点度的n 阶矩定义为： ( 妒) = 妒p ( 是) ( 2 1 ，2 ) 一阶矩( 七) 是图g 的平均节点度，二阶矩( 七2 ) 描述图g 的连接度分布的涨落。如果 图g 的一阶矩( 七) 不能反映节点度分布的性质，而二阶矩( 七2 ) 具有很大的值或二阶矩在图的 大小趋于无限时发散，称这样的图具有节点度异质性。 节点度分布可以反映无关联图的统计特性。但事实上，许多真实的网络的节点度之 间存在一定的关联性，也就是一个节点度) g k t 拘节点与另一个节点度为的节点相连接 存在一定的概率。这里，可用条件概率来描述网络中节点度之间的关联，记为p ( 砖) p ( k l k ) 表示网络中从节点度为的节点指向节点度为七的节点的边存在的概率，它满足归 一化条件p ( k l k 7 ) = 1 和节点度的平衡条件p ( k l k 7 ) p ( ) = k p ( k i k ) p ( k ) 2 1 ，2 2 。 尽管可以直接利用节点度关联的条件概率p ( 七) 来研究网络的拓扑性质，但这势必会 给结果带来一定的涨落和误差。因此，对网络中任一节点仇，此节点的平均连接度的概念 应运而生，它定义为： ，= 丢轰b = 石1 薹n 叼码 仁， 其中，g 是网络中所有与节点仇相连接的节点组成的子图。更进一步，对于整个网络而 言，可以研究网络中节点度为七的所有节点的平均连接度【2 3 】，记为( 七) ，定义为： 啡，= 斋喜去互b = 专耋丢萎? 仁1 勺 利用节点度关联概率，上式可以写为： k ( 七) = k p ( k i k ) ( 2 1 5 ) 如果网络中不存在节点度的关联，公式( 2 1 5 ) 可以写为( 七) = ( k z ) ( k ) ，即函 数 ) 与变量忌无关。在关联网络中，如果函数k ( 七) 随着自变量k 的增加而增加， 称这样的网络为同配网络；反之，称之为异配网络【2 4 】。月配网络中，节点度大的节点趋 向于与节点度大的节点相连；而异配网络中，节点度大的节点趋向于与节点度小的节点相 1 2 博士学位论文 d o c t o r a ld i s s e r i 1 0 n 2 、最短路径和直径 图中许多全局性质都与节点的可到达性有关。在图中，给定两个节点优和吩，“一j ) 通 道是指从节点优出发，经过一系列相互连接的边和节点，最后到达节点的路径。通道 的长度z 是指通道所经过的边的数目。在通道中，边和节点是可以重复的。如果通道中没 有重复的节点，我们称该通道为路( p a t h ) 。路径长度定义为这条路上边的数目。如果图 中任意两个节点之间都存在路，称此图为连通图。否则，称之为非连通图。网络中，节 点饥和之间的距离奶定义为连接这两个节点的最短路径长度。网络中任意两个节点之间 的距离的最大值定义为网络的直径，记为d ，即 d = m 口 奶)( 2 1 6 ) 因此网络的平均路径长度l 定义为网络中任意两个节点之间距离的平均值【3 】，即 k 晶与蓦奶 ( 2 1 7 ) 其中为网络中节点总数。网络的平均路径长度也称为网络的特征路径长度( t h e c h a r a c t e r i s t i cp a t hl e n g t h ) 。 在公式( 2 1 7 ) 的定义中存在一个问题，即当网络是非连通网络时，平均路径长度l 就 会发散。为了解决这个问题，一方面，可以把公式( 2 1 7 ) 仅仅利用在网络中最大的连通部 分上；另一方面，l a t o r a 和m a r c h i o r i 提出了一种称之为网络效率的测量量 2 s ，2 6 】： e 2 赤幻6 n , i 匀去 ( 2 1 8 ) 公式( 2 1 8 ) 反映了网络的传输效率，同时避免了公式( 2 1 7 ) e e 定义的发散性。因为非连通 网络中属于不同连通部分的节点对在公式( 2 1 8 ) 中的贡献为零。 3 、聚集系数( c l u s t e r i n gc o e f f i c i e n t ) 聚集系数，又称可递性( t r a n s i t i v i t y ) ，是熟人关系网络中一个基本的特征量。它反 映了两个拥有共同朋友的个体还是朋友的概率【2 7 ，2 8 】。在一般的网络中，聚集系数反映了 网络9 - 角构型( 即网络中三个节点之间彼此相连的构型) 出现的强度。网络的聚集系数 可以定义为网络上节点三元组中含有的三角构型的相对数目 8 ，2 9 ，3 0 ，即： g = 禚糕墓裂辫 仁加， u 2 两孬葡琵舌冠磊孺百 b l 圳 1 3 博士学位论文 d o ( t o r a ld i s s e r t a t i o n 其中节点三元组是指包含三个节点，并且这三个节点中至少存在两条边的构型，其中，我 们称之为节点度为二的节点的三元组，另外，网络中一个三角构型包含三个节点三元组， 如图2 ，l ，2 。 1 囝 ， 囝3 图2 1 2 ：关于聚集系数定义的说明。按照公式( 2 1 9 ) ，这个网络具有一个三角构型和八 个节点三元组，因此网络的聚集系数为学= 3 8 。其中节点l 、2 、3 和连接它们的两条虚 线组成一个节点三元组，称之为节点2 的一个三元组。按公式( 2 1 1 0 ) ，单个节点的聚集 系数从左到右分别为l 、l 、1 1 6 、0 和o ，因此网络的平均聚集系数利用公式( 2 1 1 1 ) 计 算为c = 茆1 3 。 另外种计算网络聚集系数的方法是w a t t s 和s t r o g a t z 提出来的。此时，网络中某一 节点优的局域聚集系数概念也首次被提出来。节点仇的局域聚集系数定义为节点仇的子 图中实际存在的边数( 记为色) 与子图g 中可能存在的最大边数( 记为限一1 ) 2 ，其 中乜为节点执的节点度，也是子图g 中节点个数) 之比【3 ，2 7 】，即 q ：莉2 e i ：甓； ( 2 u 。) q 。莉21 丽j 厂 【2 1 1 0 ) 对于节点度为。和1 的节点，在公式( 2 1 1 0 ) 中分子和分母都为零，定义这样节点的局域 聚集系数为o 。关于计算聚集系数的快速方法见参考文献( 3 l l 。进而，整个网络的聚集系数 可定义为： g = 专龟 ( 2 1 1 1 ) 根据定义，可知0sc - 4 1 ；t i o cs1 。公式( 2 1 9 ) 和公式( 2 1 1 1 ) 的不同点见参考 文献( 【8 ，2 6 】) 另外，可以研究网络中聚集系数与节点度之间关系，记为c ( 七) 。有时， 称4 k ) 为网络的聚集