复杂网络的无标度特性课件

目录概率统计预备知识网络(图)的基本概念规则图和随机网Scale-free网络常用软件参考文献目录1一、概率统计预备知识一、概率统计预备知识2目录随机变量与分布函数（离散、连续）随机变量的数字特征（数学期望、方差）泊松分布幂函数指数函数目录随机变量与分布函数（离散、连续）3随机变量与分布函数对某个随机试验，如果每次试验的结果可以用一个数X来表示，而且对任何实数k，X<x有着确定的概率，则称X是随机变量。随机变量X的值小于实数k的概率P(X<x)是x的函数，记作F(k)=P(X<x),函数F(x)叫做随机变量X的分布函数。随机变量与分布函数对某个随机试验，如果每次试验的结果可以4离散型分布若随机变量X只取有限个或可数个孤立的值，并且对应这些值有确定的概率，即，则称X是离散随机变量（或X是离散分布的），称为的概率分布，它满足下列条件：离散型分布若随机变量X只取有限个或可数个孤立的值5连续型分布若存在一个非负函数，使随机变量X的分布函数可以表示为则X称为连续随机变量（或X是连续分布的），称为随机变量X的概率密度。

连续型分布若存在一个非负函数，使随机变量X的分布6的性质的性质7随机变量的数字特征随机变量的数学期望定义1设x是离散型随机变量，它的概率函数是随机变量的数字特征随机变量的数学期望8随机变量的数学期望，反映了随机变量取值的平均水平，即均值，是随机变量的算术平均。

