资源预览内容
第1页 / 共50页
第2页 / 共50页
第3页 / 共50页
第4页 / 共50页
第5页 / 共50页
第6页 / 共50页
第7页 / 共50页
第8页 / 共50页
第9页 / 共50页
第10页 / 共50页
亲,该文档总共50页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
复杂网络数学建模概述南京航空航天大学应用物理系 朱陈平一、网络图的基本概念n节点、边n关联与邻接n度 k、平均度 n节点的度分布p(k)n最短路径与平均路径长度 (Dijkstra算法)n集聚系数 Caedcb有向图、无向图、不连通图n节点的度分布是指网络(图)中度 为 的节点的概率 随节点度 的变化规律。n两点之间的最短路径:从指定始点到指定终点的所有路径中 长度最小的一条路径。n网络平均路径长度:所有点对之间的最短路径的算术平均 值。22 77 55553311节点1到7之间的最短路13,平均路径长度5.47,平均度为3.4,集聚系数为0.48。二、早期网络模型规则图和随机图n规则图系统中节点及其与边的关系是固定的 ,每个节点都有相同的度数。n随机图平均说来系统中节点及其与边的关系 不确定。规则图的特征平均度为3。随机图的特征n节点确定,但边以概率 任意连接 。n节点不确定,点边关系也不确定。随机图节点19,边43平均度为2.42,集聚系数为0.13。随机图节点42,边118平均度为5.62,集聚系数为0.133。ER模型nErds和Rnyi (ER)最早提出随机网络 模型并进行了深入研究,他们是用概率统 计方法研究随机图统计特性的创始人。n给定N个节点,没有边,以概率p用边连接 任意一对节点,用这样的方法产生一随机 网络。ER模型n节点的度分布:平均值为 的泊松分布 Connect with probability pp=1/6 N=10 k 1.5Poisson distribution三、复杂网络模型n小世界(small- world) 网络模型n无标度 (scale-free) 网络模型小世界模型n为了描述从一个局部有序系统到一个随 机网络的转移过程,Watts和 Strogatz (WS)提出了一个新模型,通常称为小 世界网络模型。nWS模型始于一具有N个节点的一维网络 ,网络的节点与其最近的邻接点和次邻 接点相连接,然后每条边以概率p重新连 接。约束条件为节点间无重边,无自环 。C(p) : clustering coeff. L(p) : average path lengthP(k)=0.1 p(k)=0.3n当p等于0时,对应于规则图。两个节点间的平均 距离线性地随N增长而增长,集聚系数大。n当p等于1时,系统变为随机图。 对数地随N 增长而增长,且集聚系数随N减少而减少。n在p等于(0,1)区间任意值时,约等于随 机图的值,网络具有高度集聚性-小世界效应。n复杂网络都具有分布于平均值两边 的度分布曲线吗?无标度(Scale-free)网络nScale-free网络的发现nScale-free网络的特性Scale-free)网络的发现n信息交换网(万维网、国际互联网、电话网、电力网 )n社会网络(电影演员合作网、科研合作图、引文网、人类性接触网、语言学网)n生物网络(细胞网络、生态网络、蛋白质折叠)Scale-free网络的特性n度分布呈幂率分布n中枢节点出现n鲁棒性n脆弱性无标度网络与随机图特性比较无标度(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的幂指数分布。P(k) k-3A.-L.Barabsi, R. Albert, Science 286, 509 (1999)BA模型(a)Barabsi-Albert模拟的度分布。(b)不同系统规模下的 。 BA模型设节点 i 的度 满足动态方程:分母求和是对系统中除新进入系统的节点外 的所有节点进行的 ,则BA模型当t足够大时,有解微分方程,有由初始条件得解为 式中可给出度小于k的节点的概率 设在相同的时间间隔,添加节点到网络 中, 值具有常数概率密度代入前式t趋于无穷时度分布 式中n模型的度分布是与时间无关的渐进分布且 与系统规模无关。 n幂律度分布的系数与 成正比 。n无标度模型的动态特性可以用各种分析方 法给出 :平均场理论主方程法变化率方程法 Baralsi-Albert模型的限制条件 n保持了网络的增长特性,不考虑择优连接 ,网络度分布呈指数衰减。 n消除了增长过程,只考虑择优连接,络度 分布围绕其均值为一高斯分布。nBA认为,这两个条件缺一不可,否则不能 出现幂率度分布。Baralsi-Albert模型扩展研究n初始吸引度n非线性择优连接n择优连接的更迭机理 n增长制约条件及增长方式n局部相互作用n适应度模型其他工作n流驱动的复杂网络模型(科大王文旭等)n具有随机响应的动态有向小世界模型 (南航朱陈平等)六、主要参考文献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.谢谢大家!网络图的基本概念n图的基本元素:节点、边n关联,邻接n有限图,无限图n规则图,随机图n有向图,无向图网络图的基本概念n度、平均度n节点的度分布n最短路径与平均路径长度n集聚系数
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号