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

开 题 报 告源代码：请联系本人。论文题目：复杂网络的构建方法研究与实现 院 系： 信息工程学院专 业：遥感科学与技术姓 名： 学 号： 指导老师： 一、研究的目的和意义自然界中存在的大量复杂系统都可以通过形形色色的网络加以描述. 一个典型的网络是由许多节点与连接两个节点之间的一些边组成的,其中节点用来代表真实系统中不同的个体,而边则用来表示个体之间的关系,通常是当两个节点之间具有某种特定的关系时连一条边,反之则不连边。 有边相连的两个节点在网络中被看作是相邻的。 例如,神经系统可以看作是大量神经细胞通过神经纤维相互连接形成的网络;计算机网络可以看作是自主工作的计算机通过通信介质如光缆、双绞线、同轴电缆等相许连接形成的网络. 类似的还有电力网络、社会关系网络、交通网络等等从细菌和蛋白质系统到人类各种关系都是复杂网络，因此，对复杂网络的研究具有重要的意义。 目前而言,科学家们还没有给出复杂网络精确严格的定义,从这几年的研究来看,之所以称其为复杂网络,大致上包含以下几层意思: 首先,它是大量真实复杂系统的拓扑抽象;其次,它至少在感觉上比规则网络和随机网络复杂。复杂网络具有很多与规则网络和随机网络不同的统计特征：（1）平均路径长度：网络的平均路径长度l 则是所有节点对之间距离的平均值, 它描述了网络中节点间的分离程度, 即网络有多小。（2）聚集系数：用来描述网络中节点的聚集情况, 簇系数就是整个网络中所有节点的聚集系数的平均。（3）度分布：图论中节点i 的度为节点i 连接的边的总数目, 所有节点i 的度 的平均值称为网络的平均度。其中最重要的是小世界效应(small-world effect )和无标度特性( scale-free property)。在网络中,簇系数(clustering coefficient)专门用来衡量网络节点聚类的情况。规则网络具有大的簇系数和大的平均距离,随机网络具有小的簇系数和小的平均距离。Newman和Watts给出了一种新的网络的构造方法,在他们的网络(NW 网络) 中,原有的连边并不会被破坏,平均距离的缩短源于以一个很小的概率在原来的规则网络上添加新的连边。后来物理学家把大的簇系数和小的平均距离两个统计特征合在一起称为小世界效应,具有这种效应的网络就是小世界网络。真实网络几乎都具有小世界效应,同时科学家还发现大量真实网络的节点度服从幂率分布,这里某节点的度是指该节点拥有相邻节点的数目,或者说与该节点关联的边的数目。 节点度服从幂律分布就是说,具有某个特定度的节点数目与这个特定的度之间的关系可以用一个幂函数近似地表示。幂函数曲线是一条下降相对缓慢的曲线,这使得度很大的节点可以在网络中存在。 对于随机网络和规则网络,度分布区间非常狭窄,几乎找不到偏离节点度均值较大的点,故其平均度可以被看作是其节点度的一个特征标度.在这个意义上,我们把节点度服从幂律分布的网络叫做无标度网络( scale-free networks) ,并称这种节点度的幂律分布为网络的无标度特性。 复杂网络研究的内容主要包括：网络的几何性质，网络的形成机制，网络演化的统计规律，网络上的模型性质，以及网络的结构稳定性，网络的演化动力学机制等问题。其中在自然科学领域，网络研究的基本测度包括：度及其分布特征，度的相关性，集聚程度及分布特征，最短距离及其分布特征，介数及其分布特征，连通集团的规模分布等等。基于以上的一些特点，以我国气象台站数据为例，以气象台站为网络节点，通过构造小规模的复杂网络，从新视角，新方法分析研究复杂网络的各种特性。二、国内外研究现状自从1998 年Watts 和Strogatz 提出小世界网络模型以来, 复杂网络的研究在过去几年得到了迅速发展。复杂网络研究为探讨复杂系统的性质提供了一个新的视角。原因有以下几个方面: (1) 计算机技术的迅猛发展使我们有可能获得各种大规模网络的统计性质; (2) 实证分析表明, 从万维网到新陈代谢网, 许多领域的各种复杂网络展现了某些共同的统计性质, 如幂律度分布, 表明其中存在一些普适性的概念和规律; (3) 理论研究也有了突破。Watts 和Strogatz 给出了小世界网络的构造方式, Barabasi和Albert 则指出, 增长和偏好连接是形成无标度网络的根本原因, 统计物理学的研究方法在复杂网络研究中得到广泛应用。理论研究和实证分析的相互促进在复杂网络的研究中得到了充分体现。目前,复杂网络的研究工作集中在以下几个方面: (1) 复杂网络拓扑结构的静态统计分析, 包括更广泛的实证研究和更深入的理论刻画, 如给定度分布基础之上的匹配模式, 各种相关关系, 加权网络的统计性质和描述方式, 网络的聚类等; (2) 复杂网络的演化和机制模型, 实证上可以研究实际网络演化的统计规律, 检验BA 模型的偏好连接假设; 理论上则可以发展完善的具有形成特定几何性质的网络机制模型; (3) 复杂网络上的动力学研究, 包括网络容错性和攻击鲁棒性, 以及网络上的传播、同步与共振等各种动力学过程。 近年来复杂网络研究的一个重要的推动力,是网络安全问题。从“九一一”事件到非典,从计算机病毒到电网故障,使人们认识到,网络安全并非只是具体的技术问题,系统和网络的拓扑结构从根本上影响和决定着系统的一系列基本性质,包括鲁棒性、抗毁性。正因为这样,鲁棒性、稳定性、脆弱性、抗毁性等概念已经越来越频繁地出现在各种文献和课题中。吴俊等的“复杂网络抗毁性测度研究”针对复杂网络面临的两种不同损伤,给出了复杂网络抗毁性的两个新测度容错度和抗攻击度,并以世界贸易网为例进行了分析,并对复杂网络抗毁性研究的思路进行了探讨,指出从网络拓扑结构出发,研究拓扑结构的各种属性对网络抗毁性的影响,这将是复杂网络抗毁性研究的一个有效而新颖的思路。关于复杂网络的研究目前正在进一步深入。三、研究内容和技术路线1）研究内容：1. 总结分析国内外学者关于复杂网络的理论研究，并根据开发设计构建一个小规模的复杂网络。2. 以图论，空间分析，网络分析等有关理论原理，以我国气象台站数据为例，以数据台站为网络节点，利用VC实现一个能够分析各种复杂网络特性的小规模复杂网络，尽可能多的实现各种网络分析的功能，以实现分析复杂网络的平均距离，度，最短距离，最优路径，集聚程度等。理解理论知识，提高编程水平。2）技术路线如下：确定复杂网络的功能体系 应用软件工程思想整体设计 采用VC编程实现各种分析功能 不 满 意各种功能完善并通过检验 满意 各种功能完善并通过检验，成型四、研究的主要阶段和进度安排第一阶段（第1周第4周）：广泛查阅国内外文献，完成开题报告；第二阶段（第5周第12周）：完成程序编写；第三阶段（第13周第14周）：撰写论文；第四阶段（第15周第16周）：论文答辩。五、主要参考文献1 孙惠泉 图论及其应用 科学出版社； 2 复杂网络系统结构研究文集；3 2005全国复杂网络学术会议文集；4 郑金连 狄增如 复杂网络研究与复杂现象 北京师范大学5 吴彤 复杂网络研究及其意义 哲学研究2004年第8期6 周涛 柏文洁等 复杂网络研究概述 中国科学技术大学 7人类对于复杂网络的认识 系统工程学报8 韦洛霞 复杂网络模型和方法 东莞理工学院学报9 浦争艳 李明禄 李治洪 复杂网络环境下一种面向对象的最优路径算法研究 上海交通大学信息安全学院10 姜璐 刘琼慧 系统科学与复杂网络研究 北京师范大学11 王林 复杂网络中的社区发现理论与应用 西北工业大学12李泉林复杂网络的拓扑结构、算法和挑战 清华大学工业工程系13 刘丽华 复杂网络简单管理 神州数码网络公司14 覃森 戴冠中 王林 节点数固定的复杂网络模型初探 西北工业大学自动化学院15 刘涛 陈忠 陈晓荣 复杂网络理论及其应用研究概述 上海交通大学目录内容摘要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参考文献致谢内容摘要 近年来,学界关于复杂网络的研究正方兴未艾,特别是小世界网络和无标度网络的提出更是吸引了很多国内外一流的科学家来研究复杂网络。本文谈论了复杂网络研究的意义、内容、复杂网络的统计特征、几何性质、拓扑结构、物理特性等相关的内容,并谈论了复杂网络研究对于社会、科学的巨大作用。最后结合我国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) 的比值。为了描述网络的