《复杂网络的无标度特性课件》由会员分享，可在线阅读，更多相关《复杂网络的无标度特性课件（73页珍藏版）》请在金锄头文库上搜索。
1、复杂网络的无标度特性,上海理工大学 管理学院、系统工程研究所 张宁,目录,概率统计预备知识 网络(图)的基本概念 规则图和随机网 Scale-free网络 常用软件 参考文献,一、概率统计预备知识,目录,随机变量与分布函数（离散、连续） 随机变量的数字特征（数学期望、方差） 泊松分布 幂函数 指数函数,随机变量与分布函数,对某个随机试验 ，如果每次试验的结果可以用一个数X来表示，而且对任何实数k，Xx有着确定的概率，则称X是随机变量。 随机变量X的值小于实数k的概率P(Xx)是x的函数，记作 F(k)=P(Xx) ,函数F(x)叫做随机变量X的分布函数。,离散型分布,若随机变量X只取有限个或可
2、数个孤立的值 ，并且对应这些值有确定的概率，即 ，则称X是离散随机变量（或X是离散分布的）， 称为的概率分布，它满足下列条件：,连续型分布,若存在一个非负函数 ，使随机变量X的分布函数 可以表示为 则X称为连续随机变量（或X是连续分布的）， 称为随机变量X的概率密度。,的性质,随机变量的数字特征,随机变量的数学期望 定义1 设x是离散型随机变量，它的概率函数是,随机变量的数学期望，反映了随机变量取值的平均水平，即均值，是随机变量的算术平均。,方差,为随机变量的方差。方差是刻划随机变量取值离差程度的一个数。 X的方差的算术平方根称为标准差(或均方差）,若X是离散型随机变量，则方差为：,泊松定理,
3、设随机变量Xn(n=0，1，2，)服从二项分布， 其分布律为,其中 设 为常数,则,泊松分布,设随机变量X所有可能取的值为0，1，2，而取各个可能值的概率为：,若 0是常数，则称变量X服从参数为 泊松分布，记为,于是，x的数学期望为：,即,所以，X的方差和均方差分别为：,指数函数,对公式线性化，两边取对数得 令 则,指数函数,幂函数,式中 为实数。 对公式线性化，两边取对数，得,令 ， ， 得,函数形式为：,幂函数,变量代换可在双对数坐标上得直线，,二、网络(图)的基本概念,中国教科网,网络(图)的基本概念,节点通常用来表示系统中的部件； 边通常用来表示系统中部件之间的关系。 网络(图)就是由
4、节点与节点之间的关系构成的一张图。,中国教科网拓扑结构,网络（图）的基本概念,关联与邻接 度、平均度 节点的度分布 最短路径与平均路径长度 群系数,网络(图)的基本概念,a,e,d,c,b,有向图、无向图、不连通图,网络(图)的基本概念,节点的度分布是指网络（图）中度为 的节点的概率 随节点度 的变化规律。,网络(图)的基本概念,最短路径就是从指定始点到指定终点的所有路径中总权最小的一条路经。 平均路径长度是指所有点对之间的最短路径的算术平均值。,网络(图)的基本概念,集群系数(Clustering coefficient)反映网络的群集程度，定义为网络的平均度与网络规模之比。,2,2,7,7
5、,5,5,5,5,3,3,1,1,网络(图)的基本概念,节点1到7之间的最短路13，平均路径长度5.47， 平均度为3.4，集群系数为0.48。,网络(图)的基本概念,三、规则图和随机图,规则图的特征 如果系统中节点及其与边的关系是固定的，每个节点都有相同的度数，就可以用规则图来表示这个系统。 随机图的特征 如果系统中节点及其与边的关系不确定，就只能用随机图来表示这个系统。,规则图的特征,平均度为3。,随机图的特征,节点确定，但边以概率 任意连接。 节点不确定，点边关系也不确定。,随机图节点19，边43,平均度为2.42，集群系数为0.13。,随机图节点42，边118,平均度为5.62，集群系
6、数为0.133。,四、Scale-free网络,目录,早期网络模型 无标度Scale-free网络 BA模型,早期网络模型,ER模型 小世界模型,ER模型,Erds和Rnyi （ER）最早提出随机网络模型并对模型进行了深入研究，他们是用概率统计方法研究随机图统计特性的创始人。 在模型开始阶段给定N个节点，没有边，以概率p用边连接任意一对节点，用这样的方法产生一随机网络。,ER模型,Erds和Rnyi（1959）首先研究了在随机网络中最大和最小度的分布，Bollobs(1981)随后得到了所有度分布的形式，推导出度数为k的节点数遵从平均值为 的泊松分布，即,Poisson distributio
7、n,小世界模型,为了描述从一个局部有序系统到一个随机网络的转移过程，Watts和 Strogatz（WS）提出了一个新模型，通常称为小世界网络模型。 WS模型始于一具有N个节点的一维网络，网络的节点与其最近的邻接点和次邻接点相连接，然后每条边以概率p重新连接。约束条件为节点间无重边，无自环。,C(p) : clustering coeff. L(p) : average path length,P(k)=0.1 p(k)=0.3,小世界模型,当p等于0时，对应的网络规则图。两个节点间的平均距离线性地随N增长而增长，集群系数大。 当p等于1时，系统变为随机图。 对数地随N增长而增长，且集群系数随
8、N减少而减少。 在p等于（0，1）区间任意值时，模型显示出小世界特性，约等于随机图的值，网络具有高度集群性。,复杂网络都具有分布于平均值两边的度分布曲线吗？,无标度(Scale-free)网络,Scale-free网络的发现 Scale-free网络的特性,Scale-free)网络的发现,信息交换网（万维网、国际互联网、电话网、电力网） 社会网络（电影演员合作网、科研合作图、引文网、人类性接触网、语言学网） 生物网络（细胞网络、生态网络、蛋白质折叠）,Scale-free网络的特性,度分布呈幂率分布 中枢节点出现 稳健性 脆弱性,无标度网络与随机图特性比较,无标度（Scale-free）网络
9、,无标度模型由Albert-Lszl Barabsi和Rka Albert在1999年首先提出，现实网络的无标度特性源于众多网络所共有的两种生成机制： （）网络通过增添新节点而连续扩张； （）新节点择优连接到具有大量连接的节点上。,BA模型,增长和择优连接这两种要素激励了BarabsiAlbert模型的提出，该模型首次导出度分布按幂函数规律变化的网络。 模型的算法如下： （1）增长：开始于较少的节点数量（m0），在每个时间间隔增添一个具有m（m0）条边的新节点，连接这个新节点到m个不同的已经存在于系统中的节点上。 （2）择优连接：在选择新节点的连接点时，假设新节点连接到节点i的概率取决于节点i
10、的度数即,经过t时间间隔后，该算法程序产生一具有N=t+m0个节点，mt条边的网络。 数量模拟表明具有k条边的节点的概率服从指数为r=3的幂指数分布。,P(k) k-3,A.-L.Barabsi, R. Albert, Science 286, 509 (1999),BA模型,（a)Barabsi-Albert模拟的度分布。 （b）不同系统规模下的 。,BA模型,设节点 i 的度 满足动态方程： 分母求和是对系统中除新进入系统的节点外的所有节点进行的 ，则,BA模型,当t足够大时，有 解微分方程，有,由初始条件得,解为 式中,可给出度小于k的节点的概率,设在相同的时间间隔，添加节点到网络 中，
11、 值具有常数概率密度,代入前式,t趋于无穷时度分布,式中,模型的度分布是与时间无关的渐进分布且与系统规模无关。 幂律度分布的系数与 成正比 。 无标度模型的动态特性可以用各种分析方法给出 ： 连续域理论 主方程法 变化率方程法,Baralsi-Albert模型的限制条件,保持了网络的增长特性，不考虑择优连接，网络度分布呈指数衰减。 消除了增长过程，只考虑择优连接，络度分布围绕其均值为一高斯分布。,Baralsi-Albert模型扩展研究,初始吸引度 非线性择优连接 择优连接的更迭机理 增长制约条件及增长方式 局部相互作用 适应度模型,五、常用软件,Sas Matlab Pajek Origin
12、 Netdraw,Waxman Gt-itm Tiers Brite Inet Plarg,六、主要参考文献,Albert, R., H. Jeong, and A.-L. Barabsi, Diameter of the World-Wide-Web,1999, Nature (London)401, 130. Barabsi, A.-L., and R. Albert, Emergence of scaling in random networks, 1999, Science 286, 509 . Barabsi, A.-L., R. Albert, and H. Jeong, Mean-field theory for scale-free random networks, 1999, Physica A 272, 173. Albert, R., and A.-L. Barabsi, statistical Mechanics of complex network, 2002, Rev. Mod. Phys. Vol. 74, No.1, 47-97.,谢谢！,
