复杂网络理论及应用

1、复杂网络理论及应用Complex Network Theory and Its Application项厦门大学 信息科学与技术学院: xiangly Tel:第四章复杂网络模型4.1 规则网络模型4.2 随机网络模型4.3 小世界网络模型4.4 无标度网络模型2复杂网络模型随机图理论(Random Graph Theory) A revolution made in 1950-60sPaul ErdösAlfred Rényi3复杂网络模型数字情种 Erdös (1913-1996)> 1500 papers>500 coauthors“My Bra

2、in Is Open”“Another Roof, Another Proof ”4复杂网络模型5复杂网络模型文献1陈项文献2文献3Erdös1 L.Y. Xiang, F. Chen, G.R. Chen. Nonlinear Dynamics, 2014, 78: 1609-1628.2 C.K. Chui, G.R. Chen. Kalman Filtering with Real-Time Applications. Berlin: Springer-Verlag, 1987.3 I. Borosh, C.K. Chui, P. Erdös. Anal. Math.

3、, 1978, 4(1): 3-12.6“小世界”体验YOU?ER随机图模型 G(N, p)构造算法:初始化: 给定N 个节点和概率p0,1。(1)(2):随机(i) 选择一对没有边相连的不同的节点；(ii) 生成一个随机数 r(0,1)；(iii) 如果 r <p，那么在这对节点之间添加一条边；否则就不添加边；(iv) 重复步骤(i)-(iii)，直至所有的节点对都被选择过一次。 几种情形:(1) p=0:(2) p=1:(3) p0,1:7复杂网络模型ER随机图模型 G(N, p)构造算法:初始化: 给定N 个节点和概率p0,1。(1)(2):随机(i) 选择一对没有边相连的不同的节

4、点；(ii) 生成一个随机数 r(0,1)；(iii) 如果 r <p，那么在这对节点之间添加一条边；否则就不添加边；(iv) 重复步骤(i)-(iii)，直至所有的节点对都被选择过一次。 几种情形:(1) p=0: N 个孤立节点，(2) p=1:(3) p0,1:M=0。8复杂网络模型ER随机图模型 G(N, p)构造算法:初始化: 给定N 个节点和概率p0,1。(1)(2):随机(i) 选择一对没有边相连的不同的节点；(ii) 生成一个随机数 r(0,1)；(iii) 如果 r <p，那么在这对节点之间添加一条边；否则就不添加边；(iv) 重复步骤(i)-(iii)，直至所有

5、的节点对都被选择过一次。 几种情形:(1) p=0: N 个孤立节点，M=0。(2) p=1: N 个节点组成的全局耦合网络，(3) p0,1:M=N(N-1)/2。9复杂网络模型ER随机图模型 G(N, p)构造算法:初始化: 给定N 个节点和概率p0,1。(1)(2):随机(i) 选择一对没有边相连的不同的节点；(ii) 生成一个随机数 r(0,1)；(iii) 如果 r <p，那么在这对节点之间添加一条边；否则就不添加边；(iv) 重复步骤(i)-(iii)，直至所有的节点对都被选择过一次。 几种情形:(1) p=0: N 个孤立节点，M=0。(2) p=1: N 个节点组成的全局

6、耦合网络，M=N(N-1)/2。(3) p0,1: 从理论上说，生成具有任一给定的都是有可能的。复杂网络模型M0, N(N-1)/2的网络10N =10和p =1/6时所生成的随机图的3个实例一般而言，不同的网络出现的概率是不一样的。对于固定的概率p，当网络规模 N 充分大时，每次运行算法都非常接近！换句话说，在给定相同参数 N 和所得到的p的情形，实际上不可能一次得到的很少，而另一次得到的很大！11复杂网络模型ER随机图的基本性质分布给定网络节点总数N，网络中任意两个节点以概率p，生成的网络全体记为G(N, p) ，一个概率空间。网络中数目是一个随量X，取值范围为0, N(N-1)/2。有M

7、条边的网络数目为:其中一个特定网络出现的概率为:分布的平均值为:N个节点可以组N(N-1)/2个节点对，而每个节点对之间存在边的概率均为 p表示M对节点之间添加了边表示具有N个节点和M条边的简单图的数量ER随机图的基本性质(续)度分布网络中任一给定节点恰好与其它 k 个节点有边相连的概率为 pk(1-p)N-1-k。由于共有 CN-1k 种选取这 k 个其它节点的方式，因此，网络中任一给定节点的度为 k 的概率服从二项分布：度分布的均值为:当 N 很大，p 很小时，二项分布趋于泊松 (Poission) 分布！13复杂网络模型黑点表示均值为5的泊松分布，实线对应二项分布N=10, p=0.5

