复杂网络数学建模精选PPT.ppt

《复杂网络数学建模精选PPT.ppt》由会员分享，可在线阅读，更多相关《复杂网络数学建模精选PPT.ppt（52页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、复杂网络数学建模第1页，此课件共52页哦一、网络图的基本概念第2页，此课件共52页哦n n节点、边n n关联与邻接n n度 k、平均度 n n节点的度分布p(k)n n最短路径与平均路径长度（Dijkstra算法）n n集聚系数 C第3页，此课件共52页哦aedcb第4页，此课件共52页哦有向图、无向图、不连通图第5页，此课件共52页哦n n节点的度分布是指网络（图）中度为 的节点的概率 随节点度 的变化规律。第6页，此课件共52页哦n n两点之间的最短路径：从指定始点到指定终点的所有路径中长度最小的一条路径。n n网络平均路径长度：所有点对之间的最短路径的算术平均值。第7页，此课件共52页哦

2、22 77 55553311第8页，此课件共52页哦节点1到7之间的最短路13，平均路径长度5.47，平均度为3.4，集聚系数为0.48。第9页，此课件共52页哦二、早期网络模型第10页，此课件共52页哦规则图和随机图n n规则图系统中节点及其与边的关系是固定的，每个节点都有相同的度数。n n随机图平均说来系统中节点及其与边的关系不确定。第11页，此课件共52页哦规则图的特征平均度为3。第12页，此课件共52页哦随机图的特征n n节点确定，但边以概率 任意连接。n n节点不确定，点边关系也不确定。第13页，此课件共52页哦随机图节点19，边43平均度为2.42，集聚系数为0.13。第14页，此

3、课件共52页哦随机图节点节点4242，边，边118118平均度为5.62，集聚系数为0.133。第15页，此课件共52页哦ER模型n nErds和Rnyi（ER）最早提出随机网络模型并进行了深入研究，他们是用概率统计方法研究随机图统计特性的创始人。n n给定N个节点，没有边，以概率p用边连接任意一对节点，用这样的方法产生一随机网络。第16页，此课件共52页哦第17页，此课件共52页哦ER模型n n节点的度分布：平均值为 的泊松分布 第18页，此课件共52页哦Connect with probability pp=1/6 N=10 k 1.5Poisson distribution第19页，此课

4、件共52页哦三、复杂网络模型n n小世界（small-world)网络模型n n无标度（scale-free)网络模型第20页，此课件共52页哦小世界模型n n为了描述从一个局部有序系统到一个随机网络的转移过程，Watts和 Strogatz（WS）提出了一个新模型，通常称为小世界网络模型。n nWS模型始于一具有N个节点的一维网络，网络的节点与其最近的邻接点和次邻接点相连接，然后每条边以概率p重新连接。约束条件为节点间无重边，无自环。第21页，此课件共52页哦C(p):clustering coeff.L(p):average path lengthP(k)=0.1 p(k)=0.3第22页

5、，此课件共52页哦n n当当p p等于等于0 0时，对应于规则图。两个节点间的平均距离时，对应于规则图。两个节点间的平均距离线性地随线性地随N N增长而增长，集聚系数大。增长而增长，集聚系数大。n n当当p p等等于于1 1时时，系系统统变变为为随随机机图图。对对数数地地随随N N增增长长而而增长，且集聚系数随增长，且集聚系数随N N减少而减少。减少而减少。n n在在p p等等于于（0 0，1 1）区区间间任任意意值值时时，约约等等于于随随机机图图的值，网络具有高度集聚性的值，网络具有高度集聚性-小世界效应。小世界效应。第23页，此课件共52页哦n n复杂网络都具有分布于平均值两边的度分布曲线

6、吗？第24页，此课件共52页哦无标度(Scale-free)网络n nScale-free网络的发现n nScale-free网络的特性第25页，此课件共52页哦Scale-free)网络的发现n n信息交换网（万维网、国际互联网、电话网、电力网万维网、国际互联网、电话网、电力网）n n社会网络（电影演员合作网、科研合作图、引文网、人类电影演员合作网、科研合作图、引文网、人类性接触网、语言学网性接触网、语言学网）n n生物网络（细胞网络、生态网络、蛋白质折叠细胞网络、生态网络、蛋白质折叠）第26页，此课件共52页哦第27页，此课件共52页哦第28页，此课件共52页哦Scale-free网络的特

7、性n n度分布呈幂率分布n n中枢节点出现n n鲁棒性n n脆弱性第29页，此课件共52页哦第30页，此课件共52页哦第31页，此课件共52页哦无标度网络与随机图特性比较第32页，此课件共52页哦无标度（Scale-free）网络n n无标度模型由Albert-Lszl Barabsi和Rka Albert在1999年首先提出，现实网络的无标度特性源于众多网络所共有的两种生成机制：（）网络通过增添新节点而连续扩张；（）新节点择优连接到具有大量连接的节点上。第33页，此课件共52页哦BA模型n n增长和择优连接这两种要素激励了增长和择优连接这两种要素激励了BarabBarab sisiAlber

