网络拓扑基本模型及其性质

2.1引言

要理解网络结构与网络行为之间的关系，并进而考虑改善网络的行为，就需要对实际的网络的结构特征有很好的了解，并在此基础上建立合适的网络结构模型。本章介绍几类基本的模型，包括规则网络、随机图、小世界网络、无标度网络、等级网络和局域世界演化网络模型。此外，进一步介绍复杂网络的模块化和自相似性等特征。现在是1页\一共有41页\编辑于星期三2.2规则网络

在一个全局耦合网络中，任意两个点之间都有边直接相连。因此，全局耦合网络具有最小的平均路径长度Lgc=1和最大的聚类系数Cgc=1.现在是2页\一共有41页\编辑于星期三

最近邻耦合网络中每一个节点只和周围的邻居节点相连。具有周期边界条件的最近邻耦合网络包含N个围成一个环的点，其中每个点都与它左右各K/2个邻居节点相连，这里K是一个偶数。对于较大K值，最近邻耦合网络的聚类系数为：Cnc=

因此这样的网络是高度聚类的。然而，最近邻耦合网络不是一个小世界网络，相反对固定的K值，该网络的平均路径长度为：

Lnc现在是3页\一共有41页\编辑于星期三

星形耦合网络，它有一个中心点，其余的N-1个点都只与这个中心点连接，而他们彼此之间不连接。星形网络的平均路径长度为：

Lstar=星形网络的聚类系数为：

Cstar=现在是4页\一共有41页\编辑于星期三2.3随机图

假设有大量的纽扣（N>>1）散落在地上，并以相同的概率P给每对纽扣系上一根线。这样就会得到一个有N个节点，约pN(N-1)/2条边的ER随机图的实例。（a）p=0,给定的10个孤立点；（b）~（d）分别以连接概率p=0.1、p=0.15和p=0.25生成的随机图（a）（b）（c）（d）现在是5页\一共有41页\编辑于星期三

随机图理论的一个主要研究课题是：当概率p为多大时，随机图会产生一些特殊的属性？

Erdos和Renyi系统性地研究了当N时，ER随机图的性质与概率p之间的关系。他们采用如下定义：如果当N时产生一个具有性质Q的ER随机图的概率为1，那么就称几乎每一个ER随机图都具有性质Q。

Erdos和Renyi最重要的发现是ER随机图有如下的涌现或变相性质：

ER随机图的许多重要的性质都是突然涌现的，也就是说，对于任一给定的概率p，要么几乎每一个图都具有某个性质Q，要么几乎每一个图都不具有该性质。

现在是6页\一共有41页\编辑于星期三

ER随机图平均路径长度为:LER∝lnN/ln<k>。这种平均路径长度为网络规模的对数增长函数的特性就是典型的小世界特征。ER随机图的聚类系数是:C=p=<k>/N<<1，这意味着大规模的稀疏ER随机图没有聚类特性。固定ER随机图的平均度<k>不变，则对于充分大的N，由于每条边出现与否都是独立的，ER随机图的度分布可以用Poission分布来表示:P(k)=pk(1-p)N-k现在是7页\一共有41页\编辑于星期三2.4小世界网络模型作为从完全规则网络向完全随机图的过渡，Watts和Strogtz引入了小世界网络模型，称为WS小世界模型。其构造算法如下：①从规则图开始：考虑一个含有N个点的最近邻耦合网络，它们围成一个环，其中每个节点都与它左右相邻的各K/2节点相连，K是偶数。②随机化重连：以概率p随机地重新连接网络中的每个边，即将边的一个端点保持不变，而另一个端点取为网络中随机选择的一个节点，其中规定，任意两个不同的节点之间至多只能有一条边，并且每一个节点都不能有边与自身相连。现在是8页\一共有41页\编辑于星期三在上述模型中，p=0对应于完全规则网络，p=1则对应于完全随机网络，通过调节p的值就可以控制从完全规则网络到完全随机网络的过渡，如下图所示。这类既具有较短的平均路径长度又具有较高的聚类系数的网络就称为小世界网络现在是9页\一共有41页\编辑于星期三WS小世界模型构造算法中的随机化过程可能破坏网络的连通性。另一个研究较多的小世界模型是由Newman和Watts提出的NW小世界模型。该模型是通过”随机化加边”取代WS小世界模型中的随机化重连而得到的。具体的构造算法如下：①从规则图开始：考虑一个含有N个点的最近邻耦合网络，它们围成一个环，其中每个节点都与它左右相邻的各K/2节点相连，K是偶数。②随机化重连：以概率p在随机选取的一对节点之间加上一条边。其中，任意两个不同的节点之间至多只能有一条边，并且每一个节点都不能有边与自身相连。现在是10页\一共有41页\编辑于星期三在NW小世界模型中，p=0对应于原来的最近邻耦合网络，p=1对应于全局耦合网络。下面介绍小世界网络模型的一些统计性质。现在是11页\一共有41页\编辑于星期三1.聚类系数WS小世界网络的聚类系数为：NW小世界网络的聚类系数为：2.平均路径长度迄今为止，人们还没有关于WS小世界模型的平均路径长度L的精确解析表达式，不过，利用重正化群的方法可以得到如下公式：现在是12页\一共有41页\编辑于星期三其中f(u)为一普适标度函数，满足Newman等人基于平均场方法给出了如下的近似表达式：但目前为止还没有f(u)的精确显示表达式。现在是13页\一共有41页\编辑于星期三3.度分布在基于“随机化加边”机制的NW小世界模型中，每个节点的度至少为K。因此当k>>K时，一个随机选取的节点的度为k的概率为：而当k<K时P(k)=0.对于基于“随机化重连”机制的WS小世界模型，当k>=K/2时有：而当k<K/2时P(k)=0。类似于ER随机图模型，WS小世界模型也是所有节点的度都近似相等的均匀网络。现在是14页\一共有41页\编辑于星期三2.5无标度网络模型2.5.1BA无标度网络