随机变量的数学期望，反映了随机变量取值的平均水平，即均值，是9方差为随机变量的方差。方差是刻划随机变量取值离差程度的一个数。X的方差的算术平方根称为标准差(或均方差）

方差为随机变量的方差。方差是刻划随机变量取值离差程度的10若X是离散型随机变量，则方差为：若X是离散型随机变量，则方差为：11泊松定理设随机变量Xn(n=0，1，2，…)服从二项分布，其分布律为其中设为常数则泊松定理设随机变量Xn(n=0，1，2，…)服从二项分12泊松分布

设随机变量X所有可能取的值为0，1，2，…，而取各个可能值的概率为：

若>0是常数，则称变量X服从参数为泊松分布，记为

泊松分布设随机变量X所有可能取的值为0，1，2，…，而取13<k><k>14于是，x的数学期望为：即于是，x的数学期望为：即15复杂网络的无标度特性课件16所以，X的方差和均方差分别为：

所以，X的方差和均方差分别为：17指数函数对公式线性化，两边取对数得令则指数函数对公式线性化，两边取对数得18指数函数指数函数19幂函数式中为实数。对公式线性化，两边取对数，得令，，得函数形式为：幂函数式中为实数。令，20幂函数变量代换可在双对数坐标上得直线，

幂函数变量代换可在双对数坐标上得直线，21二、网络(图)的基本概念二、网络(图)的基本概念22中国教科网中国教科网23网络(图)的基本概念节点通常用来表示系统中的部件；边通常用来表示系统中部件之间的关系。网络(图)就是由节点与节点之间的关系构成的一张图。网络(图)的基本概念节点通常用来表示系统中的部件；24中国教科网拓扑结构中国教科网拓扑结构25网络（图）的基本概念关联与邻接度、平均度节点的度分布最短路径与平均路径长度群系数网络（图）的基本概念关联与邻接26网络(图)的基本概念aedcb网络(图)的基本概念aedcb27有向图、无向图、不连通图有向图、无向图、不连通图28网络(图)的基本概念节点的度分布是指网络（图）中度为的节点的概率随节点度的变化规律。网络(图)的基本概念节点的度分布是指网络（图）中度为的节29网络(图)的基本概念最短路径就是从指定始点到指定终点的所有路径中总权最小的一条路经。平均路径长度是指所有点对之间的最短路径的算术平均值。网络(图)的基本概念最短路径就是从指定始点到指定终点的所有路30网络(图)的基本概念集群系数(Clusteringcoefficient)反映网络的群集程度，定义为网络的平均度与网络规模之比。网络(图)的基本概念集群系数(Clusteringcoef312277

55553311网络(图)的基本概念227755553311网络(图)的基本概念32节点1到7之间的最短路13，平均路径长度5.47，平均度为3.4，集群系数为0.48。网络(图)的基本概念节点1到7之间的最短路13，平均路径长度5.47，网络(图)33三、规则图和随机图规则图的特征如果系统中节点及其与边的关系是固定的，每个节点都有相同的度数，就可以用规则图来表示这个系统。随机图的特征如果系统中节点及其与边的关系不确定，就只能用随机图来表示这个系统。三、规则图和随机图规则图的特征34规则图的特征平均度为3。规则图的特征平均度为3。35随机图的特征节点确定，但边以概率任意连接。节点不确定，点边关系也不确定。随机图的特征节点确定，但边以概率任意连接。36随机图——节点19，边43平均度为2.42，集群系数为0.13。随机图——节点19，边43平均度为2.42，集群系数为0.137随机图——节点42，边118平均度为5.62，集群系数为0.133。随机图——节点42，边118平均度为5.62，集群系数为0.38四、Scale-free网络四、Scale-free网络39目录早期网络模型无标度Scale-free网络BA模型目录早期网络模型40早期网络模型ER模型小世界模型早期网络模型ER模型41ER模型Erdös和Rényi（ER）最早提出随机网络模型并对模型进行了深入研究，他们是用概率统计方法研究随机图统计特性的创始人。在模型开始阶段给定N个节点，没有边，以概率p用边连接任意一对节点，用这样的方法产生一随机网络。ER模型Erdös和Rényi（ER）最早提出随机网络模型42复杂网络的无标度特性课件43ER模型Erdös和Rényi（1959）首先研究了在随机网络中最大和最小度的分布，Bollobás(1981)随后得到了所有度分布的形式，推导出度数为k的节点数遵从平均值为的泊松分布，即ER模型Erdös和Rényi（1959）首先研究了在随机网44Connectwithprobabilitypp=1/6N=10k~1.5PoissondistributionConnectwithprobabilitypp=1/45小世界模型为了描述从一个局部有序系统到一个随机网络的转移过程，Watts和Strogatz（WS）提出了一个新模型，通常称为小世界网络模型。WS模型始于一具有N个节点的一维网络，网络的节点与其最近的邻接点和次邻接点相连接，然后每条边以概率p重新连接。约束条件为节点间无重边，无自环。小世界模型为了描述从一个局部有序系统到一个随机网络的转移过程46C(p):clusteringcoeff.L(p):averagepathlengthP(k)=0.1p(k)=0.3C(p):clusteringcoeff.47小世界模型当p等于0时，对应的网络规则图。两个节点间的平均距离<L>线性地随N增长而增长，集群系数大。当p等于1时，系统变为随机图。<L>对数地随N增长而增长，且集群系数随N减少而减少。在p等于（0，1）区间任意值时，模型显示出小世界特性，<L>约等于随机图的值，网络具有高度集群性。小世界模型当p等于0时，对应的网络规则图。两个节点间的平均距48复杂网络都具有分布于平均值两边的度分布曲线吗？复杂网络都具有分布于平均值两边的度分布曲线吗？49无标度(Scale-free)网络Scale-free网络的发现Scale-free网络的特性无标度(Scale-free)网络Scale-free网络的50Scale-free)网络的发现信息交换网（万维网、国际互联网、电话网、电力网）社会网络（电影演员合作网、科研合作图、引文网、人类性接触网、语言学网）生物网络（细胞网络、生态网络、蛋白质折叠）Scale-free)网络的发现信息交换网（万维网、国际互联51复杂网络的无标度特性课件52复杂网络的无标度特性课件53Scale-free网络的特性度分布呈幂率分布中枢节点出现稳健性脆弱性Scale-free网络的特性度分布呈幂率分布54复杂网络的无标度特性课件55复杂网络的无标度特性课件56无标度网络与随机图特性比较无标度网络与随机图特性比较57无标度（Scale-free）网络无标度模型由Albert-LászlóBarabási和RékaAlbert在1999年首先提出，现实网络的无标度特性源于众多网络所共有的两种生成机制：（ⅰ）网络通过增添新节点而连续扩张；（ⅱ）新节点择优连接到具有大量连接的节点上。无标度（Scale-free）网络无标度模型由Albert-58BA模型增长和择优连接这两种要素激励了Barabási－Albert模型的提出，该模型首次导出度分布按幂函数规律变化的网络。模型的算法如下：（1）增长：开始于较少的节点数量（m0），在每个时间间隔增添一个具有m（≤m0）条边的新节点，连接这个新节点到m个不同的已经存在于系统中的节点上。（2）择优连接：在选择新节点的连接点时，假设新节点连接到节点i的概率π取决于节点i的度数即BA模型增长和择优连接这两种要素激励了Barabási－Al59经过t时间间隔后，该算法程序产生一具有N=t+m0个节点，mt条边的网络。数量模拟表明具有k条边的节点的概率服从指数为r=3的幂指数分布。经过t时间间隔后，该算法程序产生一具有N=t+m0个节点，m60P(k)~k-3A.-L.Barabási,R.Albert,Science286,509(1999)P(k)~k-3A.-L.Barabási,R.Alb61BA模型（a)Barabási-Albert模拟的度分布。（b）不同系统规模下的。

