复杂网络第六章ppt课件.ppt

《复杂网络第六章ppt课件.ppt》由会员分享，可在线阅读，更多相关《复杂网络第六章ppt课件.ppt（60页珍藏版）》请在三一办公上搜索。

1、第六章 随机网络模型,6.1 本章要点,常见的规则网络模型 随机图模型及其拓扑性质 具有任给定度分布的广义随机图模型 基于随机重连的零模型,6.2 从规则网络说起,常见的规则网络,星型耦合网络,全局耦合网络,最近邻耦合网络,6.2.1 全局耦合网络,如果一个网络中的任意两个节点之间都有边直接相连，那么就称该网络为全局耦合网络，简称全耦合网络。,大型实际网络一般都是稀疏的，它们的边数一般至多是O（N）而不是O（N2）。,6.2.1 全局耦合网络,网络中可能存在不少稠密，甚至全耦合的子图。,Twitter上挑选的168个用户之间的关注关系,6.2.2 最近邻耦合网络,如果在一个网络中，每一个节点只

2、和它周围的邻居节点相连，那么就称该网络为最近邻耦合网络。 例如，传感器网络等。,6.2.2 最近邻耦合网络,常见的一种具有周期边界条件的最近邻耦合网络包含围成一个环的N个节点，其中每个节点都与它左右各K/2个邻居点相连，这里K是一个偶数。,6.2.3 星型耦合网络,如果一个网络它有一个中心点，其余的N-1个点都只与这个中心点连接，而它们彼此之间不连接，那么就称该网络为星型耦合网络。,6.2.3 星型耦合网络,6.3 基本拓扑性质,规则网络拓扑性质总结,从一个点出发的三角形数量以任意节点为中心的连通三元组的数目为于是，最近邻耦合网络的聚类系数为,网络中能在一步到达的最远的节点与该节点的格子距离为

3、K/2。两个格子间距为m的节点之间的距离为2m/K,即不小于2m/K的最小整数。 该网络的平均路径长度为,6.1 本章要点,常见的规则网络模型 随机图模型及其拓扑性质 据有人给定度分布的广义随机图模型 基于随机重连的零模型,6.3 随机图,与完全规则网络相对应的是完全随机网络，最为经典的模型是ER随机图模型，该模型既易于描述又可通过解析方法研究。ER随机图模型一直是研究复杂网络拓扑的基本理论。,6.3.1 ER随机图的两种形式定义,1.具有固定边数的ER随机图G（N,M）算法 6.1 ER随机图的构造算法（1）初始化：给定N个节点和待添加的边数M（2）随机连边： 随机选取一对没有边相连的不同的

4、节 点，并在这对节点之间添加一条边。 重复步骤，直至在M对不同的节点之间各添加了一条边。,十个节点，四条边的网络生成过程。,6.3.1 ER随机图的两种形式定义,从另一个角度来看，该模型是从所有的具有N个节点和M条边的简单图中完全随机地选取出来的。严格说来，随机图模型是指一簇网络。 G（N,M）的严格定义是所有图G上的一个概率分布P(G)：记具有N个节点和M条边的简单图的数目为 ，那么对于任一这样的简单图有P(G)=1/ ,而对于其他图有P(G)=0,6.3.1 ER随机图的两种形式定义,在讨论随机图的性质时，通常是指这一簇网络的平均性质。,具有固定连边概率的ER随机图G(N,p),2 ER随

5、机图G(N,p)构造算法（1）初始化：给定N个节点以及连边概率p0,1。（2）随机连边： 选择一对没有边相连的不同的节点 生成一个随机数r （0,1） 如果rp，那么在这对节点之间添加一条边；否则就不添加边。 重复步骤 ，直至所有的节点对都被选择过一次。,N=10，p=1/6情形生成的随机图实例。,具有固定连边概率的ER随机图G(N,p),算法6-2生成的随机图具有如下几种情形： （1）如果p=0，那么G=(N,p)只有一种可能：N个孤立节点，边数M=0 （2）如果p=1，那么G=(N,p)也只有一种可能：N个节点组成的全耦合网络，边数 （3）如果p（0,1），那么从理论上说，N个节点生成具有