近年来在复杂网络研究上的另一个重大发现就是许多复杂网络，包括Internet、WWW以及姓陈代谢网络等的连接度分布函数具有幂律形式。由于这类网络的节点的连接度没有明显的特征长度，故称为无标度网络。为了解释幂律分布的产生机理，Barabasi和Albert提出了一个无标度网络模型，现被称为BA模型。他们认为以前的许多网络模型都没有考虑到实际网络的如下两个重要特性：现在是15页\一共有41页\编辑于星期三①增长特性：即网络规模是不断扩大的。例如每个月都会有大量的新的科研文章发表，而WWW上则每天有大量新的网页产生。②优先连接特性：即新的节点更倾向于与那些具有较高连接度的“大”节点相连接。这种现象也被称为“富者更富”或“马太效应”。例如新发表的文章更倾向于引用一些已被广泛引用的重要文献，新的个人主页上的超文本链接更有可能指向新浪、雅虎等著名的站点。基于网络的增长和优先连接特性，BA无标度网络模型的构造算法如下：

现在是16页\一共有41页\编辑于星期三①增长：从一个具有m0个节点的网络开始，每次引入一个新的节点，并且连接到m个已存在的节点上，这里m<=m0。②优先连接：一个新节点与一个已经存在的节点i相连接的概率与节点i的度ki、节点j的度kj之间满足如下关系：在经过t步后，这种算法产生一个有N=t+m0个节点、mt条边的网络。BA无标度网络的演化(m=m0=2)现在是17页\一共有41页\编辑于星期三1.平均路径长度BA无标度网络的平均路径长度为：这表明该网络具有小世界特性。2.聚类系数BA无标度网络的聚类系数为：这表明与ER随机图类似，当网络规模充分大时BA无标度网络不具有明显的聚类特征现在是18页\一共有41页\编辑于星期三3.度分布BA网络的度分布函数为：这表明BA网络的度分布函数可由幂指数为3的幂律函数近似描述。2.5.2鲁棒性与脆弱性对于一个给定的网络，如果在移走少量节点后网络中的绝大部分节点仍是连通的，那么就称该网络的连通性对节点故障具有鲁棒性现在是19页\一共有41页\编辑于星期三去除节点对网络连通性的影响现在是20页\一共有41页\编辑于星期三下面比较ER随机图和BA无标度网络的连通性对节点去除的鲁棒性。现考虑两种去除策略：一是随机故障策略，即完全随机地去除网络中的一部分节点；二是蓄意攻击策略，即从去除网络中度最高的节点开始，有意识地去除网络中一部分度最高的节点。假设去除的节点数占原始网络总节点数的比例为f，可以用最大连通子图的相对大小S和平均路径长度l与f的关系来度量网络的鲁棒性。研究发现，ER随机图和BA无标度网络之间存在极其显著的差异。无标度网络对随机节点故障具有极高的鲁棒性：与随机图相比，最大连通子图的相对大小在相对高得多的f时才下降到零，而其平均路径长度的增长则要缓慢得多。无标度网络的这种对随机故障的高度鲁棒性，来自于网络度分布的极端非均匀性：绝大多数节点的度都相对很小，而有少量节点的度相对很大。然而正是这种非均匀性使得无标度网络对蓄意攻击具有高度的脆弱性：只要有意识地去除网络中极少量度最大的节点就会对整个网络的连通性产生大的影响。现在是21页\一共有41页\编辑于星期三方块对应随机故障，圆点对应蓄意攻击现在是22页\一共有41页\编辑于星期三现在是23页\一共有41页\编辑于星期三2.5.3适应度模型BA无标度模型把实际复杂网络的无标度特性，归结为增长和优先连接这两个非常简单明了的机制。但这也不可避免地使BA无标度网络模型和真实网络相比存在一些明显的限制。例如，BA模型只能生成度分布的幂律指数固定为3的无标度网络，而各种实际的复杂网络的幂律指数则不甚相同，而且大都属于2至3的范围内。此外，实际网络常常具有一些非幂律特征。在BA无标度网络的增长过程中，节点的度也在发生变化并且满足如下幂律关系：现在是24页\一共有41页\编辑于星期三其中，ki(t)为第i个节点在时刻t的度，ti是第i个节点加入到网络中的时刻。上式表明，在BA无标度网络中，越老的节点具有越高的度。然而在许多实际网络系统中，节点的度及其增长速度并非只与该节点的年龄有关。。例如，社会关系网络中的某些人具有较强的交友能力，他们可以较为容易地把一次随机相遇变为一个持续的社会连接。显然，这些例子都是与节点的内在性质相关的。Bianconi和Barabasi把这一性质称为节点的适应度，并提出了适应度模型，其构造算法如下：①增长：从一个具有m0个节点的网络开始，每次引入一个新的节点，并且连接到m个已存在的节点上，这里m<=m0。每个节点的适应度按概率分布选取。②优先连接：一个新节点与一个已经存在的节点i相连接的概率∏i与节点i的度ki、节点j的度kj和适应度之间满足如下关系：现在是25页\一共有41页\编辑于星期三2.6局域世界演化网络模型研究表明，许多国家都致力于加强与各自区域经济合作组织内部的国家之间的经济合作和贸易关系。在世界贸易网中，优先连接机制是存在于某些区域经济体中的。类似地，在Internet中，计算机网络是基于域-路由器的结构组织管理的，一台主机通常是只与同一域内的其他主机相连，而路由器则代表它内部域的主机与其他路由器相连。其中优先连接机制不是对整个网络，而是在每个节点各自的局域世界中有效。所有这些都说明在诸多实际的复杂网络中所存在着的局域世界。在许多现实的网络中，由于局域世界连接性的存在，每一个节点都有各自的局域世界，因而也只占有和使用整个网络的局部连接信息。局域世界演化模型就是用来描述这种情形的。其构造算法如下：现在是26页\一共有41页\编辑于星期三①增长：网络初始时有m0个节点和e0条边。每次新加入一个节点和附带的m条边。②局域世界优先连接：随机地从网络已有的节点中选取M个节点（M>=m），作为新加入节点的局域世界。新加入的节点根据优先连接概率来选择与局域世界中的m个节点相连接，其中LW由新选的M个节点组成。显而易见，在t时刻，m<=M<=m0+t。因此上述局域世界演化模型有两个特殊的情形：M=m和M=m0+t。现在是27页\一共有41页\编辑于星期三（1）特殊情形A：M=m这时，新加入的节点与局域世界中所有的节点相连接，这意味着在网络增长过程中，优先连接原则实际上已经不发挥作用了。这等价于BA无标度网络模型中只保留增长机制而没有优先连接机制。网络度分布服从指数分布：（2）特殊情形B：M=t+m0在这种特殊情形，每个节点的局域世界其实就是整个网络。因此，局域世界模型此时完全等价于BA无标度网络模型。现在是28页\一共有41页\编辑于星期三2.7模块性与等级网络

