第二章 网络拓扑基本模型和其性质.ppt

2.2 规则网络 在一个全局耦合网络中， 任意两个点之间都有边直接相连。 因此，全局耦合网络具有最小的 平均路径长度Lgc=1和最大的聚 类系数Cgc=1. 2.3 随机图 假设有大量的纽扣（N1）散落在地上，并以相同的概率P给每对纽扣系上一根线。这样就会得到一个有N个节点，约pN(N-1)/2条边的ER随机图的实例。 随机图理论的一个主要研究课题是：当概率p为多大时，随机图会产生一些特殊的属性？ Erdos和Renyi系统性地研究了当N 时，ER随机图的性质与概率p之间的关系。他们采用如下定义： 如果当N 时产生一个具有性质Q的ER随机图的概率为1，那么就称几乎每一个ER随机图都具有性质Q。 Erdos和Renyi最重要的发现是ER随机图有如下的涌现或变相性质： ER随机图的许多重要的性质都是突然涌现的，也就是说，对于任一给定的概率p，要么几乎每一个图都具有某个性质Q，要么几乎每一个图都不具有该性质。 2.4 小世界网络模型 作为从完全规则网络向完全随机图的过渡，Watts和Strogtz引入了小世界网络模型，称为WS小世界模型。其构造算法如下： 2.5 无标度网络模型 2.5.1 BA无标度网络 近年来在复杂网络研究上的另一个重大发现就是许多复杂网络，包括Internet、WWW以及姓陈代谢网络等的连接度分布函数具有幂律形式。由于这类网络的节点的连接度没有明显的特征长度，故称为无标度网络。 为了解释幂律分布的产生机理，Barabasi和Albert提出了一个无标度网络模型，现被称为BA模型。他们认为以前的许多网络模型都没有考虑到实际网络的如下两个重要特性： 2.6 局域世界演化网络模型 研究表明，许多国家都致力于加强与各自区域经济合作组织内部的国家之间的经济合作和贸易关系。在世界贸易网中，优先连接机制是存在于某些区域经济体中的。类似地，在Internet中，计算机网络是基于域-路由器的结构组织管理的，一台主机通常是只与同一域内的其他主机相连，而路由器则代表它内部域的主机与其他路由器相连。其中优先连接机制不是对整个网络，而是在每个节点各自的局域世界中有效。所有这些都说明在诸多实际的复杂网络中所存在着的局域世界。 在许多现实的网络中，由于局域世界连接性的存在，每一个节点都有各自的局域世界，因而也只占有和使用整个网络的局部连接信息。局域世界演化模型就是用来描述这种情形的。其构造算法如下： 2.7 模块性与等级网络 2.7.1 模块与模体 一般而言，模块是指一组物理上或功能上连接在一起的、共同完成一个相对独立功能的节点。许多实际系统中都包含模块，例如社会网络中的一群朋友或WWW上相似主题的网站等。 在第一章已经指出，与具有相同规模的度分布的随机网络相比，许多实际网络的聚类系数要高的多。网络的高度聚类性表明网络在局部可能包含各种由高度连接的节点组构成的子图。这时出现单个功能模块的一个前提。子图描绘了从局部层次刻画一个给定网络的相互连接的特定模式。 复杂网络可能包含各种各样的子图，如三角形、正方形和五角形等。其中的一些子图所占的比例明显高于同一网络的完全随机化形式中这些子图所占的比例。这些子图就称为模体。 2.8 复杂网络的自相似性 为了判断实际网络中的一个子图i是否为模体，需要产生与实际网络对应得随机化网络以作比较。 判断实际网络中的一个子图i是否为模体的依据如下： ① 该子图在实际网络对应的随机化网络中出现的次数大于它在实际网络中出现次数的概率是很小的，通常要求这个概率小于某个阈值P（如P=0.01）。 ② 该子图在实际网络中出现的次数Nreali不小于某个下限U（如U=4）。 ③ 该子图在实际网络中出现的次数Nreali明显高于高于它在随机化网络中出现的次数Nrandi，一般要求Nreali1.1Nrandi 。 网络模体检测示意图 2.7.2 等级网络 为了说明许多实际系统中同时存在的模块性、局部聚类和无标度拓扑特性，需要假设模块以某种迭代方式生成一个等级网络。研究表明，一些网络中的拓扑模块确实是按等级组织起来的。 * * 第二章 网络拓扑基本模型及其性质 2.1 引言 2.2 规则网络 2.3 随机图 2.4 小世界网络模型 2.