BA模型（a)Barabási-Albert模拟的度分布。62BA模型设节点i的度满足动态方程：分母求和是对系统中除新进入系统的节点外的所有节点进行的，则BA模型设节点i的度满足动态方程：63BA模型当t足够大时，有解微分方程，有BA模型当t足够大时，有64由初始条件得解为式中可给出度小于k的节点的概率

由初始条件得解为65设在相同的时间间隔，添加节点到网络中，值具有常数概率密度

代入前式t趋于无穷时度分布

式中设在相同的时间间隔，添加节点到网络中，值具有常数66模型的度分布是与时间无关的渐进分布且与系统规模无关。幂律度分布的系数与成正比。无标度模型的动态特性可以用各种分析方法给出：连续域理论主方程法变化率方程法模型的度分布是与时间无关的渐进分布且与系统规模无关。67Baralási-Albert模型的限制条件保持了网络的增长特性，不考虑择优连接，网络度分布呈指数衰减。消除了增长过程，只考虑择优连接，络度分布围绕其均值为一高斯分布。Baralási-Albert模型的限制条件保持了网络的增68Baralási-Albert模型扩展研究初始吸引度非线性择优连接择优连接的更迭机理增长制约条件及增长方式局部相互作用适应度模型Baralási-Albert模型扩展研究初始吸引度69五、常用软件SasMatlabPajekOriginNetdrawWaxmanGt-itmTiersBriteInetPlarg五、常用软件SasWaxman70六、主要参考文献Albert,R.,H.Jeong,andA.-L.Barabási,DiameteroftheWorld-Wide-Web,1999,Nature(London)401,130.Barabási,A.-L.,andR.Albert,Emergenceofscalinginrandomnetworks,1999,Science286,509.Barabási,A.-L.,R.Albert,andH.Jeong,Mean-fieldtheoryforscale-freerandomnetworks,1999,PhysicaA272,173.Albert,R.,andA.-L.Barabási,statisticalMechanicsofcomplexnetwork,2002,Rev.Mod.Phys.Vol.74,No.1,47-97.六、主要参考文献Albert,R.,H.Jeong,71精品课件！精品课件！72精品课件！精品课件！73谢谢！谢谢！74目录概率统计预备知识网络(图)的基本概念规则图和随机网Scale-free网络常用软件参考文献目录75一、概率统计预备知识一、概率统计预备知识76目录随机变量与分布函数（离散、连续）随机变量的数字特征（数学期望、方差）泊松分布幂函数指数函数目录随机变量与分布函数（离散、连续）77随机变量与分布函数对某个随机试验，如果每次试验的结果可以用一个数X来表示，而且对任何实数k，X<x有着确定的概率，则称X是随机变量。随机变量X的值小于实数k的概率P(X<x)是x的函数，记作F(k)=P(X<x),函数F(x)叫做随机变量X的分布函数。随机变量与分布函数对某个随机试验，如果每次试验的结果可以78离散型分布若随机变量X只取有限个或可数个孤立的值，并且对应这些值有确定的概率，即，则称X是离散随机变量（或X是离散分布的），称为的概率分布，它满足下列条件：离散型分布若随机变量X只取有限个或可数个孤立的值79连续型分布若存在一个非负函数，使随机变量X的分布函数可以表示为则X称为连续随机变量（或X是连续分布的），称为随机变量X的概率密度。