2.7.1模块与模体

一般而言，模块是指一组物理上或功能上连接在一起的、共同完成一个相对独立功能的节点。许多实际系统中都包含模块，例如社会网络中的一群朋友或WWW上相似主题的网站等。在第一章已经指出，与具有相同规模的度分布的随机网络相比，许多实际网络的聚类系数要高的多。网络的高度聚类性表明网络在局部可能包含各种由高度连接的节点组构成的子图。这时出现单个功能模块的一个前提。子图描绘了从局部层次刻画一个给定网络的相互连接的特定模式。复杂网络可能包含各种各样的子图，如三角形、正方形和五角形等。其中的一些子图所占的比例明显高于同一网络的完全随机化形式中这些子图所占的比例。这些子图就称为模体。现在是29页\一共有41页\编辑于星期三为了判断实际网络中的一个子图i是否为模体，需要产生与实际网络对应得随机化网络以作比较。判断实际网络中的一个子图i是否为模体的依据如下：①该子图在实际网络对应的随机化网络中出现的次数大于它在实际网络中出现次数的概率是很小的，通常要求这个概率小于某个阈值P（如P=0.01）。②该子图在实际网络中出现的次数Nreali不小于某个下限U（如U=4）。③该子图在实际网络中出现的次数Nreali明显高于高于它在随机化网络中出现的次数Nrandi，一般要求Nreali>1.1Nrandi。现在是30页\一共有41页\编辑于星期三网络模体检测示意图现在是31页\一共有41页\编辑于星期三2.7.2等级网络为了说明许多实际系统中同时存在的模块性、局部聚类和无标度拓扑特性，需要假设模块以某种迭代方式生成一个等级网络。研究表明，一些网络中的拓扑模块确实是按等级组织起来的。现在是32页\一共有41页\编辑于星期三等级模块性的一个最重要的量化标志是节点聚类系数服从幂律C(k)∝k-1。这表明度很小的节点具有高的聚类系数且属于高度连接的小模块。相反，度很高的hub节点具有低的聚类系数，其作用只是把不同的模块连接起来。需要注意的是，ER随机图和BA无标度网络都不具有等级拓扑；在这两类网络中节点聚类系数C(k)与该节点的度k无关。2.7.3超家族小世界和无标度是许多实际网络的共同全局结构特征，那么不同德网络是否也有可能具有相似的局部结构特征？网络模体的研究有助于人们从局部结构上来理解复杂网络的设计原理。在此基础上，Milo等人提出了基于重要性剖面(SP)比较网络局部结构的方法。计算SP的基本思想仍然是把一个实际网络与其对应的随机化网络作对比，这样就可避免不同网络的规模和度序列的影响。现在是33页\一共有41页\编辑于星期三网络中每个子图i的统计重要性用来描述，其中Nreali和Nrandi仍然分别表示该子图在实际网络和对应的随机化网络中出现的次数，<Nrandi>和std(Nrandi)分别是Nrandi的均值和标准方差。对Zi作规范化处理就得到对应的SPi：研究表明，相同类型的网络不仅具有相同的网络模体，而且各个模体在网络中的相对重要性也是相似的。此外，一个网络超家族中可能包含着规模差异很大的功能极其不同的网络。现在是34页\一共有41页\编辑于星期三2.8复杂网络的自相似性左图中的等级网络看上去有一个非常明显的特征，那就是该网络的部分与整体具有很明显的相似性；而局部在某种意义上与整体相似，即自相似性，正是分型的一个基本特征。与自相似性密切相关的一个概念是分数维。计算自相似分形的维数的一种常用方法是盒记数法。该方法的基本思想是用边长为lB的盒子来覆盖该图形，并统计完全覆盖该图形所需要的最少的盒子数NB(lB).现在是35页\一共有41页\编辑于星期三这里的盒子在一位情况下是线段，二维情况下是正方形，三维情况下是立方体，lB是盒子的尺寸。图形的维数的近似计算公式为：等价地有幂律标度公式一般情况下，在理论上只有当盒子尺寸lB趋于零时，才能由公式等到维数的精确值。人们通常在对数坐标系中画出NB(lB)和lB之间的关系，拟合直线的斜率的负值就是dB现在是36页\一共有41页\编辑于星期三盒记数法用于复杂网络的只要困难是：对于大多数实际网络并不存在包含这些网络的自然地欧式空间，而