复杂网络的无标度特性.ppt

复杂网络的无标度特性 上海理工大学管理学院 系统工程研究所张宁 目录 概率统计预备知识网络 图 的基本概念规则图和随机网Scale free网络常用软件参考文献 一 概率统计预备知识 目录 随机变量与分布函数 离散 连续 随机变量的数字特征 数学期望 方差 泊松分布幂函数指数函数 随机变量与分布函数 对某个随机试验 如果每次试验的结果可以用一个数X来表示 而且对任何实数k X x有着确定的概率 则称X是随机变量 随机变量X的值小于实数k的概率P X x 是x的函数 记作F k P X x 函数F x 叫做随机变量X的分布函数 离散型分布 若随机变量X只取有限个或可数个孤立的值 并且对应这些值有确定的概率 即 则称X是离散随机变量 或X是离散分布的 称为的概率分布 它满足下列条件 连续型分布 若存在一个非负函数 使随机变量X的分布函数可以表示为则X称为连续随机变量 或X是连续分布的 称为随机变量X的概率密度 的性质 随机变量的数字特征 随机变量的数学期望定义1设x是离散型随机变量 它的概率函数是 随机变量的数学期望 反映了随机变量取值的平均水平 即均值 是随机变量的算术平均 方差 为随机变量的方差 方差是刻划随机变量取值离差程度的一个数 X的方差的算术平方根称为标准差 或均方差 若X是离散型随机变量 则方差为 泊松定理 设随机变量Xn n 0 1 2 服从二项分布 其分布律为 其中设为常数 则 泊松分布 设随机变量X所有可能取的值为0 1 2 而取各个可能值的概率为 若 0是常数 则称变量X服从参数为泊松分布 记为 于是 x的数学期望为 即 所以 X的方差和均方差分别为 指数函数 对公式线性化 两边取对数得令则 指数函数 幂函数 式中为实数 对公式线性化 两边取对数 得 令 得 函数形式为 幂函数 变量代换可在双对数坐标上得直线 二 网络 图 的基本概念 中国教科网 网络 图 的基本概念 节点通常用来表示系统中的部件 边通常用来表示系统中部件之间的关系 网络 图 就是由节点与节点之间的关系构成的一张图 中国教科网拓扑结构 网络 图 的基本概念 关联与邻接度 平均度节点的度分布最短路径与平均路径长度群系数 网络 图 的基本概念 a e d c b 有向图 无向图 不连通图 网络 图 的基本概念 节点的度分布是指网络 图 中度为的节点的概率随节点度的变化规律 网络 图 的基本概念 最短路径就是从指定始点到指定终点的所有路径中总权最小的一条路经 平均路径长度是指所有点对之间的最短路径的算术平均值 网络 图 的基本概念 集群系数 Clusteringcoefficient 反映网络的群集程度 定义为网络的平均度与网络规模之比 2 2 7 7 5 5 5 5 3 3 1 1 网络 图 的基本概念 节点1到7之间的最短路13 平均路径长度5 47 平均度为3 4 集群系数为0 48 网络 图 的基本概念 三 规则图和随机图 规则图的特征如果系统中节点及其与边的关系是固定的 每个节点都有相同的度数 就可以用规则图来表示这个系统 随机图的特征如果系统中节点及其与边的关系不确定 就只能用随机图来表示这个系统 规则图的特征 平均度为3 随机图的特征 节点确定 但边以概率任意连接 节点不确定 点边关系也不确定 随机图 节点19 边43 平均度为2 42 集群系数为0 13 随机图 节点42 边118 平均度为5 62 集群系数为0 133 四 Scale free网络 目录 早期网络模型无标度Scale free网络BA模型 早期网络模型 ER模型小世界模型 ER模型 Erd s和R nyi ER 最早提出随机网络模型并对模型进行了深入研究 他们是用概率统计方法研究随机图统计特性的创始人 在模型开始阶段给定N个节点 没有边 以概率p用边连接任意一对节点 用这样的方法产生一随机网络 ER模型 Erd s和R nyi 1959 首先研究了在随机网络中最大和最小度的分布 Bollob s 1981 随后得到了所有度分布的形式 推导出度数为k的节点数遵从平均值为的泊松分布 即 Poissondistribution 小世界模型 为了描述从一个局部有序系统到一个随机网络的转移过程 Watts和Strogatz WS 提出了一个新模型 通常称为小世界网络模型 WS模型始于一具有N个节点的一维网络 网络的节点与其最近的邻接点和次邻接点相连接 然后每条边以概率p重新连接 约束条件为节点间无重边 无自环 C p clusteringcoeff L p averagepathlength P k 0 1p k 0 3 小世界模型 当p等于0时 对应的网络规则图 两个节点间的平均距离线性地随N增长而增长 集群系数大 当p等于1时 系统变为随机图 对数地随N增长而增长 且集群系数随N减少而减少 在p等于 0 1 区间任意值时 模型显示出小世界特性 约等于随机图的值 网络具有高度集群性 复杂网络都具有分布于平均值两边的度分布曲线吗 无标度 Scale free 网络 Scale free网络的发现Scale free网络的特性 Scale free 网络的发现 信息交换网 万维网 国际互联网 电话网 电力网 社会网络 电影演员合作网 科研合作图 引文网 人类性接触网 语言学网 生物网络 细胞网络 生态网络 蛋白质折叠 Scale free网络的特性 度分布呈幂率分布中枢节点出现稳健性脆弱性 无标度网络与随机图特性比较 无标度 Scale free 网络 无标度模型由Albert L szl Barab si和R kaAlbert在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 Science286 509 1999 BA模型 a Barab si Albert模拟的度分布 b 不同系统规模下的 BA模型 设节点i的度满足动态方程 分母求和是对系统中除新进入系统的节点外的所有节点进行的 则 BA模型 当t足够大时 有解微分方程 有 由初始条件得 解为式中 可给出度小于k的节点的概率 设在相同的时间间隔 添加节点到网络中 值具有常数概率密度 代入前式 t趋于无穷时度分布 式中 模型的度分布是与时间无关的渐进分布且与系统规模无关 幂律度分布的系数与成正比 无标度模型的动态特性可以用各种分析方法给出 连续域理论主方程法变化率方程法 Baral si Albert模型的限制条件 保持了网络的增长特性 不考虑择优连接 网络度分布呈指数衰减 消除了增长过程 只考虑择优连接 络度分布围绕其均值为一高斯分布 Baral si Albert模型扩展研究 初始吸引度非线性择优连接择优连接的更迭机理增长制约条件及增长方式局部相互作用适应度模型 五 常用软件 SasMatlabPajekOriginNetdraw WaxmanGt itmTiersBriteInetPlarg 六 主要参考文献 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 Alber