2786.复杂网络的构建方法研究与实现【分析代码+开题报告+毕业论文】 .doc

目录内容摘要Abstract第一章 绪论11.1 本文的研究目的和意义11.2 研究进展概述21.3 本文主要研究内容2第二章 复杂网络基本理论的分析与研究42.1 复杂网络的现实状况42.2 复杂网络的基本特征42.3 复杂网络的统计特征62.4 复杂网络的其它性质8第三章 复杂网络模型研究与分析103.1 复杂网络的分类103.2 复杂网络的网络特征参数与性能指标及拓扑结构143.3 复杂网络的几何性质14第四章 复杂网络的物理特性分析164.1 复杂网络的动力学研究164.2 混沌同步164.3 沙堆模型与自组织临界性17第五章 复杂网络的应用分析185.1 复杂网络的社会研究意义185.2 复杂网络的科学研究作用18第六章 用VC实现复杂网络206.1 气象数据e00格式数据的读入与显示206.2 气象站点复杂网络的构建226.3 气象站点复杂网络特性的分析236.4 实验系统的设计与开发25第七章 总结与展望287.1 本文的主要研究工作287.2 存在的问题与今后的研究方向28参考文献致谢30内容摘要 近年来,学界关于复杂网络的研究正方兴未艾,特别是小世界网络和无标度网络的提出更是吸引了很多国内外一流的科学家来研究复杂网络。本文谈论了复杂网络研究的意义、内容、复杂网络的统计特征、几何性质、拓扑结构、物理特性等相关的内容,并谈论了复杂网络研究对于社会、科学的巨大作用。最后结合我国194个气象台站的GIS数据,采用VC编程方法构造了一个小规模的复杂网络,并计算该复杂网络的三个统计特征:度分布、聚集系数和最短路径,还讨论了将其它气象参数作为权值加入网络计算的用途。关键词:复杂网络、度、聚集系数、最短路径、小世界网络、无标度网络、E00数据 AbstractLately,the study of complex network is in the ascendant,especially the advance of Small-World and Scale-Free attract lots of excellence scientists nationally and overseas.the text talk about the meaning,the content,the statistic character,the geometry character,the topology construct and the phystics character of complex network,then also talk about the great societal and scientific effects of the study of complex network.Lastly,I combined the 973 data of weather,adopted the programme method of Visual C+ 6.0, constructed a small complex network,and accounted the three statistic characters:the degree,the coefficient of assemble and the shortest paths of the complex network.And,I also talk about the use of the calculate of the network joined with value of other weather parameters.Keywords:complex network,degree, the coefficient of assemble, the shortest paths,the Small-World,the Scale_Free,the data of E00 第一章 绪论1.1 本文的研究目的和意义 我们人类生活的环境是一个巨大的网络系统,能源、气候、人口、粮食等等都是由一个个复杂而巨大的网络系统构成的。神经网络、交通网络、电力网络、社会关系网络等等在我们生活中无处不在,而我们研究的地理信息系统更是经常涉及到各种复杂的网络系统,我们要处理各种地理信息数据,就应该在深刻认识和掌握复杂网络各种特性的基础上进行,因此我们对复杂网络的研究具有重要的意义。 自然界中存在的大量复杂系统,我们在研究时都可以将它们看成由许多节点和连接节点之间的一些边的网络,其中节点用来表示真实系统中不同的个体,边则用来表示个体之间的关系,通常来说,只有当两个节点之间存在某种特定的关系时才有必要连接一条或多条边,反之则不连边。有边相连的两个节点在网络中被看作是相连的, 例如,神经系统可以看作是大量神经细胞通过神经纤维相互连接形成的网络,计算机网络可以看作是自主工作的计算机通过通信介质如光缆、双绞线、同轴电缆等相互连接形成的网络,同样,在我们研究的GIS领域,目前正时兴的网格GIS更可以看成是一种具有非凡功能的大型的复杂网络系统。 复杂网络的研究,为我们提供了一种复杂性研究的新视角、新方法,并且提供了一种比较的视野,一种宏观与微观结合的方法。我们可以在复杂网络研究的旗帜下,对各种复杂网络进行比较、研究和综合概括,从而服务于我们在GIS领域的各种信息提取,数据挖掘与空间分析。首先，复杂网络的覆盖现象极为广泛，如果我们能够发现一种概括它们的共同特性的观点和方法，或者一种结构，我们就可以提取出这类复杂网络的关键特征来，然后形成深入的认识。小世界、无标度性和高集团度这三个特性正是复杂网络研究过程中被发现的，它们非常好的描述了复杂网络的特性，我们通过研究复杂网络,可以提取出各种过去被我们所忽略的统计特性。其次,随着我们对复杂网络研究的深入，我们在大量网络现象的基础上抽象出两种复杂网络:小世界网络和无标度网络。这两种网络都同时具有两个基本特征:高平均聚集程度和小的最短路径。而无标度网络的度分布又具有幂律分布特征，其复杂性程度要高于小世界网络。高平均聚集程度反映了事物在小世界的境况下自发走向有序的态势，小的最短路径特征反映了演化速度快的特征。还有一种叫做随机网络,这种网络的研究起步很早,研究的科学家也很多。本文就这两个基本特性，研究了GIS领域中我们所涉及到的地理信息数据的处理过程中体现的复杂网络的性质和特性。高平均聚集程度, 小的最短路径等价于我们处理空间信息所涉及的拓扑关系，几何关系等所需要处理的空间关系,我们通过研究复杂网络的特性进而应用于GIS中,为我们提取信息、处理数据、挖掘信息服务。1.2 研究进展概述自从1998 年Watts 和Strogatz 提出小世界网络模型以来, 复杂网络的研究在过去几年得到了迅速发展。复杂网络研究为探讨复杂系统的性质提供了一个新的视角。原因有以下几个方面: (1) 计算机技术的迅猛发展使我们有可能获得各种大规模网络的统计性质; (2) 实证分析表明, 从万维网到新陈代谢网, 许多领域的各种复杂网络展现了某些共同的统计性质, 如幂律度分布, 表明其中存在一些普适性的概念和规律; (3) 理论研究也有了突破。Watts 和Strogatz 给出了小世界网络的构造方式, Barabasi和Albert 则指出, 增长和偏好连接是形成无标度网络的根本原因, 统计物理学的研究方法在复杂网络研究中得到广泛应用。理论研究和实证分析的相互促进在复杂网络的研究中得到了充分体现。 另外,在数学家们研究的基础上,物理学家们不仅在方法论上为网络研究注入了新的活力,而且大大地拓展了网络研究的视野。他们不仅和数学家一样关心网络自身的拓扑性质,而且关注网络上进行的各种物理过程和动力学行为,诸如传播、同步、自组织临界、玻色-爱因斯坦凝聚等等,他们发现了网络拓扑结构对各种动力学行为的影响,并给出了很多虽不严谨但很美妙的解释。 这些工作很有可能会推动相关数学物理理论的发展。而在GIS领域,还没有专门的机构来研究在地理信息方面呈现的复杂网络现象,只是涉及到GIS中的各种网络分析时,路径分析,流分析等,处理各个节点之间的相关性,考虑整体呈现的特征时我们可以从复杂网络的特性出发来研究,这是一个很值得研究的领域。1.3 本文主要研究内容 目前, 复杂网络的研究工作集中在以下几个方面: (1) 复杂网络拓扑结构的静态统计分析, 包括更广泛的实证研究和更深入的理论刻画, 如给定度分布基础之上的匹配模式, 各种相关关系, 加权网络的统计性质和描述方式, 网络的聚类等; (2) 复杂网络的演化和机制模型, 实证上可以研究实际网络演化的统计规律, 检验BA 模型的偏好连接假设; 理论上则可以发展完善的具有形成特定几何性质的网络机制模型; (3) 复杂网络上的动力学研究, 包括网络容错性和攻击鲁棒性, 以及网络上的传播、同步与共振等各种动力学过程。总的来说,网络的结构与功能及其相互关系是网络研究的主要内容, 结构与功能的相互作用特别是其对网络演化的影响是复杂网络研究需要解决的重要的问题。本文在深入学习图论,空间分析,网络分析,复杂网络理论的基础上,以我国气象台站数据为例,以数据台站为网络节点,采用VC实现一个小规模的复杂网络.然后,以GIS中数据处理所涉及的网络分析为例,尽可能多的研究复杂网络的平均路径、节点的度与网络的度、最短路径、集聚程度等。第二章 复杂网络基本理论的分析与研究2.1 复杂网络的现实状况自从1998 年Watts 和Strogatz 提出小世界网络模型以来, 复杂网络的研究在过去几年得到了迅速发展。原因有以下几个方面: (1) 计算机技术的迅猛发展以及网络技术的迅速提高使我们有可能获得各种大规模网络的统计性质; (2)实证分析表明, 从万维网到新陈代谢网, 许多领域的各种复杂网络展现了某些共同的统计性质, 如幂律度分布, 表明其中存在一些普适性的概念和规律; (3) 理论研究也有了突破。Watts 和Strogatz 给出了小世界网络的构造方式, Barabasi和Albert 则指出, 增长和偏好连接是形成无标度网络的根本原因, 统计物理学的研究方法在复杂网络研究中得到广泛应用。另外，很多科学家也正在不断探索复杂网络的其它特性。 目前,科学家们还没有给出复杂网络精确、严格的定义,但从这几年的研究来看,之所以称其为复杂网络,大致上包含以下几层意思: 首先,它是大量真实复杂系统的拓扑抽象;其次,它至少在感觉上比规则网络和随机网络复杂,因为我们可以很容易地生成规则和随机网络,但就目前而言,还没有一种简单方法能够生成完全符合真实统计特征的复杂网络;最后,由于复杂网络是大量复杂系统得以存在的拓扑基础,因此对它的研究被认为有助于理解“复杂系统之所以复杂”这一至关重要的问题。近年来,复杂网络研究的一个重要的推动力是网络安全问题。从“九一一”事件到非典,从计算机病毒到电网故障,使人们认识到,网络安全并非只是具体的技术问题,系统和网络的拓扑结构从根本上影响和决定着系统的一系列基本性质,包括鲁棒性、抗毁性。吴俊等的“复杂网络抗毁性测度研究”针对复杂网络面临的两种不同损伤,给出了复杂网络抗毁性的两个新测度容错度和抗攻击度.并以世界贸易网为例进行了分析,对复杂网络抗毁性研究的思路进行了探讨,指出从网络拓扑结构出发,研究拓扑结构的各种属性对网络抗毁性的影响,这将是复杂网络抗毁性研究的一个有效而新颖的思路。另外,复杂网络研究的领域也正不断扩展,但由于理论与技术的限制,很多具体研究领域的进展不是很明显,但前景很乐观。例如,在GIS领域,在复杂的地理信息数据构成的大型复杂系统中,可以用复杂网络的理论和研究模式,研究方法来处理地理信息数据形成的复杂的拓扑结构以及处理空间分析等目前急需提高的部分。2.2 复杂网络的基本特征 复杂网络具有很多与规则网络和随机网络不同的统计特征,其中最重要的是小世界效应(small-world effect )和无标度特性( scale-free property)。 科学家发现绝大多数实际的复杂网络都具有如下几个基本特征。2.2.1 网络行为的统计性 网络行为的统计性是从整体上来研究和考查一个网络的节点之间的行为所呈现的宏观现象。实际上一个网络中,尤其是一个大型的复杂网络,网络节点数往往是成千上万的,甚至更多,这么大数目的节点聚集在一起,又往往使得大规模性的网络行为具有统计特性。另外在GIS领域,在海量数据组成的复杂网络系统中,我们经常能够发现各种地物间所呈现的相关作用,连锁作用也很普遍,因此,我们可以从整体上考虑各个节点(地物)之间所呈现的网络行为的统计特性,再以此为依据,解决我们所希望得到突破的难题。2.2.2 节点动力学行为的复杂性 在复杂网络中,各个节点还呈现出节点动力学行为的复杂性,即: 各个节点本身可以是个非线性系统,具有分岔和混沌等非线性动力学行为。 而非线性是复杂性的根源，这不仅表现在事物形态结构的无规律分布上，也表现在事物发展过程中的近乎随机变化上。然而，通过混沌理论，我们却可以洞察到这些复杂现象背后的简单性。非线性科学把表象的复杂性与本质的简单性联系起来。另一方面，很多由非线性产生的复杂性往往具有自相似结构或自仿射结构，如何理解这种复杂性与简单性的统一，也得通过对非线性科学的研究来实现。非线性动力学行为是复杂网络的一个比较重要的特性,我们可以通过混沌理论等各种理论研究各个节点之间存在的各种信息,这样,我们在研究GIS中的一些理论时,可以借鉴复杂网络的一些特征理论,从而拓展我们研究的深度和广度。2.2.3 网络连接的稀疏性 一个N个节点的具有全局耦合结构的网络的连接数目为O()，而实际大型网络的连接数目通常为O(N)。在一个复杂网络中,各个节点之间往往并非都能连接,节点的连接状态往往可以体现出整个网络的紧密情况、连通情况。在我们研究GIS时,地物节点之间也经常出现这种情况,节点由于某些客观原因并非像我们所希望的那样满足一些连通、相关等相互作用,为此我们必须精确掌握地物节点之间的实际情况。2.2.4 连接结构的复杂性 网络连接结构既非完全规则也非完全随机。复杂网络既不像规则网络也不像随机网络,故此,它所具有与规则网络,随机网络不同的复杂的连接结构。很多情况下,复杂网络具有规则网络和随机网络中的一些优点,结合两者的长处,并更加合理的形成一个与现实生活更为接近的虚拟的系统。例如我们经常研究的GIS,它就是这样的一个复杂网络,各个地物之间的连接结构我们是否已经完全掌握,我们能否改变我们所需要的一些地物之间的连接结构来满足我们的需要呢,我们能否构造新的结构来重新替代地物之间的连接结构等等问题都需要我们不断深入的研究来实现。2.2.5 网络的时空演化的复杂性 复杂网络具有空间和时间的演化复杂性, 展示出丰富的复杂行为, 特别是网络节点之间的不同类型的同步化运动（包括出现周期、非周期混沌和阵发行为等运动）。复杂网络随着时间和空间的改变也时刻发生着变化,我们处理的GIS也是这样。一切都随时空的改变而改变,我们能否很好的把握住复杂网络的演化方向和程度,取决于我们能否很好的掌握其时空演化的复杂性,能积累足够的理论和实践经验来跟踪、监控或者随机应变,这些都还很不成熟,还需要我们进一步研究。例如,GIS中的海量数据随着时空的变化,信息不断的更新,整个网络系统不断变化,我们就有必要把握各地物的演化的行为的复杂性,这样才能尽可能做到实时、快捷,来满足我们生活和工作对于GIS更高的要求。 而网络的时空演化的复杂性,又是一个比较综合的课题,需要数学(尤其是图论) 、物理学、计算机网络学、生物进化学等等学科综合来研究.而我们GIS领域可以吸取其它学科的研究成果,结合我们的学科特点,实际地研究我们需要解决的问题,进而推动复杂网络研究取得更进一步的进展。 以上5种特征，反映了实际复杂网络的复杂性特征。一方面，它具有无序演化的特征，另一方面，它也具有增加有序程度的演化特征。它具有分形和混沌的特征，具有自组织演化的特征，也具有形成序参量的特征。因此，复杂网络的研究会综合以往的各种自组织理论、非线性和复杂性理论研究的成果，从而形成新的复杂性研究机制的理论。这些都需要我们进一步的探索,以期取得尽快的进展,服务于其它学科与我们的生活。2.3复杂网络的统计特征用网络的观点描述客观世界起源于1736 年德国数学家Eular 解决哥尼斯堡七桥问题。复杂网络研究的不同之处在于首先从统计角度考察网络中大规模节点及其连接之间的性质, 这些性质的不同意味着不同的网络内部结构, 而网络内部结构的不同导致系统功能有所差异。所以,对这些统计性质的描述和理解是我们进行复杂网络相关研究的第一步, 下面简述之。2.3.1 平均路径长度在网络研究中, 一般定义两节点间的距离为连接两者的最短路径的边的加权的路径和; 网络的直径为任意两点间的最大距离; 网络的平均路径长度l 则是所有节点对之间最短路径的平均值, 它描述了网络中节点间的分离程度, 即网络有多小。复杂网络研究中一个重要的发现是绝大多数大规模真实网络的平均路径长度比想象的小得多, 称之为“小世界效应”。这一提法来源于著名的 Milgram“小世界”试验,试验要求参与者把一封信传给他们熟悉的人之一, 使这封信最终传到指定的人, 籍此来探明熟人网络中路径长度的分布, 结果表明平均传过人数仅为六, 这一试验也正是流行的“六度分离”概念的起源。通过一些通信试验，人们发现，平均来说，世界上任何两个人之间可以仅仅通过6对朋友关系连接起来, 这就是我们俗称的“小世界”。最短路径对于我们GIS行业来说具有非常重要的作用,路径加权,最优路径,流分析等等都必须涉及到复杂网络的整体情况,就需要我们根据实际情况,先从模型出发,研究出一套最佳方案,再经过调查研究,实地考证等步骤,才能实现我们的目标.例如,最近的酒店、厕所、车站等等与我们日常生活密切相关的场所我们通过研究网络特性,然后将其纳入GIS系统,并随着网络的更新不断改变系统,使其满足我们生活的需要。2.3.2 聚集系数 聚集系数C 用来描述网络中节点的聚集情况, 即网络有多紧密, 比如在社会网络中, 你朋友的朋友可能也是你的朋友或者你的两个朋友可能彼此也是朋友。其计算方法为: 假设节点i 通过 条边与其它个节点相连接,如果这个节点都相互连接, 它们之间应该存在* (-1)/2 条边, 这是一种理想的状态,而这个节点之间实际存在的边数只有的话, 则它与* (- 1)/2 之比就是节点i 的聚集系数。而网络的聚集系数就是整个网络中所有节点的聚集系数的平均。显然, 只有在全连通网络(每个节点都与其余所有的节点相连接) 中, 聚集系数才能等于1, 一般均小于1。在完全随机网络中, C:, 然而实证结果却表明大部分大规模真实网络中的节点倾向于聚集在一起, 尽管聚集系数C 远远小于1, 但都远比大。 具体来说,顶点聚集系数用来描述网络局部集团化的程度. 对于每一个人(顶点V ) , 考察他的所有朋友, 这些朋友互相之间还是不是朋友的情况由集聚系数来度量。若这些朋友互相之间都不再熟识, 则原顶点的集聚系数为0; 反之, 若这些朋友互相之间都有边相连, 即它们互相之间都有朋友关系, 则原顶点的集聚系数为1。所有顶点的集聚系数的平均值称为平均集聚系数。2.3.3 度分布图论中节点i 的度 为节点i 连接的边的总数目, 所有节点i 的度的平均值称为网络的平均度, 定义为< k> 。网络中节点的度分布用分布函数p (k ) 来表示, 其含义为一个任意选择的节点恰好有k 条边的概率, 也等于网络中度数为k 的结点的个数占网络结点总个数的比值。 2.4复杂网络的其它性质 随着研究的深入, 人们逐渐发现真实网络还具有一些其它重要的统计性质. 下面简述之。2.4.1 网络弹性网络的功能依赖其节点的连通性, 我们称网络节点的删除对网络连通性的影响为网络弹性, 其分析有两种方式随机删除和有选择的删除,前者称为网络的鲁棒性分析, 后者称为网络的脆弱性分析。Albert等人分别对度分布服从指数分布的随机网络模型和度分布服从幂律分布的BA网络模型进行了研究. 结果显示: 随机删除节点基本上不影响BA 网络的平均路径长度, 相反, 有选择的删除节点后,BA 网络的平均路径长度较随机网络的增长快得多。这表明,BA 模型相对随机网络具有较强的鲁棒性和易受攻击性。出现上述现象的原因在于幂律分布网络中存在的少数具有很大度数的节点在网络连通中扮演着关键角色, 一般也称它们为Hub节点。幂律分布指的是一种能用幂函数来表示的分布形式。2.4.2 介数介数分为边介数和节点介数。节点的介数为网络中所有的最短路径中经过该节点的数量比例; 边的介数含义类似。介数反映了相应的节点或者边在整个网络中的作用和影响力, 具有很强的现实意义。例如, 在社会关系网络或技术网络中, 介数的分布特征反映了不同人员、资源和技术在相应生产关系中的地位, 这对于在网络中发现和保护关键资源和技术具有重要意义。2.4.3 度与聚集系数之间的相关性 网络中度和聚集系数之间的相关性被用来描述不同网络结构之间的差异, 它包括两个方面不同度数节点之间的相关性和节点度分布与其聚集系数之间的相关性。前者指的是网络中与高度数(或低度数) 节点相连接的节点的度数偏向于高还是低; 后者指的是高度数节点的聚集系数偏向于高还是低。实证表明, 在社会网络(演员合作网络、公司董事网络、电子邮箱网络) 中节点具有正的度的相关性, 而节点度分布与其聚集系数之间却具有负的相关性; 其它类型的网络(信息网络、技术网络、生物网络) 则相反。正因为如此, 这两种相关性被认为是社会网络区别于其他类型网络的重要特征, 在社会网络研究中引起了高度重视。2.4.4 网络的社区结构复杂网络的另外一个重要特征就是网络中所呈现出的社区结构。大量实证研究表明:许多网络是异构的,即复杂网络不是一大批性质完全相同的节点随机地连接在一起的,而是许多类型的节点的组合。 相同类型的节点之间存在较多的连接, 而不同类型的节点之间的连接则相对较少。我们把满足同一类型中的节点以及这些节点之间的边所构成的子图称为网络中的社区。在大型复杂网络中自动搜寻或发现社区, 具有重要的实用价值。 如社会网络中的社区代表根据兴趣或背景而形成的真实的社会团体。万维网中的社区就是讨论相关主题的若干网站;而生物化学网络或者电子电路网络中的社区可以是某一类功能单元; 发现这些网络中的社区有助于我们更加有效地理解和开发这些网络。与社区发现相关的理论包括图论、模式识别等。复杂网络中社区发现的研究起源于社会学的研究工作和以及和的研究成果, 使得复杂网络中的社区发现成为近几年复杂网络领域的一个研究热点并形成了复杂网络中一个重要的研究方向。尽管复杂网络的社区发现问题得到了大量的研究, 但还存在一些尚未解决的基本问题.如社区概念虽然大量使用,但却缺少严格的数学定义。 大多数社区发现算法虽然性能优越,但所需计算量却很大, 这说明复杂网络中社区发现的研究还需要付出大量的努力。第三章 复杂网络模型研究与分析3.1 复杂网络的分类3.1.1 经典随机网络经典的随机网络是这样构造的: 给定N 个顶点, 任意两点之间都尝试以某个概率p 连接, 所构成的网络就叫随机网络。数学家在上个世纪50 年代对随机网络进行了深入细致的研究, 得到了网络性质突现的临界连接概率等一系列结果, 发现对于同样规模的网络, 随机网络具有短的平均最短路径, 这一点和许多实证研究结果相符。但另一方面, 许多实际网络都具有很高的平均集聚系数, 而随机网络却是一个局部集团化很差的网络, 平均集聚系数很低。所以, 随机网不是实际网络的一个很好的刻画。和随机网络相对应的是完全规则网, 如一维链或二维平面上的规则网络。规则网络的性质恰与随机网相反, 一般情况下具有大的集聚系数和长的平均最短路径。所以，无论是规则网络还是随机网络都无法作为描述真实网络的合适的研究基础。或者说, 把规则晶格和随机网络作为复杂系统的抽象都过于简单化了, 离真实的复杂性太远。3.1.2 小世界网络 Watts 和Strogatz结合规则网和随机网的特点, 给出了小世界网的生成机制模型。小世界网络是在规则网络的基础上加入随机性产生的, 即对规则网络的每一个顶点的所有边, 以概率p 断开一个端点, 并重新连接, 连接的新端点从网络中的其他顶点里随机选择, 如果所选的顶点已经与此顶点相连, 则再随机选择别的顶点来重连。其生成方法见图1，其中左图为规则网络，右图为随机网络,中间是一个典型的Small-World 网络。p = 0 时就是规则网络, p = 1 时为随机网络, 对于0< p < 1 的情况, p 值存在一个很大的区域, 网络同时拥有大集聚程度和小最短路径, 如图3.1 所示。在复杂网络研究中, 网络同时具备这两个性质时我们就称其具有小世界特性。 图3.1 小世界网络模型, 图中中间的小世界网络是在左图的规则网络基础上通过边的重连得到的。p 为每一条的重连几率。实证结果表明, 大多数的真实网络具有小世界性(较小的最短路径) 和聚集性(相对较大的聚集系数), 见下表3-1所示。表3-1实际网络的Small-world 现象注: 下标rand 为随机网络模型下的计算, 通过对比实际网络与相应随机网络(相同的节点数和边数) 的性质, 可以发现真实网络具有小世界和较高聚集系数的性质。图3.2 小世界网络的几何性质图。小世界网络同时有大集聚程度而小最短路径, 而且此性质在p 略大于0 到小于1 的很大范围内存在。图中, 横坐标为重连的概率, 为了方便, 数据已经做对数处理; 纵坐标为平面集聚程度和最短路径与对应的规则网络的集聚程度的C (0) 和最短路径L (0) 的比值。为了描述网络的小世界特性, 我们将上图中的两个量平均集聚程度和最短路径联系起来定义成一个量CL (p ) =（C (p ) /C (0) ） / L (p ) /L (0)）, 该量随重连概率p 的变化如下图所示。从图上可以看到, 在概率约为0. 08 时, CL (p ) 出现一个峰值, 在峰值左右的一个比较大的p 范围内, CL (p ) 都比较大, 在p 靠近0和1 两端时, CL (p ) 非常小, 所以, 我们可以用CL (p )来度量网络的小世界特性, 而这一特性来源于规则性和随机性之间。 图3.3基于图3.2 的CL (p ) 散点图,横坐标概率p 已经作对数处理3.1.3 无标度网络 除了小世界特性外,大量实际网络还存在着另一个突出的结构特征幂律度分布, 我们称其为无标度网络。无标度网络的特点是度分布的自相似结构及其高度弥散性。网络中的大部分节点度值都很低, 但存在着度数非常高的中枢节点。幂律度分布使网络在小世界特征的基础上又具有了许多新的性质。如不存在传染病传播的临界阈值等。对网络攻击的研究结果表明, 随机攻击基本上不会破坏无标度网络的连通性, 但在有目的的最大度攻击下, 很小比例的顶点移除就会对网络的连通性造成根本性的破坏。鲁棒性和脆弱性奇妙地结合在了一起,这与现实世界中许多复杂系统的表现完全类似。Barabasi 和Albert 提出了一个经典的无标度网络演化机制模型, 指出网络增长和偏好连接是产生幂律度分布上的根本原因。在已有的网络基础上不断有新的顶点加入, 每个新顶点加入时都要有m 条边与已有顶点相连, 但连接到某个顶点的概率与该顶点的度值成正比, 这样就可以形成一个幂律指数为- 3 的无标度网络, 且与初始分布和m 值无关。小世界网络的形成机制是从规则网络开始, 加入某些随机性; 而在无标度网络的BA 模型形成机制中, 则是在完全随机的基础上加上一些确定性不平权的偏好连接概率。这又一次为复杂性来源于规则性和随机性之间提供了例证。 幂律分布相对于指数分布其图形没有峰值, 大多数节点仅有少量连接, 而少数节点拥有大量连接, 不存在随机网络中的特征标度, 于是Barabási 等人称这种度分布具有幂律特征的网络为Scale-free 网络。为解释Scale-free 网络的形成机制, Barabási 和Albert 提出了著名的BA 模型, 他们认为以前的网络模型没有考虑真实网络的两个重要性质增长性和择优连接性, 前者意味着网络中不断有新的节点加入进来, 后者则意味着新的节点进来后优先选择网络中度数大的节点进行连接。他们不仅给出了BA 模型的生成算法并进行了模拟分析, 而且还利用统计物理中的平均场方法给出了模型的解析解,结果表明: 经过充分长时间的演化后, BA 网络的度分布不再随时间变化, 度分布稳定为指数为3 的幂律分布。BA 模型的提出是复杂网络研究中的又一重大突破,标志着人们对客观网络世界认识的深入。之后, 许多学者对这一模型进行了改进, 如非线性择优连接、加速增长、重绕边的局域事件、逐渐老化、适应性竞争等等。需要注意的是, 绝大多数而不是所有的真实网络都是Scale-free 网络, 如有的真实网络度分布为指数分布截断形式等等。实证结果却表明对于大多数大规模真实网络用幂律分布来描述它们的度分布更加精确, 即P (k) k - C, 见表3-2 所示。表3-2实际网络的Scale-free 现象注: 下标out、in 分别表示出度和入度的幂律分布指数, 可见很多网络的度分布具有幂律特征。下标real、rand 和pow 分别表示真实网络、随机网络模型和Scale-free 网络模型中计算的平均路径长度。 3.2 复杂网络的网络特征参数与性能指标及拓扑结构 复杂网络的性能指标可以通过最短路径、顶点的聚集系数、网络的聚集系数,度分布等来描述网络恢复、网络增长与进化、网络过程等与网络拓扑相关的参数体现出来.而在复杂网络的信息流交换等过程中的稳态输出率、输出量方差、响应时间、延误时间、满意概率、可靠性、安全性、单元利用率等可以很好的描述一个复杂网络的整体情况、它的性能、它能给人们带来的影响等等.3.3 复杂网络的几何性质 相对于复杂网络的动力学行为,本小节将小结一下复杂网络的几何性质,也即静态几何性质,并用静态几何量来描述。静态几何量指的是给定网络G = ( V , E) 的微观量的统计分布或者宏观统计平均值。由于有向网络与加权网络有其特有的几何量,将分开讨论无向网络,有向网络与加权网络。 无向网络的基本几何量有:度及其分布特征、度的相关性、集聚程度及其分布特征、最短距离及其分布特征,介数(Betweenness) 及其分布特征,连通集团的规模分布。这些概念和作用前面都已经介绍过。目前已得到研究的典型有向网络包括:WWW 网络,细胞内化学反应网络,食物链网络、引文网络、电力网络、神经网络等。当我们忽略边的方向的时候,或者反过来看认为任何一条边都是双向的时候,有向网络就成为无向网络。因此,关于无向网络的所有几何量都可以在有向网络中研究。有向网络的特殊静态几何量包括: In 度和Out 度的分布特征、基于顶点的In-Out 度关联性、基于边的(In-Out , In- In ,Out- In ,Out-Out) 度关联性、双向比、In 集团和Out 集团的集聚程度。我们把无向网络的度推广为In 度和Out 度，以及可分别研究In 度和Out 度的分布特征。实证研究表明,有向网络中存在In 度和Out 度的双向幂律分布,如WWW网络,细胞内化学反应网络;但是也存在只有In度幂律分布的网络,如引文网络;以及符合指数衰减的网络,如电力网络与神经网络;此外,由于受顶点数规模限制,食物链网络的度分布特征仍然没有确定。由于每一个有向网络的顶点都存在In 与Out 两个度值,研究这两个度值之间的关联将是有向网络的另一个重要特征。与无向网络的度相关类似,我们可以研究有向网络基于边的度相关。任意选取一条边,在边的两端存在4 个度值,起点的In 度和Out 度,终点的In 度和Out 度,所以存在4 种关联性,分别是In- In , In-Out ,Out- In ,Out-Out 关联。有向网络的度相关性正是建立反馈机制的重要参考。加权网络的静态几何量包括:度及其分布特征、权及其分布特征、权的相关性、权与度的相关性、最短距离及其分布特征、介数及其分布特征与隧道现象与相应无权网络的对比、距离关系与类聚分析以及在加权网络上集聚程度的定义及其统计性质。首先加权并不改变度与集聚程度等局域几何量,所以无权网络的局域几何量分析都可以在加权网络上实现。例如，对于引文网络来说，权的分布反映的是本领域内学术交流的活性,如果我们认为所有学术研究都将表现为文献发表与学术交流的话,那么它反映的是此领域内学术研究的活跃程度。第四章 复杂网络的物理特性分析 对于物理学家而言,研究复杂网络的终极目标是理解网络拓扑结构对物理过程的影响。 在以前的研究中,物理学家往往忽略了网络的拓扑性质,在讨论逾渗、传播、同步等物理过程时,他们自然地选择了最容易模拟和分析的规则网络或随机网络,而没有仔细思考和研究这种选择是不是应该的,不同的选择会不会对物理过程产生不可忽略的影响。 以网络上的传播动力学模型为例,由于传统的网络传播模型大都是基于规则网络的,因此,复杂网络不同统计特征的发现使科学家面临更改既有结论的危险。当然,如果理论研究和实验结果都说明复杂网络上的传播动力学行为与规则网络别无二致,那么我们至少暂时还可以使用以前的结论。但是,不幸的是,复杂网络上的传播行为与规则网络相比确实存在根本上的不同。类似的情况还出现在其他的物理过程中,下面我们将简略地介绍网络拓扑性质对某些典型物理过程的影响。4.1 复杂网络的动力学研究 复杂网络的动力学的一个典型是疾病传播动力学。疾病在网络中的平均波及范围与疾病的传染强度正相关,而疾病的传染强度有一个阈值,只有当其值大于这个阈值时,疾病才能在网络中长期存在,否则感染人数会呈指数衰减。根据这个理论,疾病若是持久存在,则必然波及大量个体。但实验研究表明,计算机病毒、麻疹等一般仅波及少数个体但能够长期存在。这一理论与实验的矛盾在很长时间里一直困扰着科学界。 近年来的研究表明,在无标度网络中,没有正的传播阈值,也就是说,即使疾病的传染强度接近零,只波及非常少的个体,也能在网络中长期存在。由于大部分真实网络是无标度网络,因此该结论很好地解决了上面的矛盾。4.2 混沌同步近十余年来,混沌动力系统在网络上的同步性能吸引了大量科学家的关注。 早期的研究主要是针对以最近邻环网为代表的规则网络,研究表明,对于给定的非零耦合强度,当节点数目很大时,网络无法实现同步。 最近几年的研