复杂网络数学建模.pptVIP

无标度网络与随机图特性比较 无标度（Scale-free）网络 无标度模型由Albert-László Barabási和Réka Albert在1999年首先提出，现实网络的无标度特性源于众多网络所共有的两种生成机制： （ⅰ）网络通过增添新节点而连续扩张； （ⅱ）新节点择优连接到具有大量连接的节点上。 BA模型 增长和择优连接这两种要素激励了Barabási－Albert模型的提出，该模型首次导出度分布按幂函数规律变化的网络。 模型的算法如下： （1）增长：开始于较少的节点数量（m0），在每个时间间隔增添一个具有m（≤m0）条边的新节点，连接这个新节点到m个不同的已经存在于系统中的节点上。 （2）择优连接：在选择新节点的连接点时，假设新节点连接到节点i的概率π取决于节点i的度数即 经过t时间间隔后，该算法程序产生一具有N=t+m0个节点，mt条边的网络。 数量模拟表明具有k条边的节点的概率服从指数为r=3的幂指数分布。 P(k) ~k-3 A.-L.Barabási, R. Albert, Science 286, 509 (1999) BA模型 （a)Barabási-Albert模拟的度分布。 （b）不同系统规模下的 。 BA模型 设节点 i 的度 满足动态方程： 分母求和是对系统中除新进入系统的节点外的所有节点进行的 ，则 BA模型 当t足够大时，有 解微分方程，有 由初始条件得 解为 式中 可给出度小于k的节点的概率 设在相同的时间间隔，添加节点到网络 中， 值具有常数概率密度 代入前式 t趋于无穷时度分布 式中 模型的度分布是与时间无关的渐进分布且与系统规模无关。 幂律度分布的系数与 成正比 。 无标度模型的动态特性可以用各种分析方法给出 ： 平均场理论 主方程法 变化率方程法 Baralási-Albert模型的限制条件 保持了网络的增长特性，不考虑择优连接，网络度分布呈指数衰减。 消除了增长过程，只考虑择优连接，络度分布围绕其均值为一高斯分布。 BA认为，这两个条件缺一不可，否则不能出现幂率度分布。 Baralási-Albert模型扩展研究 初始吸引度 非线性择优连接 择优连接的更迭机理 增长制约条件及增长方式 局部相互作用 适应度模型 其他工作 流驱动的复杂网络模型（科大王文旭等） 具有随机响应的动态有向小世界模型 （南航朱陈平等） 六、主要参考文献 Albert, R., H. Jeong, and A.-L. Barabási, Diameter of the World-Wide-Web,1999, Nature (London)401, 130. Barabási, A.-L., and R. Albert, Emergence of scaling in random networks, 1999, Science 286, 509 . Barabási, 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. Barabási, statistical Mechanics of complex network, 2002, Rev. Mod. Phys. Vol. 74, No.1, 47-97. 谢谢大家！ 网络图的基本概念 图的基本元素：节点、边 关联，邻接 有限图，无限图 规则图，随机图 有向图，无向图 网络图的基本概念 度、平均度 节点的度分布 最短路径与平均路径长度 集聚系数 复杂网络数学建模概述 复杂网络数学建模概述 * 复杂网络数学建模概述 一、网络图的基本概念 节点、边 关联与邻接 度 k、平均度 k 节点的度分布p(k) 最短路径与平均路径长度 （Dijkstra算法） 集聚系数 C a e d c b 有向图、无向图、不连通图 节点的度分布是指网络（图）中度为 的节点的概率 随节点度 的变化规律。 两点之间的最短路径： 　　　从指定始点到指定终点的所有路径中长度最小的一条路径。 网络平均路径长度： 　　　所有点对之间的最短路径的算术平均值。 2 2 7 7 5 5 5 5 3 3 1 1 节点1到7之间的最短路13，平均路径长度5.47， 平均度为3.4，集聚系数为0.48。 二、早期