复杂无标度网络的特性讲稿.ppt
复杂无标度网络的特性第一页，讲稿共七十三页哦目录n概率统计预备知识n网络(图)的基本概念n规则图和随机网nScale-free网络n常用软件n参考文献第二页，讲稿共七十三页哦一、概率统计预备知识第三页，讲稿共七十三页哦目录n随机变量与分布函数（离散、连续）n随机变量的数字特征（数学期望、方差）n泊松分布n幂函数n指数函数第四页，讲稿共七十三页哦随机变量与分布函数n对某个随机试验 ，如果每次试验的结果可以用一个数X来表示，而且对任何实数k，Xx有着确定的概率，则称X是随机变量。n随机变量X的值小于实数k的概率P(Xx)是x的函数，记作 F(k)=P(X0是常数，则称变量X服从参数为 泊松分布，记为 第十四页，讲稿共七十三页哦第十五页，讲稿共七十三页哦于是，x的数学期望为：即第十六页，讲稿共七十三页哦第十七页，讲稿共七十三页哦所以，X的方差和均方差分别为：第十八页，讲稿共七十三页哦指数函数bxyae对公式线性化，两边取对数得令则lnlnyabxln,lnuy caucbx第十九页，讲稿共七十三页哦指数函数ucbx第二十页，讲稿共七十三页哦幂函数bya x式中 为实数。对公式线性化，两边取对数，得lnlnlnyabx令 ，得lnuylnvxlncaucb vb函数形式为：第二十一页，讲稿共七十三页哦幂函数变量代换可在双对数坐标上得直线，yabx第二十二页，讲稿共七十三页哦二、网络(图)的基本概念第二十三页，讲稿共七十三页哦中国教科网第二十四页，讲稿共七十三页哦网络(图)的基本概念n节点通常用来表示系统中的部件；n边通常用来表示系统中部件之间的关系。n网络(图)就是由节点与节点之间的关系构成的一张图。第二十五页，讲稿共七十三页哦中国教科网拓扑结构第二十六页，讲稿共七十三页哦网络（图）的基本概念n关联与邻接n度、平均度n节点的度分布n最短路径与平均路径长度n群系数第二十七页，讲稿共七十三页哦网络(图)的基本概念aedcb第二十八页，讲稿共七十三页哦有向图、无向图、不连通图第二十九页，讲稿共七十三页哦网络(图)的基本概念n节点的度分布是指网络（图）中度为 的节点的概率 随节点度 的变化规律。k)(kpk第三十页，讲稿共七十三页哦网络(图)的基本概念n最短路径就是从指定始点到指定终点的所有路径中总权最小的一条路经。n平均路径长度是指所有点对之间的最短路径的算术平均值。第三十一页，讲稿共七十三页哦网络(图)的基本概念n集群系数(Clustering coefficient)反映网络的群集程度，定义为网络的平均度与网络规模之比。NkC第三十二页，讲稿共七十三页哦22 77 55553311网络(图)的基本概念第三十三页，讲稿共七十三页哦节点1到7之间的最短路13，平均路径长度5.47，平均度为3.4，集群系数为0.48。网络(图)的基本概念第三十四页，讲稿共七十三页哦三、规则图和随机图n规则图的特征n如果系统中节点及其与边的关系是固定的，每个节点都有相同的度数，就可以用规则图来表示这个系统。n随机图的特征n如果系统中节点及其与边的关系不确定，就只能用随机图来表示这个系统。第三十五页，讲稿共七十三页哦规则图的特征平均度为3。第三十六页，讲稿共七十三页哦随机图的特征n节点确定，但边以概率 任意连接。n节点不确定，点边关系也不确定。p第三十七页，讲稿共七十三页哦随机图节点19，边43平均度为2.42，集群系数为0.13。第三十八页，讲稿共七十三页哦随机图节点42，边118平均度为5.62，集群系数为0.133。第三十九页，讲稿共七十三页哦四、Scale-free网络第四十页，讲稿共七十三页哦目录n早期网络模型n无标度Scale-free网络nBA模型第四十一页，讲稿共七十三页哦早期网络模型nER模型n小世界模型第四十二页，讲稿共七十三页哦ER模型nErds和Rnyi（ER）最早提出随机网络模型并对模型进行了深入研究，他们是用概率统计方法研究随机图统计特性的创始人。n在模型开始阶段给定N个节点，没有边，以概率p用边连接任意一对节点，用这样的方法产生一随机网络。第四十三页，讲稿共七十三页哦第四十四页，讲稿共七十三页哦ER模型nErds和Rnyi（1959）首先研究了在随机 网 络 中 最 大 和 最 小 度 的 分 布，Bollobs(1981)随后得到了所有度分布的形式，推导出度数为k的节点数遵从平均值为 的泊松分布，即 k!eP(k)k第四十五页，讲稿共七十三页哦Connect with probability pp=1/6 N=10 k 1.5Poisson distribution第四十六页，讲稿共七十三页哦小世界模型n为了描述从一个局部有序系统到一个随机网络的转移过程，Watts和 Strogatz（WS）提出了一个新模型，通常称为小世界网络模型。nWS模型始于一具有N个节点的一维网络，网络的节点与其最近的邻接点和次邻接点相连接，然后每条边以概率p重新连接。约束条件为节点间无重边，无自环。第四十七页，讲稿共七十三页哦C(p):clustering coeff.L(p):average path lengthP(k)=0.1 p(k)=0.3第四十八页，讲稿共七十三页哦小世界模型n当p等于0时，对应的网络规则图。两个节点间的平均距离线性地随N增长而增长，集群系数大。n当p等于1时，系统变为随机图。对数地随N增长而增长，且集群系数随N减少而减少。n在p等于（0，1）区间任意值时，模型显示出小世界特性，约等于随机图的值，网络具有高度集群性。第四十九页，讲稿共七十三页哦n复杂网络都具有分布于平均值两边的度分布曲线吗？第五十页，讲稿共七十三页哦无标度(Scale-free)网络nScale-free网络的发现nScale-free网络的特性第五十一页，讲稿共七十三页哦Scale-free)网络的发现n信息交换网（万维网、国际互联网、电话网、电力网）n社会网络（电影演员合作网、科研合作图、引文网、人类性接触网、语言学网）n生物网络（细胞网络、生态网络、蛋白质折叠）第五十二页，讲稿共七十三页哦kkp)(第五十三页，讲稿共七十三页哦第五十四页，讲稿共七十三页哦Scale-free网络的特性n度分布呈幂率分布n中枢节点出现n稳健性n脆弱性第五十五页，讲稿共七十三页哦第五十六页，讲稿共七十三页哦第五十七页，讲稿共七十三页哦N etw orkCCrandLNW W W0.10780.000233.1153127Internet0.18-0.30.0013.7-3.763015-6209A ctor0.790.000273.65225226C oauthorship0.430.000185.952909M etabolic0.320.0262.9282Foodw eb0.220.062.43134C.elegance0.280.052.65282无标度网络与随机图特性比较第五十八页，讲稿共七十三页哦无标度（Scale-free）网络n无标度模型由Albert-Lszl Barabsi和Rka Albert在1999年首先提出，现实网络的无标度特性源于众多网络所共有的两种生成机制：（）网络通过增添新节点而连续扩张；（）新节点择优连接到具有大量连接的节点上。第五十九页，讲稿共七十三页哦BA模型n增长和择优连接这两种要素激励了BarabsiAlbert模型的提出，该模型首次导出度分布按幂函数规律变化的网络。n模型的算法如下：（1）增长：开始于较少的节点数量（m0），在每个时间间隔增添一个具有m（m0）条边的新节点，连接这个新节点到m个不同的已经存在于系统中的节点上。（2）择优连接：在选择新节点的连接点时，假设新节点连接到节点i的概率取决于节点i的度数即第六十页，讲稿共七十三页哦n经过t时间间隔后，该算法程序产生一具有N=t+m0个节点，mt条边的网络。n数量模拟表明具有k条边的节点的概率服从指数为r=3的幂指数分布。jjiikkk)(第六十一页，讲稿共七十三页哦P(k)k-3A.-L.Barabsi,R.Albert,Science 286,509(1999)第六十二页，讲稿共七十三页哦BA模型（a)Barabsi-Albert模拟的度分布。（b）不同系统规模下的 。kp3000000tmN150000N100000N第六十三页，讲稿共七十三页哦BA模型设节点 i 的度 满足动态方程：分母求和是对系统中除新进入系统的节点外的所有节点进行的，则ik11njiiiikkmkmtkmmtkjj2第六十四页，讲稿共七十三页哦BA模型当t足够大时，有解微分方程，有tktkii2tdtkdkii2tkln21ln21ctk第六十五页，讲稿共七十三页哦由初始条件得 mitik解为 式中 iittmtk21可给出度小于k的节点的概率 ktikP 11ktmtPktkPii第六十六页，讲稿共七十三页哦设在相同的时间间隔，添加节点到网络 中，值具有常数概率密度 it tmtPi01011111mtktmktmtPi代入前式 110112ktmtmkktkPkPit趋于无穷时度分布 rkmkP1211r式中第六十七页，讲稿共七十三页哦n模型的度分布是与时间无关的渐进分布且与系统规模无关。n幂律度分布的系数与 成正比。n无标度模型的动态特性可以用各种分析方法给出：连续域理论 主方程法 变化率方程法 2m第六十八页，讲稿共七十三页哦Baralsi-Albert模型的限制条件 n保持了网络的增长特性，不考虑择优连接，网络度分布呈指数衰减。n消除了增长过程，只考虑择优连接，络度分布围绕其均值为一高斯分布。第六十九页，讲稿共七十三页哦Baralsi-Albert模型扩展研究n初始吸引度n非线性择优连接n择优连接的更迭机理 n增长制约条件及增长方式n局部相互作用n适应度模型第七十页，讲稿共七十三页哦五、常用软件nSasnMatlabnPajeknOriginnNetdrawnWaxmannGt-itmnTiers nBritenInetnPlarg第七十一页，讲稿共七十三页哦六、主要参考文献nAlbert,R.,H.Jeong,and A.-L.Barabsi,Diameter of the World-Wide-Web,1999,Nature(London)401,130.nBarabsi,A.-L.,and R.Albert,Emergence of scaling in random networks,1999,Science 286,509.nBarabsi,A.-L.,R.Albert,and H.Jeong,Mean-field theory for scale-free random networks,1999,Physica A 272,173.nAlbert,R.,and A.-L.Barabsi,statistical Mechanics of complex network,2002,Rev.Mod.Phys.Vol.74,No.1,47-97.第七十二页，讲稿共七十三页哦谢谢！第七十三页，讲稿共七十三页哦
