（系统工程专业论文）基于复杂网络的信息传播.pdf

摘要 复杂网络被普遍认为是刻画自然界和社会系统的一个全新而有力的工具，与 其相关的研究和应用，已经广泛渗透到系统科学、社会、经济、管理、工程技术 等领域。复杂网络的错综复杂，源于其大量的节点、连边，以及它们之间的非线 性关系，进而节点和连边等要素拥有自身复杂的状态和更新策略；若是动态网络 还要涉及规模的增长乃至网络拓扑结构的变化，以及结构对功能的影响。复杂网 络的复杂，有助于我们理解复杂科学和复杂系统的复杂，从而能够研究和应对这 类复杂。 本文讨论了复杂网络的经典理论以及近年发展起来的极具代表性的复杂网 络模型小世界网络模型和无标度网络模型。在此基础上，构建了一个意见交 互模型和一个话题传播模型，用以研究系统中普遍存在的传播现象，从而总结出 传播规律及影响系统效率和均衡的主要因素，进而可以预测事件走向，同时为限 制或者促成思想的传播提供了理论支持。 在意见交互模型中，综合分析临界沟通难度阈值对交互均衡的影响，研究了 小世界网络中网络结构对网络效率的作用，归纳得出加入少量长程边的网络的传 播效率远大于仅具有短程边的网络，尽管长程边的效用也是边际递减的。 在基于无标度网络的话题传播模型中，通过分析话题有趣度、个体关注他人 程度等对于话题传播的影响，归纳得出最终参与讨论的人数与话题的重要性和有 趣度成正相关，个体关注他人程度越高越有助于话题讨论时群体策略一致性的达 成。 关键词：复杂系统：复杂网络；传播动力学 a b s t r a c t g e n e r a l l y , t h ec o m p l e xn e t w o r kh a sa l r e a d yb e e nr e g a r d e da sab r a n d n e wa n d p o w e r f u lt o o lw h i c hp o r t r a y st h en a t u r ea n ds o c i a ls y s t e mw e l la n dh a sp o t e n t i a l a p p l i c a t i o n si ns c i e n t i f i cr e s e a r c h , s u c ha ss y s t e m ss c i e n c e ，s o c i o l o g y , e c o n o m i c s ， m a n a g e m e n t ，e n g i n e e r i n gt e c h n o l o g y , a n ds oo n t h ec o m p l e xn e t w o r k sc o m p l e x i t y s t e m sf r o mi t sm a s s i v en o d e sa n de d g e s ，a sw e l la st h en o n l i n e a rr e l a t i o n s h i pb e t w e e n t h e m ，s ot h en o d e sa n de d g e sh a v et h e i ro w nc o m p l e xs t a t u sa n dr e n e w a ls t r a t e g y c o n t i n u a l l y f u r t h e r m o r e ，ad y n a m i cn e t w o r kh a se v e nm o r ec o m p l e x i t ys u c ha ss c a l e e x p a n s i o n ，t o p o l o g yc h a n g i n g , a n ds t r u c t u r e si n f l u e n c et of u n c t i o n t h er e s e a r c ho n c o m p l e xn e t w o r ki sh e l p f u l i nu n d e r s t a n d i n gc o m p l e xs c i e n c ea n dc o m p l i c a t e d s y s t e m s t h ef i r s tp a r to ft h i sa r t i c l ei n t r o d u c e st h ec l a s s i c a lt h e o r yo fc o m p l e xn e t w o r k ， a n dt h em o s tr e p r e s e n t a t i v ec o m p l e xn e t w o r km o d e l ，t h es m a l l w o r l dn e t w o r ka n dt h e s c a l e - f r e en e t w o r k t h e n ，b a s e do nt h ec o n s t r u c t i o no fa i lo p i n i o ni n t e r a c t i v em o d e l a n dat o p i cd i f f u s i o nm o d e ls e p a r a t e l y , t h i sa r t i c l es t u d i e st h eu n i v e r s a le x i s t e n c e d i s s e m i n a t i o np h e n o m e n o nf r o mw h i c ht h ed i f f u s i o nr u l ea n dt h ep r i m a r yi n f l u e n t i a l f a c t o r so fs y s t e me f f i c i e n c ya n db a l a n c ea r es u m m a r i z e d ，a n dt h ep o s s i b l ew a yt o f o r e c a s tt h ee v e n tt r e n d ，l i m i to rf a c i l i t a t et h es p r e a d i n go ft h o u g h t ，i sg i v e n t h eo p i n i o ni n t e r a c t i v em o d e la n a l y z e st h ec r i t i c a lc o m m u n i c a t i o nd i f f i c u l t y t h r e s h o l dv a l u ef i r s t ，a n dt h e ns t u d i e st h ei n f l u e n c eo fa r c h i t e c t u r et oe f f i c i e n c yi nt h e s e r i e ss m a l l w o r l dn e t w o r k w ef i n dt h a tt h ee f f i c i e n c yt h a to n l yd e p e n d si nt h es h o r t e d g e si s f a ri n f e r i o rt ot h a to ft h ed i s t a n te d g e s ，a l t h o u g ht h ed i s t a n te d g e sa r e d i m i n i s h i n gm a r g i n a lu t i l i t ya l s o t h et o p i cd i f f u s i o nm o d e li nt h es c a l e f r e en e t w o r ka n a l y z e sh o wt h ei n t e r e s to f t h et o p i c ，t h ei n d i v i d u a l sa t t e n t i o nl e v e lt oo t h e rp e o p l ea n ds oo n ，a f f e c tt h et o p i c d i s s e m i n a t i o n a si st h ec a s e ，t h em o r ei m p o r t a n ta n dm o r ei n t e r e s t i n gt h et o p i ci s ，t h e m o r ep a r t i c i p a t o r sj o i nd i s c u s s i o nf i n a l l y c a r i n ga b o u to t h e r s v i e w sw i l lb o o s tt h e t o p i cd i s c u s s i o nw i t hc o m m u n i t ys t r a t e g yu n i f o r ma g r e e m e n t k e yw o r d s ：c o m p l e xs y s t e m ；c o m p l e xn e t w o r k ；t r a n s m i s s i o nd y n a m i c s 厦门大学学位论文原创性声明 兹呈交的学位论文，是本人在导师指导下独立完成的研究成 果。本人在论文写作中参考的其他个人或集体的研究成果，均在 文中以明确方式标明。本人依法享有和承担由此论文产生的权利 和责任。 声明人( 签名) ：荔s 荔韬 子年 月弓e l 厦门大学学位论文著作权使用声明 本人完全了解厦f - j 3 v 学有关保留、使用学位论文的规定。厦 门大学有权保留并向国家主管部门或其指定机构送交论文的纸 质版和电子版，有权将学位论文用于非赢利目的的少量复制并允 许论文进入学校图书馆被查阅，有权将学位论文的内容编入有关 数据库进行检索，有权将学位论文的标题和摘要汇编出版。保密 的学位论文在解密后适用本规定。 本学位论文属于 1 、保密() ，在年解密后适用本授权书。 2 、不保密( ) ( 请在以上相应括号内打“ ) 日期：硝年臼3 日 日期：沙矿年易月弓日 第一章绪论 第一章绪论 系统是由相互作用和相互依赖的若干组成部分( 要素) 结合而成，具有特定 功能、结构、环境的有机整体。系统具有整体性、集合性、层次性、相关性、目 的性、环境适应性。复杂系统是组元之间相互作用的非线性性不可忽略，系统运 行机制不明晰，一般带有不确定性。通常这些非线性相互作用能够使复杂系统作 为一个统一的整体进行自组织演化，从而获得组元独自无法获得的集体行为和特 征。 随着上世纪七八十年代自组织理论和非线性科学的蓬勃发展，复杂系统和复 杂性科学的研究掀起了一个浪潮【1 。8 1 ，这对人们原先的还原论的认识带来革命性 的新思潮。著名科学家h a w k i n g 认为：二十一世纪是复杂性科学的世纪。复杂网 络的动力学特性研究，将对当前国际上关注的多智能体( m u l t i a g e n t ) 协作、群 体行为( c o l l e c t i v eb e h a v i o r ) 控制等热点问题，带来新的视角和方法。总之，复 杂网络可作为研究复杂系统、复杂性科学一个可行的切入点【9 1 6 1 ，并将会在生态 演化、神经网络、群体智能、认知科学、自组织涌现行为、网络化系统、经济动 力学等方面的研究中彰显重要作用。 1 1 复杂网络概述 系统工程是以大规模复杂系统( 特别是管理系统) 为研究对象，在系统理论、 管理科学及运筹学等学科基础上形成的- f 7 交叉学科。系统工程在研究复杂系统 结构和功能的基础上产生了复杂网络这样一个有力的工具，网络不但可以表现许 多复杂系统的结构形态，还可以反映系统的动力学特性。当系统中元素，在某类 事件中表现出一定的同质性，则可以使用网络的方法来研究系统在该类事件下的 性质和演化，如传染性疾病、信息的传播。作为系统，其结构可以抽象为网络， 各类作用体抽象为网络结点，各种相互作用抽象为结点之间的边。这样，就可以 运用图论和网络分析的理论、方法及工具进行系统结构的拓扑特性研究。近年来 关于复杂网络的研究受到统计物理学、系统科学、社会科学和工程领域研究人员 的广泛关注，已经成为他们的一个研究热点。 自然界中存在的大量复杂系统都可以通过形形色色的网络加以描述。一个典 型的网络是由许多节点与连接两个节点之间的些连线组成的，然而并非节点间 有任意关系就有连边，往往是根据具体问题，两个节点之间具有某种特定的关系 基于复杂网络的信息传播 才连一条边，反之则不连边，有边相连的两个节点在网络中被看作是相邻的。实 际上，正是因为现实世界中很多复杂系统都可以用复杂网络来建模，复杂网络的 研究才有其实际背景。例如，i n t e r a c t 是路由器等各种各样的终端组成的复杂网 络；万维网( w 6 r l dw i d ew e b ) 是由网页组成的复杂网络；大脑是由神经元组成 的复杂网络；一个社会关系网络是由个人、组织甚至国家组成的复杂网络。此外 常见的复杂网络还有通信网络、电网、物种之间的捕食网、蛋白质问交互组成的 网络、v l s i 电路与系统( 节点是电子元件，边是它们之间的线路) 、公路网、铁 路网、航空网、科研合作网( 节点是研究者，边是研究者合作的指标) 、论文之 间的引用关系网等。 构建了网络之后，即可研究复杂网络上面的动力学现象，如在社会关系网络 上讨论舆论的传播，接触关系网络上讨论传染病的传播，计算机病毒在i n t e r n e t 网络或邮件网络上的传播，在引文网络上研究新思想的提出与传播，在科学家网 络上研究科学家之间的相互影响，电网的级联崩溃事故，城市务工人员的流动等。 网络与现象结合还可以用来讨论网络的稳定性等结构与功能关系。例如，在食物 链网络上讨论个别或部分物种灭绝对整体生态系统的影响；致死性传染病传播的 过程中对网络拓扑的改变，如欧洲中世纪的黑死病；网络路由在中间结点损毁时 能够智能调整路径；在科学家网络中讨论某个领域中不同的科学家对网络演化的 影响：在级联崩溃等激烈的动力学过程中，我们可以更加明显地观察到系统在达 成功能的过程中，结构的自适应变化。此外，网络本身的演化过程也是一个有趣 的问题，例如i n t e m e t 网络的形成被认为是无限定原则的，但是它却展现了一些 重要而普适的结构特征与稳定性；再如，对于某学科内的引文网络与科学家网络 的演化机制的研究，有可能给出促进科学发展的新方案和模式【1 7 q 8 1 。这些复杂网 络问题都与人们的生活息息相关，比如2 0 0 0 年4 月4 日“爱虫”电脑病毒在i n t e m e t 上迅速蔓延造成的损失高达数亿美元：2 0 0 3 年8 月1 4 日发生的北美电网级联崩 溃导致的大停电，事故波及美国和加拿大两国，超过5 0 0 0 万的人口，并造成经 济损失约3 0 0 亿美元。专家认为，如果恐怖分子有效袭击美国电网，连锁反应的 后果可能比撞毁世贸中心更严重。 数学家和物理学家在考虑网络的时候，往往只关心节点之间有没有边相连， 至于节点到底在什么位置，边是长还是短，是弯曲还是平直，二维表现时有没有 2 第一章绪论 相交等等都是他们不在意的。在此，我们把网络不依赖于节点的具体位置和边的 具体形态就能表现出来的性质叫做网络的拓扑性质，其相应的结构叫做网络的拓 扑结构。什么样的拓扑结构比较适合用来描述真实的系统呢? 两百多年来，对这 个问题的研究经历了三个阶段。欧拉对“七桥问题的证明是图论研究的开始。 在随后的近两百年间，科学家们对现实网络系统的研究，局限于使用图论研究规 则网络或是结点个数比较少的小结构网络，例如二维平面上的欧几里德格网，或 者最近邻一维链。 到了2 0 世纪5 0 年代末6 0 年代初，两位匈牙利数学家p a u le r d 6 s 和a l f i d d r d n y i 在图论领域做出了一个重要突破，即在文献 1 9 2 1 中提出的随机图理论。 他们用随机图来描述网络的拓扑结构，这为复杂网络的研究奠定了一个数学理论 基础。随机网络的概念在接下来的4 0 年里一直主导着人们对现实世界的理解和 思维，直到今天仍有人在做这方面的研究。但随机图理论是否能准确地描述现实 世界中所有的网络呢? 通过大量的观察，我们可以得知：现实世界中绝大多数的 网络既非完全规则亦非完全随机。例如，两个人是否是朋友，i n t c m c t 中两个路 由器之间是否有光纤连接，w w w 上两个页面之间是否有超链接等都不会是完全 确定或是完全靠抛硬币可决定的。e r 随机图理论虽然不能准确地描述现实世界 中的网络，但却能统治这个领域这么多年，主要还是由于过去我们缺乏对现实世 界中网络数据的分析能力和对现实世界网络拓扑结构的准确认识。 近年来，事情发生了变化，由于科学技术领域特别是i t 领域的高速发展， 使我们获得的可供我们刻画现实世界网络特征的数据越来越多，加之超级计算机 的发展为我们提供了强大的计算和数据分析能力，以及各个学科之间的相互交叉 和融合趋势在不断加强，使得人们有能力在对各种不同类型网络的数据分析的基 础上，揭示复杂动力网络的一些共有特征和性质，从而激发起了人们以理论、仿 真和实际数据验证三种手段研究复杂网络的浓厚兴趣。以此为契机，经过大家在 这一研究方向上不懈的探索和努力，最近在复杂网络研究领域中取得了两项重要 的发现：大多数复杂网络都具有小世界( s m a l l w o r l d ) 和无标度( s c a l e - f r e e ) 特 性。 1 9 9 8 年6 月，美国康奈尔大学理论与应用力学系的博士生w a t t s 及其导师一 一非线性动力学专家s t r o g a t z 教授在n a t u r e 杂志上发表的题为“小世界 网络 基于复杂网络的信息传播 的集体动力学的文章【1 7 】描述了从规则格子到随机图之间的转变，提出了小世界 网络的概念。小世界的概念从字面上的意思是说尽管网络很大，但通常在网络的 任意两个节点间都有一条相对于网络规模来讲是很短的路径。我们可能经常遇到 这样的情形，当你和一个新朋友聊天的时候，发现你们有共同的好朋友( 他是你 朋友的朋友) ，于是双方都会发出“世界真小 这样的惊叹后面我们将介绍 这是因为现实的网络往往有很高的集聚系数。 1 9 9 9 年l o 月美国n o t r ed a m e 大学物理系的b a r a b d s i 教授及其博士生a l b e r t 在s c i e n c e 杂志上发表的题为随机网络中标度的涌现的文章【i8 】介绍了另一项 重要的发现。b a r a b d s i 和a l b e r t 开展一项描绘万维网的研究，他们原本以为会发 现一个随机网络的钟形图，但统计分析的结果令他们意外地发现：万维网基本上 是由少数高连通性的页面串连起来的，8 0 以上页面的连接数不到4 个，而占节 点总数不到万分之一的极少数节点，却和1 0 0 0 个以上的节点连接。随机网络具 有的有特征意义的多数节点大致相同的连接数“平均度值 不见了。于是他 们把这种网络称为“无标度网络( s c a l e f l e en e t w o r k ) 。他们在计算恰好拥有k 个连接的万维网页面的数目时，发现网页的度值分布呈现一种幂指数 ( p o w e r - l a w ) 分布率，即：任何节点与其他k 个节点相连接的概率正比于k “( 也 就是p ( k ) k “) ，直观地有度分布的函数曲线在双对数坐标系下是一条下降的直 线。经更多的实证研究发现，大量复杂系统，诸如互联网、科学家合作网络、新 陈代谢网络以及好莱坞演员合演网络，都存在这种少数但高连通的节点，遵循“幂 次定律( p o w e r - l a w ) 。这种节点可称为“集散节点( h u b ) ”。许多不同的复杂系 统，其网络结构都是无标度网络，都是由少数集散节点主控的系统。 虽然目前复杂网络研究如此火热，科学家们还没有给出复杂网络精确严格的 定义，从这几年的研究来看，之所以称其为复杂网络，大致上包含以下几层意思： 首先，它是大量真实复杂系统的拓扑抽象；其次，复杂网络至少在感觉上比规则 网络和随机网络复杂，它介于完全规则和完全随机之间，为了生成完全符合真实 统计特征的网络科研工作者不断提出更适合研究的复杂网络，并且这个过程还在 继续：最后，由于复杂网络是大量复杂系统得以存在的拓扑基础，因此对它的研 究被认为有助于理解复杂系统的复杂性。 尽管近年来提出了许多刻画和度量网络的概念，但其中有三个概念发挥了重 4 第一章绪论 要作用，它们是：度分布、平均路径长度和集聚系数。事实上最初w a t t s 和s t r o g a t z 就是试图构造一种具有小的平均路径长度( 与随机网络类似) 和较大的集聚系数 ( 与规则网络类似) 的网络，循此途径最后得到了小世界网络模型。无标度网络 的发现是由于观察到许多大规模网络的节点的度呈现一种幂指数分布率。因此， 这三个概念在复杂网络的奠基性研究中起到了至关重要的作用，并且在后来的复 杂网络研究中也扮演了重要的角色。 1 2 复杂网络的研究方向和意义 近年来，关于复杂网络的研究正处于蓬勃发展的阶段，其研究者来自图论、 系统工程、统计物理学、通信网络、生态学、社会学以及经济学等各个不同领域， 不同领域的研究者们在不同的方向上展开了研究工作，开辟了一些复杂网络的研 究方向。相信随着今后研究的进一步开展，复杂网络会有更多更重要的研究领域 被开辟出来。 就目前而言，复杂网络的研究至少包含了以下几个方向： a ) 对复杂网络特性进行更深入和广泛的实证研究。 这一课题应可视为复杂网络研究中最基础的一步，采用表征网络系统结构和 行为的统计参量来描述现实网络，对样本数据进行实际测量，从而揭示现实网络 的统计属性。事实上，正是通过分析现实世界中网络数据得出它们的共性，才有 了小世界网络和无标度网络的提出。对更多的实际复杂网络数据的分析可以发现 其新的共性，借此来构建新的更符合实际的网络模型。很多研究者相继对各个不 同领域的网络进行了研究和分析，如互联网，e m a i l 网络，电话呼叫网络，电 影演员合作网络等等。 b ) 复杂网络结构及演化机理的研究。 人们在研究实际网络的过程中，常常发现一些网络具有相似的特征，比如很 多实际网络的度分布都遵从幂律( p o w e r 1 a w ) 分布、并且有大集聚系数小平均 路径长度等等。于是为了研究的方便，根据实际网络的共有特征，构建能够帮助 理解统计属性的网络模型，使得模型化后的网络具备实际网络的某类或某几类特 征，从而解释网络结构的成因，揭示决定网络演化的主要因素。除了最初提出的 w a t t z s t r o g a t z 小世界网络模型和b a r a b d s i a l b e r t 无标度网络模型之外，研究者 相继又提出了其它一系列网络模型。 基于复杂网络的信息传播 例如，在文献 3 1 ，3 2 中作者提出并研究了确定性的小世界网络模型；文献 3 3 - 3 7 对b a 无标度网络模型进行了改进和推广，提出了各种各样的无标度网络 模型：文献 3 8 - 4 4 提出了带有群落性网络拓扑结构( c o m m u n i t ys t r u c t u r e ) 的复 杂网络模型：文献 4 5 4 8 依据实际复杂网络的生长机制提出了种种加权复杂网络 ( w e i g h t e dn e t w o r k ) 模型，这些模型能够很好的刻画实际网络中的三种幂律分 布。 c ) 复杂网络上的动力学过程和动力学特性。 通过把复杂网络看成动力系统或在复杂网络中引入动力学单元，许多研究者 对复杂网络的动力学行为展开了研究，进一步理解网络拓扑结构对网络上的物理 过程( 比如病毒传播、网络导航、拥塞、同步等) 的影响，测算性质涌现的临界， 预测网络系统的行为。如分析复杂动态网络的同步问题，探讨随机去点与选择性 攻击时网络的容错性与抗攻击性问题，研究复杂网络的控制问题。此外，一些与 实际网络结合十分紧密的动力学过程近几年也开始被广泛的研究。譬如，万维网 与社会网络的搜索与导航，社会网络和计算机网络中的病毒传播与流行，电力网 络上的大停电事故。在复杂网络动力学性质的研究中，网络的拓扑结构怎样影响 网络的动力学性质是一个非常有趣的问题，也是一个研究的热点。随着网络拓扑 结构的改变，一些有趣的现象会逐渐涌现，如在规则一维链中随机重连边，会逐 渐出现小世界现象，继续重连又会逐渐变成完全随机图。由均质的随机网络到异 质的无标度网络，网络容错能力逐渐增强，但是抗攻击性迅速减弱，这是因为随 机网络是不存在集散节点的，对随机网络的攻击与随机网络自身随机出错是无差 别的，一般来说不能造成致命性的伤害，但是对于无标度网络，攻击它的集散节 点可以使网络很快分崩离析。s a r s 的传播与防控，使我们进一步看到了无标度 网络的容错性和脆弱性研究所具有的重要实际价值。 复杂系统和复杂网络要充分重视学科的交叉和横跨研究，a l b a r a b o s i 是物 理学家，他发表的长文“s t a t i s t i c a lm e c h a n i c so f c o m p l e xn e t w o r k 【i l ，全面总结 了复杂网络的已有研究成果，高屋建瓴，启迪我们运用统计物理成熟的观念、理 论和方法，以及一切可以运用的数学成果，并把生物系统、社会经济系统和物理 系统联系起来进行观察分析，从网络的拓扑特性方面寻找它们的共性。 以系统结构的拓扑特性网络为切入点，展开研究系统学层次的系统结构 6 第一章绪论 理论，必须遵循从个性到共性的认识规律。从具体系统的网络分析入手，又适时 地抽象出共性，再考虑这些共性对其它领域的普适程度。这方面a l b a r a b i s i 也为我们提供了经验。根据他发表成果的时间表可知，他是从研究万维网起始的， 逐次扩展至互联网、演员合作网，科学合作网，基因蛋白质相互作用网等等，在 这个延展的过程中，不断反复地提炼共性，建立模型进行理论分析。钱学森曾指 出，要建立开放的复杂巨系统一般理论，必须从一个一个具体的开放的复杂巨系 统入手，只有这些研究成果多了，才能从中提炼出一般的开放的复杂巨系统理论。 同样的，从系统学的高度研究系统结构的拓扑特性也必然要经过这条道路。我们 应该意识到这样一个大好趋势，即各学科都在兴起对本学科的对象系统进行网络 分析的研究。这实质上已经把各门具体学科的研究从一个方面，即以同一范式一 一节点、连接和网络进行研究，这已是从很高的层次，进行从定性到定量的共性 提炼了。因此，从系统科学这一角度来说，首先要特别重视各学科领域的网络分 析成果，同时注意从系统科学方面进行整合研究。 系统理论在基本概念、理论和方法等方面均已取得了许多重要成果，譬如 s i m o n 关于层次结构的研究，普里高津关于耗散结构的研究，钱学森等关于开放 的复杂巨系统的研究等重要成果。我们相信，把这些成果融会进复杂网络结构和 动力学特征的研究，双向互动，在两方面都会有新的进展。 总体来说，由于复杂网络的研究尚处于起步阶段，对复杂网络理论应用的研 究相对来讲还比较少，但迄今己发现了很多潜在的有趣应用。例如，上述对复杂 网络鲁棒性的研究成果可以应用到网络拓扑设计中去，对网络同步问题的研究有 望在通信领域中发挥作用，对网络搜索和导航问题的研究可能在通信及计算机网 络等的路由问题中有应用前景同时对设计更加有效的搜索引擎也有可能起到关 键作用，对病毒传播网的研究在预防和控制传染病与计算机病毒方面有重要的指 导意义。著名的生物学家m i n o r uk a n e h i s a 亦在其近著后基因组信息学中提 出以复杂网络作为研究后基因组信息学的总体思路，他在书中列了一个表如 表1 1 所示，并写了占全书正文五分之一的总括性的最后一章“分子相互作用的 网络分析 。此外，最近在文献 3 0 中作者提出了把无标度网络模型应用到纠错 编码当中，如果和现在比较热门的研究领域网络编码结合起来可能会有重要的成 果出现。可以预见，随着复杂网络领域研究成果的不断涌现，对这些成果的应用 7 基于复杂网络的信息传播 也将成为今后研究的一个主要方向。 表1 - 1 生命科学中的网络 系统节点边 蛋白质三维结构原子原子相互作用 生物体分子 分子相互作用 脑 细胞细胞相互作用 生态系统生物体生物体相互作用 文明人社会关系相互作用 复杂网络的研究在很多学科有重要意义，包括电路与系统、复杂性科学、非 线性科学、计算机科学、控制理论、生物等等，这是由于复杂网络广泛的存在于 自然界和社会之中。因此，复杂网络的研究工作对我们进一步认识自然界和社会 的现象有着至关重要的意义。我们可以利用复杂网络的己有研究成果，更深刻的 认识自然界和社会的复杂性，进而我们可以设计出具有更好特性的复杂网络或者 使网络处在有利于我们的状态。研究复杂网络的重要意义还在于让人们正确认识 和防范系统灾害。实际生活中很多网络都不可避免地遭受侵害：电力网上发生的 连锁故障可能会导致大停电事故，给生产和生活带来严重的损失；i n t e m e t 上发 生的信息拥塞可能会使信息传输不顺畅，致使人们交流产生困难；计算机网络上 的病毒传播则会严重影响人们使用计算机进行日常工作；此外，人群网络上传染 病的传播也会影响到人们的健康。事实上，我们可以将复杂网络理论应用到其中 来解决问题，譬如可以根据复杂网络理论设计具有更好性质的网络拓扑；可以根 据复杂网络理论进行拥塞控制，改善网络的传播效率；可以根据复杂网络理论对 i n t e m c t 上计算机病毒和人群网络中传染病病毒的传播进行控制，抑制病毒的传 播。 1 3 本文的研究方法和内容安排 复杂网络是系统工程一个极有用的成果，以复杂网络的拓扑特性研究为切入 点，深入开展系统结构与功能的研究。系统结构是系统科学的基本概念，暂不谈 哲学和数学，就系统学层面来说，其内涵迄今还没有丰满的阐述。结构是客观事 8 第一章绪论 物的基本属性，也是各学科领域的基本问题，如物质科学研究物质的结构和性质， 生命科学和社会科学研究事物的结构和功能。可以说，每门学科对其研究对象的 结构，都有非常丰富的具体成果；但从系统学的高度，横跨物质系统、生物系统 和社会经济系统的具体研究成果，也就是系统学层面的成果还不多。如上所述， 系统结构可以描述成网络结构，但原来研究网络结构的规则图和随机网络理论只 反映了众多系统上两头的极端情况。大多数复杂系统既非完全规则也非完全随 机，是规则和随机伴行的，是动态演化和开放自组织的。单纯运用规则图和随机 网络理论对普遍存在的这些复杂系统不能进行实质性的分析研究，小世界网络和 无标度网络的发现，为我们打开了新的视野。 每一个复杂网络都有其自身的特殊性质、独特现象及演化机制，但是由于都 可以使用网络分析的方法，所以也存在着共性。例如，关于簇系数、顶点度值分 布对网络结构的影响及其分析方法，以及大量不同网络中存在的相同的统计特 征，不同的无标度网络对于随机去点与选择性攻击都表现出容错性和脆弱性。这 些来自不同领域的大规模系统呈现出共同的普适规律，促使人们去探索隐藏在这 些表象后面的内在演化机制，掀起了研究复杂网络的热潮。目前复杂网络的研究 主要包括三个方面的内容：复杂网络的静态拓扑结构，复杂网络的演化机制，和 复杂网络的动力学性质。 复杂网络的静态拓扑结构是指网络的拓扑结构不随时间变化，研究的主要内 容包括度分布、集聚系数、平均路径长度、介数等等。复杂网络的演化是指网络 的拓扑结构随时间的演化，目前的研究还是基于增长和偏好连接的无标度网络模 型。复杂网络上的动力学研究本质上是探讨网络结构与功能关系，这是复杂网络 的研究重点。目前人们积极致力于复杂网络上传统统计模型的动力学研究，如复 杂网络上的渗流【4 9 】，流行病传播【5 0 5 2 1 ，i s i n g 模型【5 3 - 5 4 1 ，随机行走 5 5 击2 1 等。研究 表明，复杂网络上的这些动力学性质与规则网络、随机网络上相应的动力学性质 有明显的不同，复杂网络上的这些特殊动力学性质是由复杂网络的特殊拓扑结构 所决定的。静态特性表征系统结构，动态特性表征系统功能，实际上，系统的结 构与系统的功能是密不可分的，结构影响功能，功能反作用于结构。只有将二者 结合起来研究，才能揭开复杂系统的真正面纱。把系统结构、功能与具体系统结 合起来是复杂网络研究的中心内容，分析复杂网络特性主要有以下三种方法： 9 基于复杂网络的信息传播 a ) 实证研究方法。对于复杂网络这样的研究方向，应该把实证研究放在第一 位，充分运用调查统计的手段和当今国际上已有的各种数据库，并结合强大的计 算机处理数据和计算的能力，寻找出各种复杂系统结构的拓扑特性。w w w 遵循 “幂次定律是b a r a b d s i 等人在研究万维网页面的时候发现的，幂次定律中 p ( k ) - k 7 中的y 值，通常介于2 3 之间，也是经过大量的实证研究发现的。就系 统科学来说，只有在大量的实证性成果的基础上，进行建模和理论分析，才有实 质性的意义。 b ) 解析研究方法。运用图论和网络分析的理论、方法和工具进行系统结构的 拓扑特性和系统功能的研究。主要包括连续性方法，主方程方法，变化率方程方 法等。由于复杂系统既不完全规则又不完全随机，所以完全解析的数学方法还很 不成熟，只能研究复杂系统里部分层面的问题。尤其是连续性的解析分析方法， 由于网络自身的离散性，故要求网络规模“足够大 ，大量有意义的结果要求网 络节点数在连续3 次求取常用对数后还要比1 0 大，在目前科学观察得到的宇宙 中，还没有任何一个有物理意义的数值达到如此的数量级。 c ) 数值模拟分析方法。这是目前最主要，也是用得最广泛的方法。数值模拟 不需要形成很精确的数学公式，或者使用很复杂的推导求解方法，只是根据系统 元素和它们的交互行为设计出计算机程序，然后运行以观测所模拟的系统的演化 情况。当然，数值仿真对于很多现实系统还是具有一定的解释和预测能力的，尤 其对于特定问题，即便无法提出解析方法也可以使用数值模拟，然后再回到实际 系统求证与校正。数值仿真的方法在某种程度上和实证研究有异曲同工之妙，通 过多次的仿真，可能猜测出一般性的通用命题，进而再想办法论证之。理论进步 反过来又可以指导与促进数值仿真，两者互相推动。毋庸置疑的是，对于终极解 析理论的追逐是无止境的，任何理论在数据的检验下都有可能具备改进的空间一 一哪怕是精确的牛顿运动定律，最终也被论证成为相对论在低速时的特例。 网络的研究从欧拉的经典图论，转变到数学领域的随机网络，乃至现代意义 上的复杂网络，正是一步步从纯学术向理论联系实际迈进，人们对于复杂网络所 能表现的复杂系统特性越来越感兴趣，从物理学到信息学的众多学科均加入到了 复杂网络的研究当中。 网络的节点是网络结构和功能的基础，例如信息的传播要通过一个个载体的 1 0 第一章绪论 接收与发送，传染病亦如是，公交网络中的节点也是实现其重要功能的车站，社 会网络中人或组织等个体也是网络的基础。当然，连线表达了节点之间的交互， 往往还表征网络的效率、稳定性等重要课题。如何在固有的基础之上优化网络的 传输效率或者抑制不良信息的传播是本文主要讨论的重点。 复杂网络是由成千上万个节点组成，从而使得网络行为具有统计特性，也由 于节点众多，我们往往关心统计特性多于关心每个节点的细部特性，这样就能化 复杂问题为相对简单的问题，本文正是利用统计值讨论了复杂系统中意见的交互 和话题的传播。当然，对复杂系统与复杂网络的研究毕竟才刚开始起步，还有很 多问题有待我们去研究和探索。 本文分为五章。第一章为绪言，介绍复杂系统与复杂网络的背景，研究方向 及其意义，说明了该课题的分析方法及主要内容。第二章是本文的概念定义和理 论基础，是复杂网络研究的基石，使得本文的研究能够高屋建瓴。第三章和第四 章是本文主要的研究工作，第三章研究的是复杂网络动力学中举足轻重的传播动 力学，构建了一个意见交互模型进行仿真，讨论了传播的条件，网络结构对传播 效率的影响；第四章研究的是复杂网络的演化动力学，即错综复杂的系统，其状 态更新以及更新策略在随机的基础上受一定简单规则的驱动，自组织而达成平 衡，这是复杂性重要的一种形式。第五章作了一个总结，展望了论文工作可能存 在的改进方向，乃至该课题研究可能的发展方向。 基于复杂网络的信息传播 第二章复杂网络基本理论 2 1 网络的拓扑参量 数学中以图论形式开展的网络研究是离散数学的基柱之一。1 7 3 6 年大数学 家e u l e r 解决的著名的葛底斯堡七桥问题是网络理论首个真正的证明，在此之后 网络理论得到了快速的发展。二十世纪期间，网络发展成为一个重要的知识实体。 在过去几年里，现实世界网络的很多很有趣的特征引起了科学家们的关注。这些 特征表明现实中的网络不同于规则图，也不同于随机图。现实世界网络是介于规 则图和随机图之间的一种网络，这些逐渐凸现出来的事实表明这些现实网络背后 存在特殊的生成机制。这些生成机制的发现将有助于人们开发具有特定目标的网 络结构。 首先，简单介绍有关图的基本知识。图g 是由点的集合v 和边的集合e 组 成的，记为g = ( v ，e ) 。其中v ( g ) = v l ，v 2 ，v n ) ( 或简记为v ( g ) = 1 ， 2 ，n ) ) 表示图g 的顶点集合，v 的势n 表示网络的顶点总数；边的集合是 e ( g ) = ( i l ，j 1 ) ，( i 2 ，j 2 ) ，( i m ，j m ) ，m = i e i f l l j 网络总边数。如果( i ， j ) 和( j ，i ) 对应同一条边，则该网络称为无向网络( u n d i r e c t e dn e t w o r k ) ，否则 称为有向网络( d i r e c t e dn e t w o r k ) 。一般的无权网络( u n w e i g h t e dn e t w o r k ) 实际 上是每条边的权值相等均为l ，如果要讨论不同的权值那么就要在加权网络 ( w e i g h t e dn e t w o r k ) 上。当网络是无向无权的时候，邻接矩阵a = a i j 是一个0 - l 对称矩阵，表示图中顶点之间的连接关系，具体形式为： 勺= i n 0 ：磊嚣爱篙凳 ， 勺。 ，如果f ，歹之间无边 。z 。1 当网络是有向图时，邻接矩阵a 是非对称的0 1 矩阵；当网络含权时，a 中的非 零元素代表边的权值。 本文不讨论含有重边( 同一条边出现不止一次) 和自连边( 边的两端是同一 节点) 的图。满足y y 且f e 的图g = ( v ，e ) ，称为图g = ( v ，e ) 的子 图。 2 1 1 度与度分布 节点i 的度值( d e g r e e ) 描述的是节点i 连接的边数，通常用k i 表示，在有 1 2 第二章复杂网络基本理论 向网络中又细分为出度( ) 和入度( 矽) ，节点的出度是指从该节点发出的 边的数目，入度则是指指向该节点的边的数目。 在无向图中， f 。= - i ( f ，j ) e ) ( 2 2 ) k i = i r i i ( 2 - 3 ) 在有向图中， r 7 = ui ( f ，j ) e ) ，r 7 = ji ( ，i ) e ) ( 2 - 4 ) 酽= l r ，i ，矽= l r r i ( 2 5 ) f 。= r 7 u r ? ( 2 6 ) 毛= + 矽( 有向图中k i 不一定等于ir i i ) ( 2 7 ) 那道经典的葛底斯堡七桥问题，乃至一笔画问题利用的就是节点的度值最终 解决的。虽然很巧妙但是解决的都是初等问题。在复杂系统中，我们更倾向于讨 论度的统计特性。由于每条边有两个端点，因此无向网络的边数可以写为： 蚓= 寻磅 ( 2 - 8 ) 进而我们知道平均度值在表示节点邻居( n e i g h b o r ) 数目的同时，又描述了 边的疏密程度： ( 七) = 丙1 午k 。= 等 ( 2 9 ) 更细致地描述网络节点度的情况则需要使用到节点度的分布( d e g r e e d i s t r i b u t i o n ) ，度分布函数p ( k ) 表示的是一个随机选定的节点其度恰好为k 的概率， 也即网络中度为k 的节点所占的比例： p = 掣 亿 如全局耦合网络由于每个节点都和其它所有节点连接，它们的边数都相等， 易知其度分布为( n 1 ) 处为1 ，其它处处为0 。后面即将介绍的随机网络度分布为 泊松分布( 如图2 1 a ) ，无标度网络为幂律分布。由于分布函数是离散的，直接 1 3 基于复杂网络的信息传播 画直方图会有很多的偏差，累积分布函数是实际经常采用的方法，累积度分布 ( c u m u l a t i v ed i s t r i b u t i o n ) 的定义如下： p ( 后) = p ( 尼) ( 2 1 1 ) k - - k 即节点度值大于等于k 的概率( p ( o ) = 1 ，p ( o o ) = o ，p ( k ) = ( 1 - p ( k ) ) ) 。传统的画直 方图的方法把落入同一直方内的数据点的值所存在的差异信息全部丢失，采用累 积分布函数的优点在于考虑了所有原始数据。 村 图2 1 ( a ) 当 0 时，表示整个网络呈现同配性结构， a 0 时整 个网络呈现异配性。通过分析大量实际网络数据发现，大部分的社会网络结构都 呈现同配性，像电影演员合作网络，e m a i l 地址簿网络等等；而大量科技网络， 比如电网、i n t e m e t 互联网等，以及大量生物网络，蛋白质网络、新陈代谢网络、 神经网络等等都呈现异配性。 p a s t o r - s a t o r r a s 等人在研究因特网的匹配性时，发现节点的最近邻度值的平 均值与其度值大小负相关，说明因特网是异配的，也就提出了最近邻平均度值： 向 u ”= 黼( 其中r ( k h