复杂网络第二讲 网络拓扑基本模型及其性质 李凯凯.

Presentation on theme: "复杂网络第二讲 网络拓扑基本模型及其性质 李凯凯."— Presentation transcript:

1 复杂网络第二讲 网络拓扑基本模型及其性质 李凯凯

2 规则网络 随机图 小世界网络模型 无标度网络模型 局域世界演化网络模型 模块性与等级网络 复杂网络的自相似性

3 规则网络 系统中节点及其与边的关系是固定的。 全局耦合网络具有最小的平均路径长度Lgc =1和最大的聚类系数Cgc =1；
（a）全局耦合网络； （b）最近邻耦合网络； （c）星形网络 全局耦合网络具有最小的平均路径长度Lgc =1和最大的聚类系数Cgc =1；

4 最近邻耦合网络:包含N个围成一个环的点，其中每个节点都与它左右各K/2个邻居点相连（K为偶数），对于较大的K值，最近邻耦合网络的聚类系数为

5 随机图 随机图是与规则网络相反的网络，一个典型模型是Erdos和Renyi于40多年前开始研究的随机图模型。
假设有大量的纽扣（N》1）散落在地上，并以相同的概率p给每对纽扣系上一根线。这样就会得到一个有N个节点，约pN(N-1)/2条边的ER随机图的实例。

6 ER随机图的性质 随机图理论的一个主要研究课题是： 当概率p为多大时，随机图会产生一些特殊的属性？
Erdos和Renyi系统地研究了当 时，ER随机图的性质与概率p之间的关系，他们采用了如下定义： 如果当 时产生一个具有性质Q的ER随机图的概率为1，那么就称几乎每一个ER随机图都具有性质Q。 Erdos和Renyi的最重要的发现时ER随机图具有如下的涌现或相变性质： ER随机图的许多重要的性质都是突然涌现的。也就是说，对于任意给定的概率p，要么几乎每一个图都具有性质Q，要么几乎每一个图都不具有该性质。 上述纽扣网络，如果p大于某个临界值 ，那么几乎每一个随机图都是连通的。

7 ER 随机图的平均度是 ,平均路径长度 。LER为网络规模的对数增长函数是典型的小世界特征。ER随机图的聚类系数是C=p=<k>/N《1，这意味着大规模的稀疏ER随机图没有聚类特性。实际网络的聚类系数要比相同规模的ER随机图的聚类系数要高得多。 ER随机图的度分布可用Poission分布来表示： 因此，ER随机图也称为“Poission随机图”。

8 小世界网络模型 作为从完全规则网络向完全随机图的过渡，Watts和Strogtz于1998年引入了一个小世界网络模型，称为WS小世界模型。其构造算法如下： ①从规则图开始：考虑一个含有N个点的最近邻耦合网络，它们围成一个环，其中每个节点都与它左右相邻的各K/2个节点相连，K是偶数。 ②随机化重连：以概率p随机地重连网络中的每个边，即将边的一个端点保持不变，而另一个端点取为网络中随机选择的一个节点。其中规定，任意两个不同节点之-间至多只能有一条边，并且每一个节点都不能有边与自身相连。 P=0对应于完全规则网络，p=1对应于完全随机网络。

9 具有较短的平均路径长度又具有较高的聚类系数的网络就称为小世界网络。
Newman和Watts提出了NW小世界模型，用“随机化加边”取代WS小世界模型构造中的“随机化重连”。算法如下： ①从规则图开始：含有N 个节点的最近邻耦合网络。 ②随机化加边：以概率P在随机选取的一对节点之间加上一条边。 NW小世界模型中，p=0对应于原来的最近邻耦合网络，p=1对应于全局耦合网络。

10 小世界网络的性质 1.聚类系数 WS小世界网络的聚类系数为 NW小世界网络的聚类系数为 2.平均路径长度

11 其中f（u）为一普适标度函数，满足 Newman等人基于平均场方法给出了如下近似表达式： 3.度分布 在基于“随机化加边”机制的NW小世界模型中，每个节点的度至少为K，因此当 时，一个随机选取的节点的度为k的概率为： 而当k<K时，P（k）=0。

12 无标度网络模型 研究发现许多复杂网络的连接度分布函数具有幂律形式，由于这类网络的节点的连接度没有明显的特征长度，故称为无标度网络。
Barabasi 和Albert 提出了一个无标度网络模型，称为BA模型。该模型考虑到了实际网络的两个重要特性： ①增长特性；②优先连接特性。 基于这两个特性，BA无标度网络模型构造算法如下： ①增长：从一个具有m0个节点的网络开始，每次引入一个新的节点，并且连到m个已存在的节点上，这里 。 ②优先连接：一个新节点与一个已经存在的节点i相连接的概率 与节点i的度ki，节点j的度kj之间满足如下关系：