6、任一给定的边数 的网络都是有可能的。,具有固定连边概率的ER随机图G(N,p),6.3.2 拓扑性质 边数分布,给定网络节点数N和连边概率p，生成的随机图恰好具有M条边的概率为标准的二项分布：,6.3.2 拓扑性质 边数分布,边数分布的平均值 边数分布的方差方差 刻画了实际生成的模型的边数围绕均值的波动大小,6.3.2 拓扑性质 边数分布,边数分布的变异系数： 对于给定的连边概率p，当网络的规模增大时，生成的模型中的边数越接近均值,6.3.2 拓扑性质 边数分布,随机图的稀疏性:如果连边概率p与1/N同阶， 那么有 这意味着当网络规模充分大时所得到的ER随机图为稀疏网络。,6.3.2 拓扑性质

7、 度分布,任一给定节点恰好与其他k个节点有边相连的概率为pk(1-p)N-1-k由于共有 种选取这k个其他节点的方式，因此网络中任一给定节点的度为k的概率同样服从二项分布,6.3.2 拓扑性质 度分布,度分布的均值=p(N-1)度分布的方差度分布的变异系数同样的，对于任一给定的连边概率p0,1，当网络规模增大时，生成的模型中各节点的度越接近均值=p(N-1)。,6.3.2 拓扑性质 聚类系数,对于ER随机图G(N,p)而言，两个节点之间不论是否具有共同的邻居节点，其连接概率均为p。ER随机图的聚类系数为 C=p=/(N-1),6.3.2 拓扑性质 平均路径长度,对于ER随机图随机选取的一个点，

8、网络中大约有个其他的点与该点之间的距离为1；大约有2个其他的点与该点之间的距离为2；.以此类推，由于网络总的节点数为N，设D是ER随机图的直径，大体上应该有ND因此，网络的直径和平均路径长度满足 LDlnN/ln,6.3.3 巨片的涌现与相变随机图的演化,ER随机图的连通性具有两个极端情形： （1）p=0对应于N个孤立节点 （2）p=1对应于全耦合网络：最大连通片的规模为N，随着网络规模的增长而增长。 如果网络中的一个连通片的规模随着网络规模的增长而成正比例增长，那么该连通片就是一个巨片。,6.3.3 巨片的涌现与相变随机图的演化,如果N=100，那么每次生成的随机图的边数大约为 =pN(N-

9、1)/2=5000pP值每增加0.01，每次随机图的边数就增加50条。随着连边概率的增加，生成的随机图中的边数也在增加，网络的连通性也越来越好。,6.3.3 巨片的涌现与相变随机图的演化,问题： 当连边概率p从0开始逐渐增加到1时，最大连通片的规模是如何具体变化的？ 当p多大时才会出现包含网络中一定比例节点的巨片?,6.3.3 巨片的涌现与相变,ER随机图的许多重要性质都是突然涌现的： 对于任一给定的连边概率p，要么几乎每一个G(N,p)的实例都具有某个性质Q，要么几乎每一个这样的图都不具有性质Q。 如果当N时产生一个具有性质Q的ER随机图的概率为1，那么就称几乎每一个ER随机图都具有性质Q。

10、,6.3.3 巨片的涌现与相变,S定义为ER随机图的巨片的相对规模,u=1-S为不属于巨片的节点所占的比例存在如下两种可能： S=0，u=1，网络中不存在巨片 S0，u1，网络中存在巨片,6.3.3 巨片的涌现与相变,网络中一个随机选择的节点i如果不属于巨片，那么就说明它也没有通过其他任一节点与巨片相连，也即对网络中任一其他节点j，必有两种情形： （1）节点i和j之间没有边相连，此情形发生的概率为1-p （2）节点i和j之间有边相连，但是节点j不属于巨片，此情形发生的概率为pu,6.3.3 巨片的涌现与相变,由前述分析可得，节点i没有通过任一节点与巨片相连的概率为,6.3.3 巨片的涌现与相变