8、tAlbert模模型的提出，该模型首次导出度分布按幂函数规律变化的网型的提出，该模型首次导出度分布按幂函数规律变化的网络络。n n模型的算法如下：（1 1）增增长长：开开始始于于较较少少的的节节点点数数量量（m m0 0），在在每每个个时时间间间间隔隔增增添添一一个个具具有有m m（mm0 0）条条边边的的新新节节点点，连连接接这这个个新新节节点点到到m m个个不不同的已经存在于系统中的节点上。同的已经存在于系统中的节点上。（2 2）择择优优连连接接：在在选选择择新新节节点点的的连连接接点点时时，假假设设新新节节点点连连接接到到节点节点i i的概率的概率取决于节点取决于节点i i的度数即的度数

9、即第34页，此课件共52页哦n n经过t时间间隔后，该算法程序产生一具有N=t+m0个节点，mt条边的网络。n n数量模拟表明具有k条边的节点的概率服从指数为r=3的幂指数分布。第35页，此课件共52页哦P(k)k-3A.-L.Barabsi,R.Albert,Science 286,509(1999)第36页，此课件共52页哦BA模型（a)Barabsi-Albert模拟的度分布。（b）不同系统规模下的 。第37页，此课件共52页哦BA模型设节点 i 的度 满足动态方程：分母求和是对系统中除新进入系统的节点外的所有节点进行的，则第38页，此课件共52页哦BA模型当t足够大时，有解微分方程，有

10、第39页，此课件共52页哦由初始条件得解为 式中可给出度小于k的节点的概率 第40页，此课件共52页哦设在相同的时间间隔，添加节点到网络 中，值具有常数概率密度 代入前式t趋于无穷时度分布 式中第41页，此课件共52页哦n n模型的度分布是与时间无关的渐进分布且与系统规模无关。n n幂律度分布的系数与 成正比。n n无标度模型的动态特性可以用各种分析方法给出：平均场理论 主方程法 变化率方程法 第42页，此课件共52页哦Baralsi-Albert模型的限制条件 n n保持了网络的增长特性，不考虑择优连接，网络度分布呈指数衰减。n n消除了增长过程，只考虑择优连接，络度分布围绕其均值为一高斯分

11、布。n nBA认为，这两个条件缺一不可，否则不能出现幂率度分布。第43页，此课件共52页哦Baralsi-Albert模型扩展研究n n初始吸引度n n非线性择优连接n n择优连接的更迭机理 n n增长制约条件及增长方式n n局部相互作用n n适应度模型第44页，此课件共52页哦其他工作n n流驱动的复杂网络模型（科大王文旭等）n n具有随机响应的动态有向小世界模型（南航朱陈平等）第45页，此课件共52页哦六、主要参考文献n nAlbert,R.,H.Jeong,and A.-L.BarabAlbert,R.,H.Jeong,and A.-L.Barab si,Diameter of the

12、si,Diameter of the World-Wide-Web,1999,Nature(London)401,130.World-Wide-Web,1999,Nature(London)401,130.n nBarabBarab si,A.-L.,and R.Albert,Emergence of scaling in si,A.-L.,and R.Albert,Emergence of scaling in random networks,1999,Science 286,509.random networks,1999,Science 286,509.n nBarabBarab si,

13、A.-L.,R.Albert,and H.Jeong,Mean-field si,A.-L.,R.Albert,and H.Jeong,Mean-field theory for scale-free random networks,1999,Physica A theory for scale-free random networks,1999,Physica A 272,173.272,173.n nAlbert,R.,and A.-L.BarabAlbert,R.,and A.-L.Barab si,statistical Mechanics of si,statistical Mech

14、anics of complex network,2002,Rev.Mod.Phys.Vol.74,No.1,47-complex network,2002,Rev.Mod.Phys.Vol.74,No.1,47-97.97.第46页，此课件共52页哦谢谢大家！谢谢大家！第47页，此课件共52页哦网络图的基本概念n n图的基本元素：节点、边n n关联，邻接n n有限图，无限图n n规则图，随机图n n有向图，无向图第48页，此课件共52页哦网络图的基本概念n n度、平均度n n节点的度分布n n最短路径与平均路径长度n n集聚系数第49页，此课件共52页哦复杂网络数学建模概述第50页，此课件共52页哦复杂网络数学建模概述第51页，此课件共52页哦第52页，此课件共52页哦