复杂网络数学建模

复杂网络数学建模第一页，共五十二页，编辑于2023年，星期五一、网络图的基本概念第二页，共五十二页，编辑于2023年，星期五节点、边关联与邻接度k、平均度<k>节点的度分布p(k)最短路径与平均路径长度（Dijkstra算法）集聚系数C第三页，共五十二页，编辑于2023年，星期五aedcb第四页，共五十二页，编辑于2023年，星期五有向图、无向图、不连通图第五页，共五十二页，编辑于2023年，星期五节点的度分布是指网络（图）中度为的节点的概率随节点度的变化规律。 第六页，共五十二页，编辑于2023年，星期五两点之间的最短路径：从指定始点到指定终点的所有路径中长度最小的一条路径。网络平均路径长度：所有点对之间的最短路径的算术平均值。第七页，共五十二页，编辑于2023年，星期五2277

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

第三十七页，共五十二页，编辑于2023年，星期五BA模型设节点i的度满足动态方程：分母求和是对系统中除新进入系统的节点外的所有节点进行的，则第三十八页，共五十二页，编辑于2023年，星期五BA模型当t足够大时，有解微分方程，有第三十九页，共五十二页，编辑于2023年，星期五由初始条件得解为式中可给出度小于k的节点的概率

第四十页，共五十二页，编辑于2023年，星期五设在相同的时间间隔，添加节点到网络中，值具有常数概率密度

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

式中第四十一页，共五十二页，编辑于2023年，星期五模型的度分布是与时间无关的渐进分布且与系统规模无关。幂律度分布的系数与成正比。无标度模型的动态特性可以用各种分析方法给出： 平均场理论主方程法变化率方程法第四十二页，共五十二页，编辑于2023年，星期五Baralási-Albert模型的限制条件保持了网络的增长特性，不考虑择优连接，网络度分布呈指数衰减。消除了增长过程，只考虑择优连接，络度分布围绕其均值为一高斯分布。BA认为，这两个条件缺一不可，否则不能出现幂率度分布。第四十三页，共五十二页，编辑于2023年，星期五Baralási-Albert模型扩展研究初始吸引度非线性择优连接择优连接的更迭机理增长制约条件及增长方式局部相互作用适应度模型第四十四页，共五十二页，编辑于2023年，星期五其他工作流驱动的复杂网络模型（科大王文旭等）具有随机响应的动态有向小世界模型（南航朱陈平等）第四十五页，共五十二页，编辑于2023年，星期五六、主要参考文献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.第四十六页，共五十二页，编辑于2023年，星期五谢谢大家！第四十七页，共五十二页，编辑于2023年，星期五

网络图的基本概念

图的基