11、,将S=1-u带入上式可得 S=1-e-S, 该式不存在简单的解析解。可用图示的方法得到数值解。,6.3.3 巨片的涌现与相变,6.3.3 巨片的涌现与相变,6.3.4 随机图与实际网络的比较,ER随机图与许多实际网络相比具有一些共性特征： （1）稀疏性 （2）有巨片 （3）小世界,广义随机图,人们可以从多个角度对ER随机图进行扩展使其更接近实际网络。其中一个自然的推广就是具有任意给定度分布、但在其他方面完全随机的广义随机图。配置模型随机重连与零模型,配置模型,在配置模型中事先给定的是网络的度序列d1,d2,dN,其中非负整数di为节点i的度。 显然的两个必要条件是： 由于网络中所有节点的度值

12、之和等于网络中所有边数之和的两倍， 必须为偶数并且有 di N-1,i=1,2,N,等号只有当一个节点与其他所有的节点都相连时才成立。,配置模型,定理 一个非负整数序列d1,d2,dN是某个简单图的度序列的充要条件为 1） 为偶数 2）对于每个整数k,1 k N，均有,配置模型,公式的几何说明,配置模型,例如，验证整数序列6,6,5,4,2,1是否为某个简单图的度序列的步骤如下： =28 为偶数；k=1,显然满足定理；k=2时，不满足定理条件因为 =6+6=12，k(k-1) + = 2x1+(2+2+2+2+1) = 11.所以，整数序列 6,6,5,4,2,1不可能为某个简单图的度序列。,

13、配置模型的构造算法,1）初始化：根据给定度序列确定N个节点的度值。 2）引出线头：从度为ki的节点i引出ki个线头。共有 个线头，M为网络的边数。 3）随机配对：完全随机地选取一对线头，把它们连在一起，形成一条边；再在剩余的线头中完全随机地选取另一对线头连成一条边；依此进行下去，直至用完所有线头。,配置模型的一种构造算法,A,B,D,C,A,B,C,D,C,A,B,D,6.5 随机重连与零模型,从应用角度上看，随机网络模型的价值在于它们可以起到参照系的作用。,随机重连与零模型,零模型,一般地，我们把与一个实际网络具有相同的节点数和相同的某些性质A的随机网络称为该实际网络的随机化网络。 这类随机

14、化网络模型在统计学上称为零模型。,零模型,1)0阶零模型：与原网络具有相同节点数N和边数M的随机化网络。2)1阶零模型：与原网络具有相同节点数N和度分布P(k)的随机化网络。通常做法是每个节点的度值保持不变。3)2阶零模型：与原网络具有相同节点数N和二阶度相关特性（即联合分布）P(k,k)的随机化网络。,0阶零模型：1阶零模型：度分布P(k)2阶零模型：联合度分布P(k,k)3阶零模型：三阶度相关特性P(k1,k2,k3),零模型,4)3阶零模型：与原网络具有相同节点数N和三阶度相关特性（即联合边度分布）P（k1,k2,k3）的随机化网络。,0阶：=21阶：P(1)=1/4,P(2)=1/2,

15、P(3)=1/42阶：P(1,3)=1/4,P(2,2)=1/4,P(2,3)=1/23阶：P(1,3,2)=2/3,P(2,2,3)=1/3,随机重连,在原始网络数据的基础上，保持每个节点的度不变，但是使得连边的位置尽可能随机化，已得到一个具有给定度序列的随机网络。,0阶零模型的随机重连算法,每次随机去除原网络中的一条边k1k2,在随机选择网络中两个不相连的节点k3和k4，并在他们之间添加一条连边k3k4。重复充分多次。,k1,k2,k3,k4,k1,k2,k3,k4,1阶零模型的随机重连算法,每次随机选择原网络中的两条边，记为k1k2和k3k4.如果k1、k2、k3和k4这四个节点有两条边，那么就去除这两条边，并将节点k1与k4相连、节点k2与k3相连，从而得到两条新边。重复此过程充分多次。,k1,k2,k3,k4,k1,k2,k3,k4,2阶零模型的随机重连算法,2阶零模型对应于保持联合度分布不变。每一步采取与1阶零模型相同的步骤，只是多了一个限制，及要求节点k2与k4具有相同的度值。重复此过程充分多次。,k1,k2,k3,k4,k1,k2,k3,k4,HOT网络及相应的零模型,谢谢观看！,