13

14 无标度网络的性质 1.平均路径长度 ，表明该网络具有小世界特性。 2.聚类系数 3.度分布 BA无标度网络的度分布函数为
1.平均路径长度 ，表明该网络具有小世界特性。 2.聚类系数 3.度分布 BA无标度网络的度分布函数为 这表明BA无标度网络的度分布函数可由幂指数为3的幂律函数近似描述。

15 幂律分布函数的无标度性质 ：考虑一个概率分布函数f(x)，如果对任意给定常数a，存在常数 b 使得函数 f(x) 满足如下“无标度条件”:
f(ax)=bf(x) 那么必有(假定 ) 也就是说，幂律分布函数是唯一满足“无标度条件”的概率分布函数。

16

17 鲁棒性与脆弱性 假定一个网络，每次从该网络中移走一个节点，同时移走与该节点相连的所有边，从而可能使得网络中其他节点之间的一些路径被中断，如果在节点i和节点j之间有多条路径，中断其中一些路径可能会使这两个节点之间的距离增大，从而整个网络的平均路径长度也会增大，而如果节点i和节点j之间的所有路径都被中断，那么这两个节点之间就不再连通了。如果在移走少量节点后网络中的绝大部分节点仍是连通的，那么就称该网络对节点故障具有鲁棒性。

18

19 比较ER随机图和BA无标度网络的连通性对节点去除的鲁棒性，考虑两类节点去除策略：一是随机故障策略，即完全随机地去除网络中的一部分节点；二是蓄意攻击策略，即从去除网络中度最高的节点开始，有意识地去除网络中一部分度最高的节点。

20

21

22

23 无标度网络对随机图故障具有极高的鲁棒性：这种高度鲁棒性来自于网络度分布的极端非均匀性，然而，正是这种网络度分布的非均匀性使得无标度网络对蓄意攻击具有高度的脆弱性。对随机故障的鲁棒性和对蓄意攻击的脆弱性是无标度网络的一个基本特征。 事实上，科学家研究表明，“鲁棒但又脆弱”是复杂系统的最重要和最基本的特征之一。 假设去除的节点数占原始网络总节点数的比例为f，可以用最大联通子图的相对大小S和平均路径和长度l与f的关系来度量网络的鲁棒性，研究发现，ER随机图和BA无标度网络之间存在及其显著的差异性。

24

25 适应度模型 BA模型只能生产度分布幂律指数固定为3的无标度网络，实际网络的幂律指数则不尽相同，且大都属于2至3的范围内。
2000年，Jeng等人在《Nature》上发表的文章中对43种生物体组织的新陈代谢过程加以研究，他们以各种基质（如ADP）为节点，以基质参与的某种化学反应为边构建了新陈代谢的复杂网络，结果显示，这些网络的度分布都服从幂律分布，幂指数在2.0~2.4之间。

26 在BA无标度网络的增长过程中，节点的度也在发生变化并且满足如下幂律关系。
其中 是第i个节点在时刻t的度， 是第i个节点加入到网络中的时刻，上式表明，在BA无标度网络中，越老的节点具有越高的度，然而，在许多实际网络中，节点的度及其增长速度并非只与该节点的年龄有关，有时是与节点的内在性质有关的，如个人的交友能力，WWW站点的内容和科研论文的质量等，Bianconi和Barabasi把这一性质称为节点的适应度，并据此提出了适应度模型，其构造算法如下：

27 ①增长：从一个具有m0个节点的网络开始，每次引入一个新的节点并且连到m个已存在的节点上，这里 。每个节点的适应度按概率分布 选取。
②优先连接：一个新节点与一个已经存在的节点i相连接的概率 ，与节点i的度ki，节点j的度kj和适应度 之间满足如下关系 可见，适应度模型与BA无标度模型的区别在于，在适应度模型中的优先连接概率与节点的度和适应度之积成正比，而不是仅与节点的度成正比，这样，在适应度模型中，如果一个年轻的节点具有的较高的适应度，那么该节点就有可能在随后的网络演化过程中获取更多的边。

28 局域世界演化网络模型 在许多实际网络中，每个节点都有各自的局域世界，研究者们建立了局域世界演化网络模型，其构造算法如下：
①增长：网络初始时有m0个节点和e0条边，每次新加入一个节点和附带的m条边。 ②局域世界优先连接：随机地从网络已有的节点中选取M个节点（ ），作为新加入节点的局域世界，新加入的节点根据优先连接概率 来选择与局域世界中的m个节点相连，其中LW是由新选择的M个节点组成。

