复杂网络第六章

第六章随机网络模型6.1本章要点常见的规则网络模型随机图模型及其拓扑性质具有任给定度分布的广义随机图模型基于随机重连的零模型6.2从规则网络说起常见的规则网络星型耦合网络全局耦合网络最近邻耦合网络6.2.1全局耦合网络如果一个网络中的任意两个节点之间都有边直接相连，那么就称该网络为全局耦合网络，简称全耦合网络。大型实际网络一般都是稀疏的，它们的边数一般至多是O（N）而不是O（N2）。6.2.1全局耦合网络网络中可能存在不少稠密，甚至全耦合的子图。Twitter上挑选的168个用户之间的关注关系6.2.2最近邻耦合网络如果在一个网络中，每一个节点只和它周围的邻居节点相连，那么就称该网络为最近邻耦合网络。例如，传感器网络等。6.2.2最近邻耦合网络常见的一种具有周期边界条件的最近邻耦合网络包含围成一个环的N个节点，其中每个节点都与它左右各K/2个邻居点相连，这里K是一个偶数。6.2.3星型耦合网络如果一个网络它有一个中心点，其余的N-1个点都只与这个中心点连接，而它们彼此之间不连接，那么就称该网络为星型耦合网络。6.2.3星型耦合网络6.3基本拓扑性质全耦合网络最近耦合网络星形网络聚类系数13(K-2)/4(K-1)0平均路径长度1N/2K2规则网络拓扑性质总结从一个点出发的三角形数量以任意节点为中心的连通三元组的数目为于是，最近邻耦合网络的聚类系数为2k/211(1)42CKK2k1(1)2CKK3()网络中三角形的数目网络中连通三元组的数目2/223=kKNCNC网络中能在一步到达的最远的节点与该节点的格子距离为K/2。两个格子间距为m的节点之间的距离为[2m/K],即不小于2m/K的最小整数。该网络的平均路径长度为/211[2/](/2)2NncmNLmKNK6.1本章要点常见的规则网络模型随机图模型及其拓扑性质据有人给定度分布的广义随机图模型基于随机重连的零模型6.3随机图与完全规则网络相对应的是完全随机网络，最为经典的模型是ER随机图模型，该模型既易于描述又可通过解析方法研究。ER随机图模型一直是研究复杂网络拓扑的基本理论。6.3.1ER随机图的两种形式定义1.具有固定边数的ER随机图G（N,M）算法6.1ER随机图的构造算法（1）初始化：给定N个节点和待添加的边数M（2）随机连边：①随机选取一对没有边相连的不同的节点，并在这对节点之间添加一条边。②重复步骤①，直至在M对不同的节点之间各添加了一条边。十个节点，四条边的网络生成过程。6.3.1ER随机图的两种形式定义从另一个角度来看，该模型是从所有的具有N个节点和M条边的简单图中完全随机地选取出来的。严格说来，随机图模型是指一簇网络。G（N,M）的严格定义是所有图G上的一个概率分布P(G)：记具有N个节点和M条边的简单图的数目为，那么对于任一这样的简单图有P(G)=1/,而对于其他图有P(G)=06.3.1ER随机图的两种形式定义在讨论随机图的性质时，通常是指这一簇网络的平均性质。GGGDGDGPD)(1)()(具有固定连边概率的ER随机图G(N,p)2ER随机图G(N,p)构造算法（1）初始化：给定N个节点以及连边概率p∈[0,1]。（2）随机连边：①选择一对没有边相连的不同的节点②生成一个随机数r∈（0,1）③如果r﹤p，那么在这对节点之间添加一条边；否则就不添加边。④重复步骤①~③，直至所有的节点对都被选择过一次。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个节点生成具有任一给定的边数的网络都是有可能的。)1(21NNM)]1(210[NNM，具有固定连边概率的ER随机图G(N,p)6.3.2拓扑性质–边数分布给定网络节点数N和连边概率p，生成的随机图恰好具有M条边的概率为标准的二项分布：22(1)NNCMMMCPMCPP6.3.2拓扑性质–边数分布边数分布的平均值边数分布的方差方差刻画了实际生成的模型的边数围绕均值M的波动大小20()(1)/2NCMMMPMpNN222(1)(1)2MNNMMpp2M6.3.2拓扑性质–边数分布边数分布的变异系数：对于给定的连边概率p，当网络的规模增大时，生成的模型中的边数越接近均值NNNppMM1)1(212/)1(NPNM6.3.2拓扑性质–边数分布随机图的稀疏性:如果连边概率p与1/N同阶，那么有这意味着当网络规模充分大时所得到的ER随机图为稀疏网络。)(~2/)1(NONpNM6.3.2拓扑性质–度分布任一给定节点恰好与其他k个节点有边相连的概率为pk(1-p)N-1-k由于共有种选取这k个其他节点的方式，因此网络中任一给定节点的度为k的概率同样服从二项分布k1NCkNkkNppCP11)1()k(6.3.2拓扑性质–度分布•度分布的均值k=p(N-1)•度分布的方差•度分布的变异系数同样的，对于任一给定的连边概率p∈[0,1]，当网络规模增大时，生成的模型中各节点的度越接近均值k=p(N-1)。)1)(1(p2kNp11)1(11kNNppk6.3.2拓扑性质–聚类系数对于ER随机图G(N,p)而言，两个节点之间不论是否具有共同的邻居节点，其连接概率均为p。ER随机图的聚类系数为C=p=k/(N-1)6.3.2拓扑性质–平均路径长度对于ER随机图随机选取的一个点，网络中大约有k个其他的点与该点之间的距离为1；大约有k2个其他的点与该点之间的距离为2；……..以此类推，由于网络总的节点数为N，设D是ER随机图的直径，大体上应该有N~kD因此，网络的直径和平均路径长度满足L≦D~lnN/lnk6.3.3巨片的涌现与相变—随机图的演化ER随机图的连通性具有两个极端情形：（1）p=0对应于N个孤立节点（2）p=1对应于全耦合网络：最大连通片的规模为N，随着网络规模的增长而增长。如果网络中的一个连通片的规模随着网络规模的增长而成正比例增长，那么该连通片就是一个巨片。6.3.3巨片的涌现与相变—随机图的演化如果N=100，那么每次生成的随机图的边数大约为M=pN(N-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。6.3.3巨片的涌现与相变S定义为ER随机图的巨片的相对规模,u=1-S为不属于巨片的节点所占的比例存在如下两种可能：①S=0，u=1，网络中不存在巨片②S＞0，u﹤1，网络中存在巨片6.3.3巨片的涌现与相变网络中一个随机选择的节点i如果不属于巨片，那么就说明它也没有通过其他任一节点与巨片相连，也即对网络中任一其他节点j，必有两种情形：（1）节点i和j之间没有边相连，此情形发生的概率为1-p（2）节点i和j之间有边相连，但是节点j不属于巨片，此情形发生的概率为pu6.3.3巨片的涌现与相变由前述分析可得，节点i没有通过任一节点与巨片相连的概率为11(1)u(1)[1(1)]1ln(1)ln[1(1)]1(1)NNkukppuuNkuNuNkuue6.3.3巨片的涌现与相变将S=1-u带入上式可得S=1-e-kS,该式不存在简单的解析解。可用图示的方法得到数值解。6.3.3巨片的涌现与相变6.3.3巨片的涌现与相变6.3.4随机图与实际网络的比较ER随机图与许多实际网络相比具有一些共性特征：（1）稀疏性（2）有巨片（3）小世界广义随机图人们可以从多个角度对ER随机图进行扩展使其更接近实际网络。其中一个自然的推广就是具有任意给定度分布、但在其他方面完全随机的广义随机图。–配置模型–随机重连与零模型配置模型在配置模型中事先给定的是网络的度序列{d1,d2,…,dN},其中非负整数di为节点i的度。显然的两个必要条件是：①由于网络中所有节点的度值之和等于网络中所有边数之和的两倍，必须为偶数并且有②diN-1,i=1,2,…,N,等号只有当一个节点与其他所有的节点都相连时才成立。1dNii1d(1)NiiNN配置模型定理一个非负整数序列{d1,d2,…,dN}是某个简单图的度序列的充要条件为1）为偶数2）对于每个整数k,1kN，均有1dNiik11d(1)min(,).Nijijkkkkd配置模型公式的几何说明k11d(1)min(,).Nijijkkkkd配置模型例如，验证整数序列{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}不可能为某个简单图的度序列。71dii1dkii1min(,)Njjkkd配置模型的构造算法1）初始化：根据给定度序列确定N个节点的度值。2）引出线头：从度为ki的节点i引出ki个线头。共有个线头，M为网络的边数。3）随机配对：完全随机地选取一对线头，把它们连在一起，形成一条边；再在剩余的线头中完全随机地选取另一对线头连成一条边；依此进行下去，直至用完所有线头。12NiikM配置模型的一种构造算法ABDCABCDCABD6.5随机重连与零模型从应用角度上看，随机网络模型的价值在于它们可以起到参照系的作用。美国西部电力网络ER随机图平均路径长度18.712.4聚类系数0.0800.005随机重连与零模型零模型一般地，我们把与一个实际网络具有相同的节点数和相同的某些性质A的随机网络称为该实际网络的随机化网络。这类随机化网络模型在统计学上称为零模型。零模型1)0阶零模型：与原网络具有相同节点数N和边数M的随机化网络。2)1阶零模型：与原网络具有相同节点数N和度分布P(k)的随机化网络。通常做法是每个节点的度值保持不变。3)2阶零模型：与原网络具有相同节点数N和二阶度相关特性（即联合分布）P(k,k’)的随机化网络。0阶零模型：k1阶零模型：度分布P(k)2阶零模型：联合度分布P(k,k’)3阶零模型：三阶度相关特性P(k1,k2,k3)123P(,,)kkk123P(,,)kkk零模型4)3阶零模型：与原网络具有相同节点数N和三阶度相关特性（即联合边度分布）P（k1,k2,k3）的随机化网络。0阶：k=21阶：P(1)=1/4,P(2)=1/2,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。重复充分多次。k1k2k3k4k1k2k3k41阶零模型的随机重连算法每次随机选择原网络中的两条边，记为k1k2和k3