连续型分布若存在一个非负函数，使随机变量X的分布80的性质的性质81随机变量的数字特征随机变量的数学期望定义1设x是离散型随机变量，它的概率函数是随机变量的数字特征随机变量的数学期望82随机变量的数学期望，反映了随机变量取值的平均水平，即均值，是随机变量的算术平均。

随机变量的数学期望，反映了随机变量取值的平均水平，即均值，是83方差为随机变量的方差。方差是刻划随机变量取值离差程度的一个数。X的方差的算术平方根称为标准差(或均方差）

方差为随机变量的方差。方差是刻划随机变量取值离差程度的84若X是离散型随机变量，则方差为：若X是离散型随机变量，则方差为：85泊松定理设随机变量Xn(n=0，1，2，…)服从二项分布，其分布律为其中设为常数则泊松定理设随机变量Xn(n=0，1，2，…)服从二项分86泊松分布

设随机变量X所有可能取的值为0，1，2，…，而取各个可能值的概率为：

若>0是常数，则称变量X服从参数为泊松分布，记为

泊松分布设随机变量X所有可能取的值为0，1，2，…，而取87<k><k>88于是，x的数学期望为：即于是，x的数学期望为：即89复杂网络的无标度特性课件90所以，X的方差和均方差分别为：

所以，X的方差和均方差分别为：91指数函数对公式线性化，两边取对数得令则指数函数对公式线性化，两边取对数得92指数函数指数函数93幂函数式中为实数。对公式线性化，两边取对数，得令，，得函数形式为：幂函数式中为实数。令，94幂函数变量代换可在双对数坐标上得直线，

幂函数变量代换可在双对数坐标上得直线，95二、网络(图)的基本概念二、网络(图)的基本概念96中国教科网中国教科网97网络(图)的基本概念节点通常用来表示系统中的部件；边通常用来表示系统中部件之间的关系。网络(图)就是由节点与节点之间的关系构成的一张图。网络(图)的基本概念节点通常用来表示系统中的部件；98中国教科网拓扑结构中国教科网拓扑结构99网络（图）的基本概念关联与邻接度、平均度节点的度分布最短路径与平均路径长度群系数网络（图）的基本概念关联与邻接100网络(图)的基本概念aedcb网络(图)的基本概念aedcb101有向图、无向图、不连通图有向图、无向图、不连通图102网络(图)的基本概念节点的度分布是指网络（图）中度为的节点的概率随节点度的变化规律。网络(图)的基本概念节点的度分布是指网络（图）中度为的节103网络(图)的基本概念最短路径就是从指定始点到指定终点的所有路径中总权最小的一条路经。平均路径长度是指所有点对之间的最短路径的算术平均值。网络(图)的基本概念最短路径就是从指定始点到指定终点的所有路104网络(图)的基本概念集群系数(Clusteringcoefficient)反映网络的群集程度，定义为网络的平均度与网络规模之比。网络(图)的基本概念集群系数(Clusteringcoef1052277

55553311网络(图)的基本概念227755553311网络(图)的基本概念106节点1到7之间的最短路13，平均路径长度5.47，平均度为3.4，集群系数为0.48。网络(图)的基本概念节点1到7之间的最短路13，平均路径长度5.47，网络(图)107三、规则图和随机图规则图的特征如果系统中节点及其与边的关系是固定的，每个节点都有相同的度数，就可以用规则图来表示这个系统。随机图的特征如果系统中节点及其与边的关系不确定，就只能用随机图来表示这个系统。三、规则图和随机图规则图的特征108规则图的特征平均度为3。规则图的特征平均度为3。109随机图的特征节点确定，但边以概率任意连接。节点不确定，点边关系也不确定。随机图的特征节点确定，但边以概率任意连接。110随机图——节点19，边43平均度为2.42，集群系数为0.13。随机图——节点19，边43平均度为2.42，集群系数为0.1111随机图——节点42，边118平均度为5.62，集群系数为0.133。随机图——节点42，边118平均度为5.62，集群系数为0.112四、Scale-free网络四、Scale-free网络113目录早期网络模型无标度Scale-free网络BA模型目录早期网络模型114早期网络模型ER模型小世界模型早期网络模型ER模型115ER模型Erdös和Rényi（ER）最早提出随机网络模型并对模型进行了深入研究，他们是用概率统计方法研究随机图统计特性的创始人。在模型开始阶段给定N个节点，没有边，以概率p用边连接任意一对节点，用这样的方法产生一随机网络。ER模型Erdös和Rényi（ER）最早提出随机网络模型116复杂网络的无标度特性课件117ER模型Erdös和Rényi（1959）首先研究了在随机网络中最大和最小度的分布，Bollobás(1981)随后得到了所有度分布的形式，推导出度数为k的节点数遵从平均值为的泊松分布，即ER模型Erdös和Rényi（1959）首先研究了在随机网118Connectwithprobabilitypp=1/6N=10k~1.5PoissondistributionConnectwithprobabilitypp=1/119小世界模型为了描述从一个局部有序系统到一个随机网络的转移过程，Watts和Strogatz（WS）提出了一个新模型，通常称为小世界网络模型。WS模型始于一具有N个节点的一维网络，网络的节点与其最近的邻接点和次邻接点相连接，然后每条边以概率p重新连接。约束条件为节点间无重边，无自环。小世界模型为了描述从一个局部有序系统到一个随机网络的转移过程120C(p):clusteringcoeff.L(p):averagepathlengthP(k)=0.1p(k)=0.3C(p):clusteringcoeff.121小世界模型当p等于0时，对应的网络规则图。两个节点间的平均距离<L>线性地随N增长而增长，集群系数大。当p等于1时，系统变为随机图。<L>对数地随N增长而增长，且集群系数随N减少而减少。在p等于（0，1）区间任意值时，模型显示出小世界特性，<L>约等于随机图的值，网络具有高度集群性。小世界模型当p等于0时，对应的网络规则图。两个节点间的平均距122复杂网络都具有分布于平均值两边的度分布曲线吗？复杂网络都具有分布于平均值两边的度分布曲线吗？123无标度(Scale-free)网络Scale-free网络的发现Scale-free网络的特性无标度(Scale-free)网络Scale-free网络的124Scale-free)网络的发现信息交换网（万维网、国际互联网、电话网、电力网）社会网络（电影演员合作网、科研合作图、引文网、人类性接触网、语言学网）生物网络（细胞网络、生态网络、蛋白质折叠）Scale-free)网络的发现信息交换网（万维网、国际互联125复杂网络的无标度特性课件126复杂网络的无标度特性课件127Scale-free网络的特性度分布呈幂率分布中枢节点出现稳健性脆弱性Scale-free网络的特性度分布呈幂率分布128复杂网络的无标度特性课件129复杂网络的无标度特性课件130无标度网络与随机图特性比较无标度网络与随机图特性比较131无标度（Scale-free）网络无标度模型由Albert-LászlóBarabási和RékaAlbert在1999年首先提出，现实网络的无标度特性源于众多网络所共有的两种生成机制：（ⅰ）网络通过增添新节点而连续扩张；（ⅱ）新节点择优连接到具有大量连接的节点上。无标度（Scale-free）网络无标度模型由Albert-132BA模型增长和择优连接这两种要素激励了Barabási－Albert模型的提出，该模型首次导出度分布按幂函数规律变化的网络。模型的算法如下：（1）增长：开始于较少的节点数量（m0），在每个时间间隔增添一个具有m（≤m0）条边的新节点，连接这个新节点到m个不同的已经存在于系统中的节点上。（2）择优连接：在选择新节点的连接点时，假设新节点连接到节点i的概率π取决于节点i的度数即BA模型增长和择优连接这两种要素激励了Barabási－Al133经过t时间间隔后，该算法程序产生一具有N=t+m0个节点，mt条边的网络。数量模拟表明具有k条边的节点的概率服从指数为r=3的幂指数分布。经过t时间间隔后，该算法程序产生一具有N=t+m0个节点，m134P(k)~k-3A.-L.Barabási,R.Albert,Science286,509(1999)P(k)~k-3A.-L.Barabási,R.Alb135BA模型（a)Barabási-Albert模拟的度分布。（b）不同系统规模下的。

BA模型（a)Barabási-Albert模拟的度分布。136BA模型设节点i的度满足动态方程：分母求和是对系统中除新进入系统的节点外的所有节点进行的，则BA模型设节点i的度满足动态方程：137BA模型当t足够大时，有