复杂网络基础1(M.Chang)

复杂网络基础理论第一章绪论第一章绪论l1.1引言l1.2网络科学理论发展的三个时期l1.3复杂网络的概念和特性l1.4数理统计基础1.5l1.5图论的基本概念l1.6复杂网络的研究内容和意义l1.7本书内容安排21.1引言网络无处不在：水利网、航海网、公路网、铁路网、信息网、电力网、商业网……网络如此广泛、如此重要。如何开辟出一条研究思路，揭示网络拓扑结构的形成机制，探索网络的演化规律和整体行为，认识网络内部深奥的动力学特性，挖掘网络展现出的广泛、潜在的应用价值等问题，正引起国内外学术界的高度重视。31.1引言21世纪是复杂性和网络化的世纪。从20世纪七八十年代开始，在国际上形成了非线性科学和复杂性问题的研究热潮。尤其是20世纪90年代以来，人类已经生活在一个充满各种各样复杂网络的世界中，许多复杂性问题都充满各种各样复杂网络的世界中，许多复杂性问题都可以从复杂网络的角度去研究。从网络观点重新认识事物并带来革命性变化的典型实例——Google的诞生。它的PageRank算法利用了的网络结构。41.1引言随着生命科学的发展、网络时代的到来以及人们交流和经济活动的全球化，人们早就开始观察和思考生命网络、技术网络、交通网络、社会网络等呈现的一些普遍现象或问题。所有这些问题看上去互不相关，实际上这些都是复杂网络所反映的普遍规律和复杂网实际上这些都是复杂网络所反映的普遍规律和复杂网络领域学者们所要研究的课题。近10年来，复杂网络的研究正渗透到众多不同的学科。推进复杂性科学的交叉研究，深入探索和科学理解复杂网络的定性特征与定量规律，使它获得广泛的应用，对全球科学和社会的发展具有十分重大的长远意义。5返回目录1.2网络科学理论发展的三个时期¢1.2.1规则网络理论阶段¢1.2.2随机网络理论阶段¢1.2.3复杂网络理论阶段61.2.1规则网络理论阶段规则网络理论的发展得益于图论和拓扑学等应用数学的发展。图论是一种强有力的研究工具和研究方法。历史上著名的四个图论问题：1.哥尼斯堡七桥问题1.哥尼斯堡七桥问题哥尼斯堡是当时东普鲁士的首都，今俄罗斯加里宁格勒市，普莱格尔河横贯其中，这条河上建有七座桥，将河中间的两个岛和河岸联结起来，如图所示。有人在闲暇散步时提出：能不能每座桥都只走一遍，最后又回到原来的位置。71.2.1规则网络理论阶段大数学家欧拉用一种独特的方法给出了解答。他把两座小岛和河的两岸分别看作四个点，而把七座桥看作这四个点之间的连线，于是这个问题就简化成：能不能用一笔就把这个图形画出来？经过进一步的分析，欧拉得出结论：不可能每座桥都走一遍，最后回析，欧拉得出结论：不可能每座桥都走一遍，最后回到原来的位置，并且给出了所有能够一笔画出来的图形所应具有的条件。2.哈密顿问题英国数学家哈密顿于1859年以游戏的形式提出：把一个正十二面体的二十个节点看成二十个城市，要求找出一条经过每个城市恰好一次而回到出发点的路线，如图所示。这条路线就称“哈密顿圈”。81.2.1规则网络理论阶段换一种说法，对于一个给定的网络，在确定起点和终点后，如果存在一条路径能够穿过该网络，就称该网络存在“哈密顿路径”。哈密顿路径问题在20世纪70年代初，终于被证明是“NP完备”的，也就是说具有这样性质的问题，难于找到一个有效的算法。实际上对于某些节点数不到100的网络，利用现有最好的际上对于某些节点数不到100的网络，利用现有最好的算法和计算机可能也需要几百年才能确定是否存在一条这样的路径。3.四色猜想1852年，毕业于伦敦大学的格思里来到一家科研单位做地图着色工作时，发现了一个有趣的现象：每幅地图都可以用四种颜色着色，使得有共同边界的国家着上不同的颜色。这个结论能不能从数学上加以严格证明呢？91.2.1规则网络理论阶段1878～1880年两年间，著名的律师兼数学家肯普和泰勒两人分别提交了证明四色猜想的论文，宣布证明了四色定理。但是到了1890年，数学家赫伍德以自己的精确计算指出了肯普的证明存在漏洞，而不久之后，泰勒的证明也被人们否定了。后，泰勒的证明也被人们否定了。进入20世纪以来，随着电子计算机的问世，由于演算速度迅速提高，加之人机对话的出现，大大加快了对四色猜想证明的进程。1976年，美国伊利诺斯大学哈肯和阿佩尔在大学里的两台不同的电子计算机上，用了1200个小时，作了100亿判断，终于完成了四色定理的证明。四色猜想的计算机证明，轰动了世界。它不仅解决了一个历时100多年的难题，而且成为了数学史上一系列新思维的起点。101.2.1规则网络理论阶段4.旅行商问题给定N个节点和任意一对节点{vi，vj}之间的距离为dist（vi，vj），要求找出一条闭合的回路，该回路经过每个节点有且仅有一次，并且该回路的费用最小（这里的费用是指每段路径的距离和）。（这里的费用是指每段路径的距离和）。实际上，旅行商问题就是加权的哈密顿路径问题，因此求解旅行商问题的精确解是NP难的。若将问题限定在欧氏平面上，就称为欧几里德旅行商问题，但是它也是NP难的。因此，通常用来解决TSP问题的解法都是近似算法。第一个欧几里德旅行商问题的多项式近似算法是由Arora于1998年使用随机平面分割和动态规划方法给出的。111.2.2随机网络理论阶段1959年，两个匈牙利著名的数学家Erdös和Rényi建立了著名的随机图理论，用相对简单的随机图来描述网络，简称ER随机图理论。ER随机图理论对图论理论研究的影响长达近40年，以至于在随后的近半个世纪，随机图一直是科学家研究真实网络最有力的武器。纪，随机图一直是科学家研究真实网络最有力的武器。随机网络是指在由N个节点构成的图中以概率p随机连接任意两个节点而成的网络，即两个节点之间连边与否不再是确定的事，而是由概率p决定。或简单地说，在由N个节点构成的图中，可以存在N（N－1）/2条边，从中随机连接M条边所构成的网络就叫随机网络。如果选择M=pN（N－1）/2，则这两种构造随机网络模型的方法就可以联系起来。121.2.2随机网络理论阶段随机图和经典图之间最大的区别在于引入了随机的方法，使得图的空间变得更大，其数学性质也发生了巨大的变化。Erdös和Rényi系统研究了当N→∞时随机图性质与概率p的关系，他们发现：随机网络的许多重要的性质都是随着网络规模的扩大而突然出现的，也就是说对于给定概率p，随着网络规模的扩大，要么也就是说对于给定概率p，随着网络规模的扩大，要么几乎所有的随机图具有某种性质，要么几乎每一个图都不具有该性质。Erdös数：Erdös本人的Erdös数是0；曾与Erdös合作发表过文章的人的Erdös数是1；没有与Erdös合作发表过文章，但与Erdös数为1的人合作发表过文章的人，其Erdös数是2；……几乎每一个当代数学家都有一个有限的Erdös数，而且这个数往往非常小，小得出乎本人的预料。131.2.3复杂网络理论阶段1.小世界效应的发现美国的瓦茨和斯特罗加茨于1998年发表了题为《“小世界”网络的群体动力行为》的论文，推广了“六度分离”的科学假设，提出了小世界网络模型。“六度分离”最早来自于20世纪60年代美国哈佛大学“六度分离”最早来自于20世纪60年代美国哈佛大学心理学家Milgram对社会调查的推断，是指在大多数人中，任意两个素不相识的人通过朋友的朋友，平均最多通过6个人就能够彼此认识。“KevinBacon”游戏复杂网络理论阶段2.社会网络中弱连接优势的发现哈佛大学Granovetter的弱连接优势理论指出：与一个人的工作和事业关系最密切的社会关系并不是“强连接”，而常常是“弱连接”。“弱连接”虽然不如“强连接”那样坚固，却有着极快的、可能具有低如“强连接”那样坚固，却有着极快的、可能具有低成本和高效能的传播效率。而在强连接关系下，成员彼此之间具有相似的态度，他们高度的互动频率通常会强化原本认知的观点而降低了与其它观点的融合，故强连接网络通常不能提供创新机会。相对于强连接关系，弱连接则能够在不同的团体间传递非冗余性的讯息，使得网络成员能够增加修正原先观点的机会。因此，拥有更多弱连接的人拥有信息流通的优势，往往可得到更多工作机会和业务选择机会。151.2.3复杂网络理论阶段3.无标度性质的发现Barabási等人于1999年发表了题为《随机网络中标度的涌现》的论文，提出了一个无标度网络模型，指出在复杂网络中节点的度分布具有幂指数函数的规律（节点的度是指与该节点连接的边数，而度分布是16律（节点的度是指与该节点连接的边数，而度分布是指网络中所有节点的度的分布情况），其度分布可以用幂律形式进行描述。无标度网络中，绝大部分的节点的度相对较低，而存在少量的度相对很高的节点，因此这类网络也成为非均匀网络。大量复杂系统都存在这种少数但高连通的遵循幂律分布的节点，可称为“集散节点”。许多不同的复杂系统，其网络结构都是无标度网络，都是由少数集散节点主控的系统。()Pkkg-µ1.2.3复杂网络理论阶段4.复杂网络研究的新时代对于大量真实的网络系统而言，它们既不是规则网络，也不是随机网络，而是介于两者之间的某种网络。复杂网络研究在过去10年才得到迅速发展，其原复杂网络研究在过去10年才得到迅速发展，其原因有以下几个方面：①计算机技术的迅猛发展。②普适性的发现。③理论研究也有了突破。17返回目录1.3复杂网络的概念和特性¢1.3.1复杂网络的概念¢1.3.2复杂网络的特性181.3.1复杂网络的概念1.系统和网络系统是由相互作用和相互依赖的若干组成部分结合的具有特定功能的有机整体。从三个方面理解系统的概念：①系统是由若干要素（部分）组成的。①系统是由若干要素（部分）组成的。②系统有一定的结构。③系统有一定的功能。系统有如下的属性：集合性、相关性、层次性、整体性、涌现性、对环境的适应性191.3.1复杂网络的概念从图论意义上理解网络，网络是指由节点和连线构成的图。有时用带箭头的连线表示从一个节点到另一个节点存在的某种顺序关系。有时在节点或连线旁标出数值，称为点权或线权，有时不标任何数。标出数值，称为点权或线权，有时不标任何数。网络和系统通常是密切联系的，如果用节点表示系统的各个组成部分即系统的元素，两个节点之间的连线表示系统元素之间的相互作用，那么网络就为研究系统提供了一种新的描述方式。201.3.1复杂网络的概念2.复杂性复杂性还不能算作一个严格的科学概念，人们也没有给出一个公认的复杂性定义。复杂性是相对于简单性而存在的，它是在客观事物的联系、运动和变化中表现出来的一种状态，表达物的联系、运动和变化中表现出来的一种状态，表达了一种不可还原的特征，而不是孤立、静止和显而易见的特性。复杂性科学打破了线性、均衡、简单还原的传统范式，极大地促进了科学的发展。3.复杂系统一般认为复杂系统具有以下特征：非线性与动态性、非周期性和开放性、奇怪吸引性、结构自相似性（分形）。另外，复杂系统还具有突现性、不稳性、不确定性、不可预测性等特征。211.3.1复杂网络的概念4.复杂网络复杂网络可以看作由一些具有独立特征的又与其他个体相互连接的节点的集合，每个个体可视为图中一个节点，节点间的相互连接视为图中的边。复杂网络包括两个层面：作为其连接拓扑结构的图和作为其络包括两个层面：作为其连接拓扑结构的图和作为其状态和功能的系统。钱学森给出了复杂网络的一个较严格的定义：具有自组织、自相似、吸引子、小世界、无标度中部分或全部性质的网络称为复杂网络。原则上说，任何包含大量组成单元（或子系统）的复杂系统，当我们把构成单元抽象成节点，单元之间的相互作用抽象为边时，都可以当作复杂网络来研究。221.3.2复杂网络的特性1.复杂性主要表现在以下几个方面：①网络规模庞大。②连接结构的复杂性。③节点的复杂性。④网络时空演化过程复杂。部分IP地址连接示意图朋友关系网⑤网络连接的稀疏性。⑥多重复杂性融合。231.3.2复杂网络的特性2.小世界特性大多数网络尽管规模很大，但任意两个节点间却有一条相当短的路径。3.无标度特