8、(红线)；N=20, p=0.25 (蓝线)；N=1000, p=0.005 (绿线)14复杂网络模型黑点表示均值为5的泊松分布，实线对应二项分布N=10, p=0.5 (红线)；N=20, p=0.25 (蓝线)；N=1000, p=0.005 (绿线)当N很大，p 很小时，二项分布趋于泊松(Poission)分布！15复杂网络模型实心黑点表示均值为15的ER随机图的度分布实线对应泊松分布ER随机图的度分布与泊松分布的比较复杂网络模型16ER随机图的基本性质(续)平均路径长度距离为1的节点数:距离为2的节点数: 距离为DER的节点数:17复杂网络模型ER随机图的基本性质(续)平均路径长度距离

9、为1的节点数:距离为2的节点数: 距离为DER的节点数:18复杂网络模型ER随机图的基本性质(续)平均路径长度距离为1的节点数:距离为2的节点数: 距离为DER的节点数:19复杂网络模型ER随机图的基本性质(续)平均路径长度距离为1的节点数:距离为2的节点数: 距离为DER的节点数:20复杂网络模型ER随机图的基本性质(续)平均路径长度距离为1的节点数:距离为2的节点数: 距离为DER的节点数:21复杂网络模型ER随机图的基本性质(续)平均路径长度距离为1的节点数:距离为2的节点数: 距离为DER的节点数:网络的直径和平均路径长度满足以下关系式:22复杂网络模型ER随机图的基本性质(续)平均路

10、径长度距离为1的节点数:距离为2的节点数: 距离为DER的节点数:网络的直径和平均路径长度满足以下关系式:23复杂网络模型ER随机图的基本性质(续)平均路径长度LER DERlnN/ln<k>距离为1的节点数:距离为2的节点数: 距离为DER的节点数:网络的直径和平均路径长度满足以下关系式:24复杂网络模型对网络的分析朋友数的指数增长25复杂网络模型实际网络的聚类效应实际网络中朋友数的增长26复杂网络模型ER随机图的基本性质(续)聚类系数网络中任一节点的聚类系数定义为该节点的任意两个邻居节点之间有边相连的概率 。对于ER随机图G(N, p)而言，两个节点之间不论是否具有共同的邻居节

11、点，其连接概率均为 p。网络中任一节点与其它N-1个节点中的每个节点有边相连的概率都为p。27复杂网络模型ER随机图的基本性质(续)聚类系数CER = p = <k>/(N-1) <<1网络中任一节点的聚类系数定义为该节点的任意两个邻居节点之间有边相连的概率 。对于ER随机图G(N, p)而言，两个节点之间不论是否具有共同的邻居节点，其连接概率均为 p。网络中任一节点与其它N-1个节点中的每个节点有边相连的概率都为p。28复杂网络模型ER随机图的基本性质(续)聚类系数CER = p = <k>/(N-1) <<1网络中任一节点的聚类系数定义为该节

12、点的任意两个邻居节点之间有边相连的概率 。对于ER随机图G(N, p)而言，两个节点之间不论是否具有共同的邻居节点，其连接概率均为 p。网络中任一节点与其它N-1个节点中的每个节点有边相连的概率都为当平均度固定不变时，聚类系数随着网络规模的增加而减小。p。29复杂网络模型随机图的演化ER 随机图的连通性具有两个情形:(1) p=0对应于N 个孤立节点: 最大连通片规模为常数1(只包含一个节点)，与网络规模N 无关。(2) p=1对应耦合网络: 最大连通片规模为N，随着网络规模的增长而增长。30复杂网络模型随机图的演化ER 随机图的连通性具有两个情形:(1) p=0对应于N 个孤立节点: 最大连

13、通片规模为常数1(只包含一个节点)，与网络规模N 无关。(2) p=1对应耦合网络: 最大连通片规模为N，随着网络规模的增长而增长。What happens for other p?31复杂网络模型具有不同概率的随机图32复杂网络模型随着概率p的增加，生成的随机图中的也在增加，网络的连通性也越来越好!随机图的巨片概率 p 从0开始逐渐增大到1时，最大连通片的规模是如当何具体变化的？特别地，当 p 多大时才会出现包含网络中一定比例节点的巨片？33巨片的涌现 ER随机图的许多重要的性质都是突然涌现的: 对于任一给定的概率p，要么几乎每一个图都具有某个性质Q(比如连通性)，要么几乎每一个这样的图都

14、不具有性质Q。34复杂网络模型Are real networks like random graphs?35复杂网络模型平均路径长度实际网络ER网络模型36复杂网络模型平均路径长度实际网络ER网络模型实际网络具有与相同规模和平均度的ER随机网络相近的平均路径长度.37复杂网络模型聚类系数实际网络ER网络模型38复杂网络模型聚类系数实际网络ER网络模型实际网络的聚类系数比相同规模的ER随机网络的聚类系数高得多39复杂网络模型度分布实际网络ER网络模型(a) Internet;(b) Movie Actors;(c) Coauthorship, high energy physics;(d) Coauthorship, neuroscience复杂网络模型度分布实际网络ER网络模型实际网络的