基于复杂网络的信息传播.doc

厦门大学硕士学位论文基于复杂网络的信息传播姓名：张嘉龄申请学位级别：硕士专业：系统工程指导教师：李茂青20080501，：；厦门大学学位论文原创性声明兹呈交的学位论文，是本人在导师指导下独立完成的研究成果。本人在论文写作中参考的其他个人或集体的研究成果，均在文中以明确方式标明。本人依法享有和承担由此论文产生的权利和责任。声明人（签名）：荔荔韬子年月弓厦门大学学位论文著作权使用声明本人完全了解厦学有关保留、使用学位论文的规定。厦门大学有权保留并向国家主管部门或其指定机构送交论文的纸质版和电子版，有权将学位论文用于非赢利目的的少量复制并允许论文进入学校图书馆被查阅，有权将学位论文的内容编入有关数据库进行检索，有权将学位论文的标题和摘要汇编出版。保密的学位论文在解密后适用本规定。本学位论文属于、保密（），在年解密后适用本授权书。、不保密（）（请在以上相应括号内打“）日期：硝年臼日日期：沙矿年易月弓日第一章绪论第一章绪论系统是由相互作用和相互依赖的若干组成部分（要素）结合而成，具有特定功能、结构、环境的有机整体。系统具有整体性、集合性、层次性、相关性、目的性、环境适应性。复杂系统是组元之间相互作用的非线性性不可忽略，系统运行机制不明晰，一般带有不确定性。通常这些非线性相互作用能够使复杂系统作为一个统一的整体进行自组织演化，从而获得组元独自无法获得的集体行为和特征。随着上世纪七八十年代自组织理论和非线性科学的蓬勃发展，复杂系统和复杂性科学的研究掀起了一个浪潮【。，这对人们原先的还原论的认识带来革命性的新思潮。著名科学家认为：二十一世纪是复杂性科学的世纪。复杂网络的动力学特性研究，将对当前国际上关注的多智能体（）协作、群体行为（）控制等热点问题，带来新的视角和方法。总之，复杂网络可作为研究复杂系统、复杂性科学一个可行的切入点【，并将会在生态演化、神经网络、群体智能、认知科学、自组织涌现行为、网络化系统、经济动力学等方面的研究中彰显重要作用。复杂网络概述系统工程是以大规模复杂系统（特别是管理系统）为研究对象，在系统理论、管理科学及运筹学等学科基础上形成的交叉学科。系统工程在研究复杂系统结构和功能的基础上产生了复杂网络这样一个有力的工具，网络不但可以表现许多复杂系统的结构形态，还可以反映系统的动力学特性。当系统中元素，在某类事件中表现出一定的同质性，则可以使用网络的方法来研究系统在该类事件下的性质和演化，如传染性疾病、信息的传播。作为系统，其结构可以抽象为网络，各类作用体抽象为网络结点，各种相互作用抽象为结点之间的边。这样，就可以运用图论和网络分析的理论、方法及工具进行系统结构的拓扑特性研究。近年来关于复杂网络的研究受到统计物理学、系统科学、社会科学和工程领域研究人员的广泛关注，已经成为他们的一个研究热点。自然界中存在的大量复杂系统都可以通过形形色色的网络加以描述。一个典型的网络是由许多节点与连接两个节点之间的些连线组成的，然而并非节点间有任意关系就有连边，往往是根据具体问题，两个节点之间具有某种特定的关系基于复杂网络的信息传播才连一条边，反之则不连边，有边相连的两个节点在网络中被看作是相邻的。实际上，正是因为现实世界中很多复杂系统都可以用复杂网络来建模，复杂网络的研究才有其实际背景。例如，是路由器等各种各样的终端组成的复杂网络；万维网（）是由网页组成的复杂网络；大脑是由神经元组成的复杂网络；一个社会关系网络是由个人、组织甚至国家组成的复杂网络。此外常见的复杂网络还有通信网络、电网、物种之间的捕食网、蛋白质问交互组成的网络、电路与系统（节点是电子元件，边是它们之间的线路）、公路网、铁路网、航空网、科研合作网（节点是研究者，边是研究者合作的指标）、论文之间的引用关系网等。构建了网络之后，即可研究复杂网络上面的动力学现象，如在社会关系网络上讨论舆论的传播，接触关系网络上讨论传染病的传播，计算机病毒在网络或邮件网络上的传播，在引文网络上研究新思想的提出与传播，在科学家网络上研究科学家之间的相互影响，电网的级联崩溃事故，城市务工人员的流动等。网络与现象结合还可以用来讨论网络的稳定性等结构与功能关系。例如，在食物链网络上讨论个别或部分物种灭绝对整体生态系统的影响；致死性传染病传播的过程中对网络拓扑的改变，如欧洲中世纪的黑死病；网络路由在中间结点损毁时能够智能调整路径；在科学家网络中讨论某个领域中不同的科学家对网络演化的影响：在级联崩溃等激烈的动力学过程中，我们可以更加明显地观察到系统在达成功能的过程中，结构的自适应变化。此外，网络本身的演化过程也是一个有趣的问题，例如网络的形成被认为是无限定原则的，但是它却展现了一些重要而普适的结构特征与稳定性；再如，对于某学科内的引文网络与科学家网络的演化机制的研究，有可能给出促进科学发展的新方案和模式【。这些复杂网络问题都与人们的生活息息相关，比如年月日“爱虫”电脑病毒在上迅速蔓延造成的损失高达数亿美元：年月日发生的北美电网级联崩溃导致的大停电，事故波及美国和加拿大两国，超过万的人口，并造成经济损失约亿美元。专家认为，如果恐怖分子有效袭击美国电网，连锁反应的后果可能比撞毁世贸中心更严重。数学家和物理学家在考虑网络的时候，往往只关心节点之间有没有边相连，至于节点到底在什么位置，边是长还是短，是弯曲还是平直，二维表现时有没有第一章绪论相交等等都是他们不在意的。在此，我们把网络不依赖于节点的具体位置和边的具体形态就能表现出来的性质叫做网络的拓扑性质，其相应的结构叫做网络的拓扑结构。什么样的拓扑结构比较适合用来描述真实的系统呢？两百多年来，对这个问题的研究经历了三个阶段。欧拉对“七桥问题的证明是图论研究的开始。在随后的近两百年间，科学家们对现实网络系统的研究，局限于使用图论研究规则网络或是结点个数比较少的小结构网络，例如二维平面上的欧几里德格网，或者最近邻一维链。到了世纪年代末年代初，两位匈牙利数学家和在图论领域做出了一个重要突破，即在文献中提出的随机图理论。他们用随机图来描述网络的拓扑结构，这为复杂网络的研究奠定了一个数学理论基础。随机网络的概念在接下来的年里一直主导着人们对现实世界的理解和思维，直到今天仍有人在做这方面的研究。但随机图理论是否能准确地描述现实世界中所有的网络呢？通过大量的观察，我们可以得知：现实世界中绝大多数的网络既非完全规则亦非完全随机。例如，两个人是否是朋友，中两个路由器之间是否有光纤连接，上两个页面之间是否有超链接等都不会是完全确定或是完全靠抛硬币可决定的。随机图理论虽然不能准确地描述现实世界中的网络，但却能统治这个领域这么多年，主要还是由于过去我们缺乏对现实世界中网络数据的分析能力和对现实世界网络拓扑结构的准确认识。近年来，事情发生了变化，由于科学技术领域特别是领域的高速发展，使我们获得的可供我们刻画现实世界网络特征的数据越来越多，加之超级计算机的发展为我们提供了强大的计算和数据分析能力，以及各个学科之间的相互交叉和融合趋势在不断加强，使得人们有能力在对各种不同类型网络的数据分析的基础上，揭示复杂动力网络的一些共有特征和性质，从而激发起了人们以理论、仿真和实际数据验证三种手段研究复杂网络的浓厚兴趣。以此为契机，经过大家在这一研究方向上不懈的探索和努力，最近在复杂网络研究领域中取得了两项重要的发现：大多数复杂网络都具有小世界（）和无标度（）特性。年月，美国康奈尔大学理论与应用力学系的博士生及其导师一一非线性动力学专家教授在杂志上发表的题为“小世界网络基于复杂网络的信息传播的集体动力学的文章【】描述了从规则格子到随机图之间的转变，提出了小世界网络的概念。小世界的概念从字面上的意思是说尽管网络很大，但通常在网络的任意两个节点间都有一条相对于网络规模来讲是很短的路径。我们可能经常遇到这样的情形，当你和一个新朋友聊天的时候，发现你们有共同的好朋友（他是你朋友的朋友），于是双方都会发出“世界真小这样的惊叹后面我们将介绍这是因为现实的网络往往有很高的集聚系数。年月美国大学物理系的教授及其博士生在杂志上发表的题为随机网络中标度的涌现的文章【】介绍了另一项重要的发现。和开展一项描绘万维网的研究，他们原本以为会发现一个随机网络的钟形图，但统计分析的结果令他们意外地发现：万维网基本上是由少数高连通性的页面串连起来的，以上页面的连接数不到个，而占节点总数不到万分之一的极少数节点，却和个以上的节点连接。随机网络具有的有特征意义的多数节点大致相同的连接数“平均度值不见了。于是他们把这种网络称为“无标度网络（）。他们在计算恰好拥有个连接的万维网页面的数目时，发现网页的度值分布呈现一种幂指数（）分布率，即：任何节点与其他个节点相连接的概率正比于“（也就是（）“），直观地有度分布的函数曲线在双对数坐标系下是一条下降的直线。经更多的实证研究发现，大量复杂系统，诸如互联网、科学家合作网络、新陈代谢网络以及好莱坞演员合演网络，都存在这种少数但高连通的节点，遵循“幂次定律（）。这种节点可称为“集散节点（）”。许多不同的复杂系统，其网络结构都是无标度网络，都是由少数集散节点主控的系统。虽然目前复杂网络研究如此火热，科学家们还没有给出复杂网络精确严格的定义，从这几年的研究来看，之所以称其为复杂网络，大致上包含以下几层意思：首先，它是大量真实复杂系统的拓扑抽象；其次，复杂网络至少在感觉上比规则网络和随机网络复杂，它介于完全规则和完全随机之间，为了生成完全符合真实统计特征的网络科研工作者不断提出更适合研究的复杂网络，并且这个过程还在继续：最后，由于复杂网络是大量复杂系统得以存在的拓扑基础，因此对它的研究被认为有助于理解复杂系统的复杂性。尽管近年来提出了许多刻画和度量网络的概念，但其中有三个概念发挥了重第一章绪论要作用，它们是：度分布、平均路径长度和集聚系数。事实上最初和就是试图构造一种具有小的平均路径长度（与随机网络类似）和较大的集聚系数（与规则网络类似）的网络，循此途径最后得到了小世界网络模型。无标度网络的发现是由于观察到许多大规模网络的节点的度呈现一种幂指数分布率。因此，这三个概念在复杂网络的奠基性研究中起到了至关重要的作用，并且在后来的复杂网络研究中也扮演了重要的角色。复杂网络的研究方向和意义近年来，关于复杂网络的研究正处于蓬勃发展的阶段，其研究者来自图论、系统工程、统计物理学、通信网络、生态学、社会学以及经济学等各个不同领域，不同领域的研究者们在不同的方向上展开了研究工作，开辟了一些复杂网络的研究方向。相信随着今后研究的进一步开展，复杂网络会有更多更重要的研究领域被开辟出来。就目前而言，复杂网络的研究至少包含了以下几个方向：）对复杂网络特性进行更深入和广泛的实证研究。这一课题应可视为复杂网络研究中最基础的一步，采用表征网络系统结构和行为的统计参量来描述现实网络，对样本数据进行实际测量，从而揭示现实网络的统计属性。事实上，正是通过分析现实世界中网络数据得出它们的共性，才有了小世界网络和无标度网络的提出。对更多的实际复杂网络数据的分析可以发现其新的共性，借此来构建新的更符合实际的网络模型。很多研究者相继对各个不同领域的网络进行了研究和分析，如互联网，网络，电话呼叫网络，电影演员合作网络等等。）复杂网络结构及演化机理的研究。人们在研究实际网络的过程中，常常发现一些网络具有相似的特征，比如很多实际网络的度分布都遵从幂律（）分布、并且有大集聚系数小平均路径长度等等。于是为了研究的方便，根据实际网络的共有特征，构建能够帮助理解统计属性的网络模型，使得模型化后的网络具备实际网络的某类或某几类特征，从而解释网络结构的成因，揭示决定网络演化的主要因素。除了最初提出的小世界网络模型和无标度网络模型之外，研究者相继又提出了其它一系列网络模型。基于复杂网络的信息传播例如，在文献，中作者提出并研究了确定性的小世界网络模型；文献对无标度网络模型进行了改进和推广，提出了各种各样的无标度网络模型：文献提出了带有群落性网络拓扑结构（）的复杂网络模型：文献依据实际复杂网络的生长机制提出了种种加权复杂网络（）模型，这些模型能够很好的刻画实际网络中的三种幂律分布。）复杂网络上的动力学过程和动力学特性。通过把复杂网络看成动力系统或在复杂网络中引入动力学单元，许多研究者对复杂网络的动力学行为展开了研究，进一步理解网络拓扑结构对网络上的物理过程（比如病毒传播、网络导航、拥塞、同步等）的影响，测算性质涌现的临界，预测网络系统的行为。如分析复杂动态网络的同步问题，探讨随机去点与选择性攻击时网络的容错性与抗攻击性问题，研究复杂网络的控制问题。此外，一些与实际网络结合十分紧密的动力学过程近几年也开始被广泛的研究。譬如，万维网与社会网络的搜索与导航，社会网络和计算机网络中的病毒传播与流行，电力网络上的大停电事故。在复杂网络动力学性质的研究中，网络的拓扑结构怎样影响网络的动力学性质是一个非常有趣的问题，也是一个研究的热点。随着网络拓扑结构的改变，一些有趣的现象会逐渐涌现，如在规则一维链中随机重连边，会逐渐出现小世界现象，继续重连又会逐渐变成完全随机图。由均质的随机网络到异质的无标度网络，网络容错能力逐渐增强，但是抗攻击性迅速减弱，这是因为随机网络是不存在集散节点的，对随机网络的攻击与随机网络自身随机出错是无差别的，一般来说不能造成致命性的伤害，但是对于无标度网络，攻击它的集散节点可以使网络很快分崩离析。的传播与防控，使我们进一步看到了无标度网络的容错性和脆弱性研究所具有的重要实际价值。复杂系统和复杂网络要充分重视学科的交叉和横跨研究，是物理学家，他发表的长文“【，全面总结了复杂网络的已有研究成果，高屋建瓴，启迪我们运用统计物理成熟的观念、理论和方法，以及一切可以运用的数学成果，并把生物系统、社会经济系统和物理系统联系起来进行观察分析，从网络的拓扑特性方面寻找它们的共性。以系统结构的拓扑特性网络为切入点，展开研究系统学层次的系统结构第一章绪论理论，必须遵循从个性到共性的认识规律。从具体系统的网络分析入手，又适时地抽象出共性，再考虑这些共性对其它领域的普适程度。这方面也为我们提供了经验。根据他发表成果的时间表可知，他是从研究万维网起始的，逐次扩展至互联网、演员合作网，科学合作网，基因蛋白质相互作用网等等，在这个延展的过程中，不断反复地提炼共性，建立模型进行理论分析。钱学森曾指出，要建立开放的复杂巨系统一般理论，必须从一个一个具体的开放的复杂巨系统入手，只有这些研究成果多了，才能从中提炼出一般的开放的复杂巨系统理论。同样的，从系统学的高度研究系统结构的拓扑特性也必然要经过这条道路。我们应该意识到这样一个大好趋势，即各学科都在兴起对本学科的对象系统进行网络分析的研究。这实质上已经把各门具体学科的研究从一个方面，即以同一范式一一节点、连接和网络进行研究，这已是从很高的层次，进行从定性到定量的共性提炼了。因此，从系统科学这一角度来说，首先要特别重视各学科领域的网络分析成果，同时注意从系统科学方面进行整合研究。系统理论在基本概念、理论和方法等方面均已取得了许多重要成果，譬如关于层次结构的研究，普里高津关于耗散结构的研究，钱学森等关于开放的复杂巨系统的研究等重要成果。我们相信，把这些成果融会进复杂网络结构和动力学特征的研究，双向互动，在两方面都会有新的进展。总体来说，由于复杂网络的研究尚处于起步阶段，对复杂网络理论应用的研究相对来讲还比较少，但迄今己发现了很多潜在的有趣应用。例如，上述对复杂网络鲁棒性的研究成果可以应用到网络拓扑设计中去，对网络同步问题的研究有望在通信领域中发挥作用，对网络搜索和导航问题的研究可能在通信及计算机网络等的路由问题中有应用前景同时对设计更加有效的搜索引擎也有可能起到关键作用，对病毒传播网的研究在预防和控制传染病与计算机病毒方面有重要的指导意义。著名的生物学家亦在其近著后基因组信息学中提出以复杂网络作为研究后基因组信息学的总体思路，他在书中列了一个表如表所示，并写了占全书正文五分之一的总括性的最后一章“分子相互作用的网络分析。此外，最近在文献中作者提出了把无标度网络模型应用到纠错编码当中，如果和现在比较热门的研究领域网络编码结合起来可能会有重要的成果出现。可以预见，随着复杂网络领域研究成果的不断涌现，对这些成果的应用基于复杂网络的信息传播也将成为今后研究的一个主要方向。表生命科学中的网络系统节点边蛋白质三维结构原子原子相互作用生物体分子分子相互作用脑细胞细胞相互作用生态系统生物体生物体相互作用文明人社会关系相互作用复杂网络的研究在很多学科有重要意义，包括电路与系统、复杂性科学、非线性科学、计算机科学、控制理论、生物等等，这是由于复杂网络广泛的存在于自然界和社会之中。因此，复杂网络的研究工作对我们进一步认识自然界和社会的现象有着至关重要的意义。我们可以利用复杂网络的己有研究成果，更深刻的认识自然界和社会的复杂性，进而我们可以设计出具有更好特性的复杂网络或者使网络处在有利于我们的状态。研究复杂网络的重要意义还在于让人们正确认识和防范系统灾害。实际生活中很多网络都不可避免地遭受侵害：电力网上发生的连锁故障可能会导致大停电事故，给生产和生活带来严重的损失；上发生的信息拥塞可能会使信息传输不顺畅，致使人们交流产生困难；计算机网络上的病毒传播则会严重影响人们使用计算机进行日常工作；此外，人群网络上传染病的传播也会影响到人们的健康。事实上，我们可以将复杂网络理论应用到其中来解决问题，譬如可以根据复杂网络理论设计具有更好性质的网络拓扑；可以根据复杂网络理论进行拥塞控制，改善网络的传播效率；可以根据复杂网络理论对上计算机病毒和人群网络中传染病病毒的传播进行控制，抑制病毒的传播。本文的研究方法和内容安排复杂网络是系统工程一个极有用的成果，以复杂网络的拓扑特性研究为切入点，深入开展系统结构与功能的研究。系统结构是系统科学的基本概念，暂不谈哲学和数学，就系统学层面来说，其内涵迄今还没有丰满的阐述。结构是客观事第一章绪论物的基本属性，也是各学科领域的基本问题，如物质科学研究物质的结构和性质，生命科学和社会科学研究事物的结构和功能。可以说，每门学科对其研究对象的结构，都有非常丰富的具体成果；但从系统学的高度，横跨物质系统、生物系统和社会经济系统的具体研究成果，也就是系统学层面的成果还不多。如上所述，系统结构可以描述成网络结构，但原来研究网络结构的规则图和随机网络理论只反映了众多系统上两头的极端情况。大多数复杂系统既非完全规则也非完全随机，是规则和随机伴行的，是动态演化和开放自组织的。单纯运用规则图和随机网络理论对普遍存在的这些复杂系统不能进行实质性的分析研究，小世界网络和无标度网络的发现，为我们打开了新的视野。每一个复杂网络都有其自身的特殊性质、独特现象及演化机制，但是由于都可以使用网络分析的方法，所以也存在着共性。例如，关于簇系数、顶点度值分布对网络结构的影响及其分析方法，以及大量不同网络中存在的相同的统计特征，不同的无标度网络对于随机去点与选择性攻击都表现出容错性和脆弱性。这些来自不同领域的大规模系统呈现出共同的普适规律，促使人们去探索隐藏在这些表象后面的内在演化机制，掀起了研究复杂网络的热潮。目前复杂网络的研究主要包括三个方面的内容：复杂网络的静态拓扑结构，复杂网络的演化机制，和复杂网络的动力学性质。复杂网络的静态拓扑结构是指网络的拓扑结构不随时间变化，研究的主要内容包括度分布、集聚系数、平均路径长度、介数等等。复杂网络的演化是指网络的拓扑结构随时间的演化，目前的研究还是基于增长和偏好连接的无标度网络模型。复杂网络上的动力学研究本质上是探讨网络结构与功能关系，这是复杂网络的研究重点。目前人们积极致力于复杂网络上传统统计模型的动力学研究，如复杂网络上的渗流【】，流行病传播【，模型【，随机行走击等。研究表明，复杂网络上的这些动力学性质与规则网络、随机网络上相应的动力学性质有明显的不同，复杂网络上的这些特殊动力学性质是由复杂网络的特殊拓扑结构所决定的。静态特性表征系统结构，动态特性表征系统功能，实际上，系统的结构与系统的功能是密不可分的，结构影响功能，功能反作用于结构。只有将二者结合起来研究，才能揭开复杂系统的真正面纱。把系统结构、功能与具体系统结合起来是复杂网络研究的中心内容，分析复杂网络特性主要有以下三种方法：基于复杂网络的信息传播）实证研究方法。对于复杂网络这样的研究方向，应该把实证研究放在第一位，充分运用调查统计的手段和当今国际上已有的各种数据库，并结合强大的计算机处理数据和计算的能力，寻找出各种复杂系统结构的拓扑特性。遵循“幂次定律是等人在研究万维网页面的时候发现的，幂次定律中（）中的值，通常介于之间，也是经过大量的实证研究发现的。就系统科学来说，只有在大量的实证性成果的基础上，进行建模和理论分析，才有实质性的意义。）解析研究方法。运用图论和网络分析的理论、方法和工具进行系统结构的拓扑特性和系统功能的研究。主要包括连续性方法，主方程方法，变化率方程方法等。由于复杂系统既不完全规则又不完全随机，所以完全解析的数学方法还很不成熟，只能研究复杂系统里部分层面的问题。尤其是连续性的解析分析方法，由于网络自身的离散性，故要求网络规模“足够大，大量有意义的结果要求网络节点数在连续次求取常用对数后还要比大，在目前科学观察得到的宇宙中，还没有任何一个有物理意义的数值达到如此的数量级。）数值模拟分析方法。这是目前最主要，也是用得最广泛的方法。数值模拟不需要形成很精确的数学公式，或者使用很复杂的推导求解方法，只是根据系统元素和它们的交互行为设计出计算机程序，然后运行以观测所模拟的系统的演化情况。当然，数值仿真对于很多现实系统还是具有一定的解释和预测能力的，尤其对于特定问题，即便无法提出解析方法也可以使用数值模拟，然后再回到实际系统求证与校正。数值仿真的方法在某种程度上和实证研究有异曲同工之妙，通过多次的仿真，可能猜测出一般性的通用命题，进而再想办法论证之。理论进步反过来又可以指导与促进数值仿真，两者互相推动。毋庸置疑的是，对于终极解析理论的追逐是无止境的，任何理论在数据的检验下都有可能具备改进的空间一一哪怕是精确的牛顿运动定律，最终也被论证成为相对论在低速时的特例。网络的研究从欧拉的经典图论，转变到数学领域的随机网络，乃至现代意义上的复杂网络，正是一步步从纯学术向理论联系实际迈进，人们对于复杂网络所能表现的复杂系统特性越来越感兴趣，从物理学到信息学的众多学科均加入到了复杂网络的研究当中。网络的节点是网络结构和功能的基础，例如信息的传播要通过一个个载体的第一章绪论接收与发送，传染病亦如是，公交网络中的节点也是实现其重要功能的车站，社会网络中人或组织等个体也是网络的基础。当然，连线表达了节点之间的交互，往往还表征网络的效率、稳定性等重要课题。如何在固有的基础之上优化网络的传输效率或者抑制不良信息的传播是本文主要讨论的重点。复杂网络是由成千上万个节点组成，从而使得网络行为具有统计特性，也由于节点众多，我们往往关心统计特性多于关心每个节点的细部特性，这样就能化复杂问题为相对简单的问题，本文正是利用统计值讨论了复杂系统中意见的交互和话题的传播。当然，对复杂系统与复杂网络的研究毕竟才刚开始起步，还有很多问题有待我们去研究和探索。本文分为五章。第一章为绪言，介绍复杂系统与复杂网络的背景，研究方向及其意义，说明了该课题的分析方法及主要内容。第二章是本文的概念定义和理论基础，是复杂网络研究的基石，使得本文的研究能够高屋建瓴。第三章和第四章是本文主要的研究工作，第三章研究的是复杂网络动力学中举足轻重的传播动力学，构建了一个意见交互模型进行仿真，讨论了传播的条件，网络结构对传播效率的影响；第四章研究的是复杂网络的演化动力学，即错综复杂的系统，其状态更新以及更新策略在随机的基础上受一定简单规则的驱动，自组织而达成平衡，这是复杂性重要的一种形式。第五章作了一个总结，展望了论文工作可能存在的改进方向，乃至该课题研究可能的发展方向。基于复杂网络的信息传播第二章复杂网络基本理论网络的拓扑参量数学中以图论形式开展的网络研究是离散数学的基柱之一。年大数学家解决的著名的葛底斯堡七桥问题是网络理论首个真正的证明，在此之后网络理论得到了快速的发展。二十世纪期间，网络发展成为一个重要的知识实体。在过去几年里，现实世界网络的很多很有趣的特征引起了科学家们的关注。这些特征表明现实中的网络不同于规则图，也不同于随机图。现实世界网络是介于规则图和随机图之间的一种网络，这些逐渐凸现出来的事实表明这些现实网络背后存在特殊的生成机制。这些生成机制的发现将有助于人们开发具有特定目标的网络结构。首先，简单介绍有关图的基本知识。图是由点的集合和边的集合组成的，记为（，）。其中（），）（或简记为（），）表示图的顶点集合，的势表示网络的顶点总数；边的集合是（）（，），（，），（，），网络总边数。如果（，）和（，）对应同一条边，则该网络称为无向网络（），否则称为有向网络（）。一般的无权网络（）实际上是每条边的权值相等均为，如果要讨论不同的权值那么就要在加权网络（）上。当网络是无向无权的时候，邻接矩阵是一个对称矩阵，表示图中顶点之间的连接关系，具体形式为：勺：磊嚣爱篙凳，勺。，如果，歹之间无边。当网络是有向图时，邻接矩阵是非对称的矩阵；当网络含权时，中的非零元素代表边的权值。本文不讨论含有重边（同一条边出现不止一次）和自连边（边的两端是同一节点）的图。满足且的图（，），称为图（，）的子图。度与度分布节点的度值（）描述的是节点连接的边数，通常用表示，在有第二章复杂网络基本理论向网络中又细分为出度（）和入度（矽），节点的出度是指从该节点发出的边的数目，入度则是指指向该节点的边的数目。在无向图中，。（，）（）（）在有向图中，（，），（，）（）酽，矽（）。？（）毛矽（有向图中不一定等于）（）那道经典的葛底斯堡七桥问题，乃至一笔画问题利用的就是节点的度值最终解决的。虽然很巧妙但是解决的都是初等问题。在复杂系统中，我们更倾向于讨论度的统计特性。由于每条边有两个端点，因此无向网络的边数可以写为：蚓寻磅（）进而我们知道平均度值在表示节点邻居（）数目的同时，又描述了边的疏密程度：（七）丙午。等（）更细致地描述网络节点度的情况则需要使用到节点度的分布（），度分布函数（）表示的是一个随机选定的节点其度恰好为的概率，也即网络中度为的节点所占的比例：掣亿如全局耦合网络由于每个节点都和其它所有节点连接，它们的边数都相等，易知其度分布为（）处为，其它处处为。后面即将介绍的随机网络度分布为泊松分布（如图），无标度网络为幂律分布。由于分布函数是离散的，直接基于复杂网络的信息传播画直方图会有很多的偏差，累积分布函数是实际经常采用的方法，累积度分布（）的定义如下：（后）（尼）（）即节点度值大于等于的概率（），（），（）（）。传统的画直方图的方法把落入同一直方内的数据点的值所存在的差异信息全部丢失，采用累积分布函数的优点在于考虑了所有原始数据。村图（）当一，时的泊松分布图（）当，时的幂函数累积度分布近年来大量的实证研究表明，许多真实网络的度分布都遵循幂律分布（），如网，引文网等。对于随机网络和规则网络，度分布区间非常狭窄，几乎找不到偏离节点度均值较大的节点，故其节点度均值可以被看作其节点度的一个特征标度。由于幂函数具有标度不变性，因此通常把节点度服从幂律分布的网络叫做无标度网络，并称这种节点度的幂律分布为网络的无标度特性。幂律分布函数数学形式为：（）一，其中一般介于到之间。幂函数在双对数坐标系下是条下降的直线。与指数函数相比，幂函数的曲线是一条下降相对缓慢的曲线，从而网络中可以存在度值较大的节点，通常称这第二章复杂网络基本理论些节点为集散节点（）。平均最短路径最短路径的研究是出于很多现实问题的需要，如涉及运输费用、传递效率之类的问题都要讨论最短路径。在无向无权网络中，两节点之间的距离（）定义为连接两者的最短路径经历的边数（不连通节点之间的距离有几种定义方法）。网络的直径（）为所有点点距离中最大的那一个（不连通网络的直径另有好几种规定方法），即：（）（）网络的平均路径长度定义为：（）（）则是所有节点对距离的平均值（本文中平均路径长度只考虑连通节点对之间的平均距离），它描述了网络中节点的分离程度。复杂网络研究中一个重要的发现是绝大多数大规模真实网络的平均路径长度比想象的小得多，人们把小平均路径距离和下文将提及的大集聚系数合起来称为“小世界”特性。这一提法来源于著名的“小世界实验，美国哈佛大学社会心理学家要求参与者把一封信传给他们熟悉的人，使这封信最终传到指定的人手里，籍此来探明熟人网络中路径长度的分布，结果表明平均传过人数仅为六，这一试验也正是流行的“六度分离（）概念的起源。这一结果是“小世界效应的首次直接证明之一。在讨论节点之间距离时，在年提出了网络的效率（）的概念【，定义为：乓丽，否气莉，菇去舶，其中毛表示连接节点和的路径的效率，是最短距离吃的倒数。这一定义可以用来描述网络传递信息的能力，同时避免了（）式中出现无穷大值的情形，因为对于不连通的节点和，其最短距离为无穷大，传输效率为。“小世界效应对网络的动力学含义非常明显，例如考虑信息在网络上的传播，小世界效应表明在多数现实网络上这将会是一个快速的传播过程。近年来，“小世界效应这术语有了一个更为确切的定义：如果网络平均节点度固定，基于复杂网络的信息传播网络直径的值随网络大小以对数的速度或慢于对数的速度增长，那么称此网络具有“小世界效应”。匹配性和最近邻平均度值在研究节点度的时候，相邻节点之间的度值相关性被用来描述不同网络结构之间的差异，如果网络中的节点趋于和自己相似的节点相连，比如度大的节点倾向于和度大的节点相连，就称该网络是同配的（）：否则，就称该网络是异配的（）。定义正负匹配度（又称度关联系数，扩（毛一仍纺）彳可（一）仍概来刻画网络同配性。其中，瓯为网络中边的两个端点度值分别为和的概率，仍莩磊等由当时，表示整个网络呈现同配性结构，时整个网络呈现异配性。通过分析大量实际网络数据发现，大部分的社会网络结构都呈现同配性，像电影演员合作网络，地址簿网络等等；而大量科技网络，比如电网、互联网等，以及大量生物网络，蛋白质网络、新陈代谢网络、神经网络等等都呈现异配性。等人在研究因特网的匹配性时，发现节点的最近邻度值的平均值与其度值大小负相关，说明因特网是异配的，也就提出了最近邻平均度值：向”黼（其中（融存在度数为的邻居）（）对于同配型网络，加（）随的增加而增加，对于异配型网络，曲（）随的增加而减小。集聚系数网络的集聚系数（），又称簇系数，是衡量网络集团化程度的重要参数。比如在社会关系网络中，你朋友的朋友可能也是你的朋友，或者你的两个朋友可能彼此也是朋友。度值为或者的节点，簇系数定义为；度第二章复杂网络基本理论数大于等于的节点的簇系数，定义为节点的邻接点之间实际存在的边数与所有可能的边数的比值：塾（），上一）。其中，表示节点的度值，表示节点的邻接点之间实际存在的边数，集聚系数也叫传递性，是指集聚系数大时如果节点与节点相连，并且节点与节点相连，那么节点也极有可能与节点相连。整个网络的集聚系数就是所有结点簇系数的平均值（也可以度为零的节点不参与平均，度值为的节点簇系数记为）：（）（）由于这种集聚系数定义无视节点重要性的区别，所有节点对于网络集聚系数的权重相等；集聚系数的另一个定义由和提出，定义集聚系数为网络中所有的三角形个数除以所有节点三元组个数的总和，再乘以，数学表达如下：三：丝，（堡！，星竺）（）仁互心。引图按平均簇系数计算出来的集聚系数是按照第二种方法计算出来的集聚系数是易知，环形、树形、星形等网络不存在三角形，集聚系数为；分块全局耦合的网络（可以不连通，每一个连通枝为一个节点数不小于的全连接图）的集聚系数为。现实网络的集聚系数比包含相同数目节点和边的随机图中的集聚系数要大很多。当一时，现实世界的网络有（），而随机图却有）。当俩朋友在聊天时，发现他们有共同的朋友，往往会感叹“这世界真小啊”。因基于复杂网络的信息传播此，比较大的集聚系数和比较小的平均距离，合起来称为网络的“小世界”特性。每个节点有一个簇系数同时有一个度值，那么簇系数和度值就通过节点产生了一个映射关系，记度值为的几个节点的簇系数均值为（），（）与之间的关系称为簇度相关性（）。大量的实证研究表明，许多实际网络，如好莱坞电影演员合作网络、语义网络中节点的簇度相关性存在近似倒数的关系：（）一一。等考虑到真实网络同时具有无标度特性和较大的簇系数，构造了层次网络模型（），该模型中簇度之间呈倒数关系，因此簇度的倒