29 在t时刻， ，因此上述局域世界演化网络模型有两个特殊情形：M=m和M=t+m0。
（1）特殊情形A ： M=m 这时，新加入的节点与其局域世界中所有的节点相连接，这等价于BA无标度网络模型中只保留增长机制而没有优先连接。此时，第i个节点的度的变化率为 网络度分布服从指数分布

30 （2）特殊情形B： M=t+m0 在这种特殊情形，每个节点的局域世界其实就是整个网络，因此，局域世界模型就完全等价于BA无标度网络模型。

31 模块性与等级网络 模块（module）与模体（motif） 模块是指一组物理上或功能上连接在一起的、共同完成一个相对独立功能的节点。
模体可能是复杂网络的基本模块。网络的高聚类性表明网络可能包含由高度连接的节点构成的子图。如三角形，正方形和五角形，其中一些子图所占的比例明显高于同一网络的完全随机化形式中这些子图所占的比例。这些子图就称为模体。

32 判断实际网络中的一个子图i是否为模体的依据如下：
①该子图在与实际网络对应的随机化网络中出现的次数大于它在实际网络中出现的次数的概率是很小的，通常要求这个概率要小于某个阈值P（如P=0.01） ②该子图在实际网络中出现的次数Nreali不小于某个下限U（如U=4）. ③该子图在实际网络中出现的次数Nreali明显高于它在随机化网络中出现的次数Nrandi,一般要求Nreali>1.1Nrandi 。

33

34 等级网络

35 ER随机图和BA无标度网络都不具有等级拓扑，在这两类网络中节点的聚类系数C（k）与该节点的度k无关。
等级网络具有与网络规模无关的较高的聚类系数 ， 等级模块性的一个最重要的量化标志是节点聚类系数服从幂律 。这表明度很小的节点具有较高的聚类系数，相反度很高的节点具有低的聚类系数，其作用只是把不同的模块连接起来。 ER随机图和BA无标度网络都不具有等级拓扑，在这两类网络中节点的聚类系数C（k）与该节点的度k无关。

36 复杂网络的自相似性 等级网络看上去有一个明显的特征，就是该网络部分与整体具有很明显的相似性，即自相似性，正是分形的一个基本特征。
Sierpinski三角形：

37 复杂网络的小世界特征意味着网络的平均路径长度l可以用网络规模N的对数函数来表示，即 ，等价于
其中L0表示特征长度，上式意味着网络规模是网络平均路径长度的指数函数。而自相似性要求满足某种幂律关系，然而，Song等人的研究指出，许多实际网络，包括WWW，蛋白质交互作用网络和细胞网络等，在某种长度-标度下确实是自相似的。

38 与自相似性密切相关的一个概念是分数维，计算自相似分形的维数的一种常用的方法是盒记数法。基本思想是用边长为lB的盒子来覆盖该图形，并统计完全覆盖该图形需要的最少的盒子数NB(lB)
图形维数的近似计算公式为 等价地有幂律标度公式

39 例：对于Sierpinski三角形，假设这个大三角形的边长为1，如果用边长为1/2的正方形覆盖Sierpinski三角形，那么需要3个正方形，如果用边长为1/4的正方形覆盖Sierpinski三角形，需要9个正方形，如果用边长为1/8的正方形覆盖它，则需要27个正方形，依次类推，有以下公式：

40 Song等人通过采用重整化过程，揭示出自相似性和无标度分布在网络的所有粗粒化阶段都成立，在把所有节点都分配到盒子中之后，再把每个盒子用单个节点来表示，这些节点称为重整化节点，如果在两个未重整化盒子之间至少存在一条边，那么两个重整化节点之间就有一条边相连，这样就得到一个新的重整化网络。这种重整化过程可以一直进行下去，直到这个网络被规约为单个节点。

41

42 重整化网络的度分布P（k’）在重整化下具有不变性。
下图显示了www的度分布在不同盒子尺寸lB重整化下的不变性。

43 参考文献 [1]Barabasi A L,Bonabeau E.Scale-free networks.Scientific American,May 2003,50~59 [2] Barabasi A L,Oltvai Z N.Network biology:Understanding the cell’s functional organization.Nature Reviews-Genetics,2004,5: [3]Song C,Havlin S,Makse H A.Self-similarity of complex networks.Nature,2005,433:392~395