复杂网络分析方法.ppt

第3节复杂网络分析方法 复杂网络理论与方法简介应用实例 区域气候变化的复杂网络分析 1 复杂网络 complexnetwork 是复杂系统研究的拓扑基础 近几年发展起来的复杂网络方法 是现代复杂性科学的一个重要分支 它为人们认识系统复杂性提供了一个新的视角 该分支 以具有自组织 自相似 吸引子 小世界 无标度中部分或全部性质的网络为研究对象 主要研究网络的几何性质 拓扑结构 研究网络的结构稳定性 网络演化的统计规律 以及网络形成与演化的动力学机制等 2 一 复杂网络理论与方法简介 一 复杂网络的概念简而言之 所谓复杂网络即呈现高度复杂性的网络 其复杂性主要表现在以下几个方面 1 结构复杂 表现在节点数目巨大 网络结构呈现多种不同特征 2 网络进化 表现在节点或连接的产生与消失 例如WorldwideNetwork 网页或链接随时可能出现或断开 导致网络结构不断发生变化 3 连接多样性 节点之间的连接权重存在差异 且有可能存在方向性 3 4 动力学复杂性 节点集可能属于非线性动力学系统 节点状态随时间发生复杂变化 5 节点多样性 复杂网络中的节点可以代表任何事物 例如 人际关系构成的复杂网络节点代表单独个体 万维网组成的复杂网络节点代表不同网页 6 多重复杂性融合 多重复杂性相互影响 导致更为难以预料的结果 4 二 复杂网络与传统网络的区别复杂网络与传统的图论网络相比较 具有几个方面的显著不同之处 1 以节点的数量来说 传统的网络皆属于小网络 节点数不过数十个至上百个 特殊情况才会到百个点 但复杂网络的节点数 少则数千个多则达百万个 数量的增加使得网络的复杂度大大的提高 2 复杂网络给人们带来了一种新视野 让人们发掘出在复杂的点边关系中所潜伏的规律或普遍存在的特性 以及其物理学 社会学或生物学意义 这是以往的传统网络所不及的 5 3 从研究方法来说 传统的网络研究 主要依赖数理推导和作图技巧研究小网络 但是面对数量级倍增的复杂网络 必须借助于计算机完成大量的计算和作图任务 4 从研究议题而言 复杂网络所涵盖的议题相当广泛 横跨了自然科学和社会科学等领域 6 三 复杂网络的基本统计指标复杂网络的基本统计指标 包括 度及其分布特征 平均路径长度 群聚系数 介数等 1 度与度分布数学图论中定义 网络中一个节点的度 指该节点拥有的边的个数 度分布 是指不同的度在网络中出现的概率分布 通常我们定义网络的度分布 为网络中度数为k的节点个数占节点总个数的比例 7 也等于在随机一致的原则下挑选出具有节点度为k的概率 对任一给定的网络 可用直方图来表示 而这直方图就是网络的度分布 以下简称度分布 网络的度分布的基础上 可以进一步定义网络的累计度分布 8 图8 3 1给出了泊松度分布和幂律度分布 其中 泊松分布是一个山峰形的分布 其平均度在网络中拥有最大的出现概率 而随着偏离平均度的程度越大 它出现概率越小 幂律度分布 则呈现出胖尾的直线分布 表示随着度数的增加 拥有这样度数的节点数将随之减少 9 图8 3 1两种度分布 泊松分布 a 与幂律分布 b 10 2 距离与平均路径长度在网络研究中 一般定义 两个节点之间的距离 路径长度 为两个节点间最短路径的长度 网络的直径为任意两个节点之间的最大距离 网络的平均路径长度则是所有节点对之间距离的平均值 它描述了网络中节点之间的分离程度 11 网络的平均路径长度的计算公式为式中 表示从节点i到节点j的最短路径长度 N表示节点总数 式中的定义包含了从每个节点到其自身的距离 为0 且排除了网络中存在孤立点的问题 8 3 7 12 3 群聚系数群聚系数 也称集群系数 是用来衡量一个网络中的节点之间结集成团的程度的指标 节点i的群聚系数的定义如下 网络的群聚系数 被定义为各节点群聚系数的平均值 即 13 赋权网络 对边赋权 其节点i的群聚系数被定义为 14 4 介数介数 分为两种 即节点介数和边介数 节点 边 的介数 是指网络中所有的最短路径中经过该节点 边 的数量比例 介数反映了相应的节点或边在整个网络中的作用和影响力 节点k的介数 可以通过下式计算 式中 为连接节点i和j 且通过节点k的最短路径数 为连接节点i和j的最短路径数 15 四 小世界网络与无标度网络复杂网络 一般具有两个共性 即小世界网络与无标度网络 1 小世界网络小世界网络 描述了许多复杂网络的一个共性 即 大多数网络尽管规模很大 但是任意两个节 顶 点间却存在一条相当短的路径 例如 在庞大的人际关系网络中 人与人相互认识的很少 但是任何一个人却可以找到一条相当短的路径 去结识他不认识的距他很远的其他人 这正如麦克卢汉所说 地球变得越来越小 地球村 就是对 小世界 的形象描述 16 小世界网络的判定准则有两个 1 平均路径长度短 2 高集聚系数 许多复杂网络尽管节点数目巨大 但节点之间的特征路径长度则非常小 集聚系数则是用来描述 抱团 现象的 也就是 你朋友之间相互认识的程度 数学上来说 一个节点的集聚系数等于与它相连的节点中相互连接的点对数与总点对数的比值 高集聚系数实际上保证了较小的特征路径长度 17 2 无标度网络无标度网络 是指网络的度分布满足幂律分布 也就是说无标度网络的度分布满足幂律性质 即 式中 表示度的概率 为幂指数 幂律分布这一性质 正说明了无标度网络的度分布与一般随机网络的不同 18 随机网络的度分布属于正态分布 因此有一个特征度数 即大部分节点的度数都接近它 无尺度网络的度分布是呈集散分布 大部分节点之间只有比较少的连接 而少数节点有大量的连接 由于不存在特征度数 因此得名 无尺度 19 二 应用实例 区域气候变化的复杂网络分析总步骤 运用粗粒化方法 将塔里木河流域的气候因子序列转化为由5个特征字符 R r e d D 构成的符号序列 然后以符号序列中的125种3字串组成的气候因子波动模态为网络的节点 并按照时间顺序连边 构建了有向加权的波动网络 进而计算三种网络的度与度分布 聚群系数 最短平均路径长度等动力学统计量 分析网络的复杂性特征 20 一 气候波动网络的构建对塔里木河流域23个气象台站的日平均气温和日降水量 以粗粒化方法把逐日平均气温与日降水量序列转化为由5个特征字符 R r e d D 构成的符号序列 以符号序列中的125种3字串组成的气温和降水量的波动模态为网络的节点 即连续3日的因子波动组合 并按照时间顺序连边 构建一个有向加权的气温波动网络 简记为TFN 和降水波动网络 简记为PFN 进而将气温与降水的波动模态信息蕴含于网络的拓扑结构之中 21 下面以日降水量序列为例 简要地介绍TFN和PFN网络的构建步骤 第一步 资料准备 以塔里木河流域23个气象台站1961 2011年的逐日降水量 构造时间序列 其中 t代表时间 日期 序号 n代表台站编号 即 t 1 2 3 18626 n 1 2 23 计算23个气象台站平均的日降水量序列的值 即 8 3 13 22 第二步 粗粒化 计算因子序列的波动序列 即式中 为序列的时间间隔尺度 在本项研究中 取 2 即任意连续的3天之间的降水量波动情况 8 3 14 23 运用最小二乘法拟合出降水量时间序列P t 中连续3日的变化斜率k 即 8 3 15 24 计算降水量序列可能出现的波动值的概率式中 为对应一种降水量波动模态x发生的次数 为降水量序列可能出现的波动值的概率 8 3 16 25 将降水量波动划分为5个等概率区间 把落在这5个区间的分别用符号表示为R r e d D 即 8 3 17 26 8 3 17 式中 符号R r e d D所代表的含义如图8 3 2所示 图8 3 2符号R r e d D的含义 27 按照上述思想 可把日降水量序列转化为相应的符号序列 对于日平均气温序列 进行类似处理 可以得到其符号序列 28 把气温和降水数值序列转换为符号序列过程中 时间间隔尺度参数的大小代表着时间序列的不同分辨率 对于日平均气温序列和日降水量序列 分别在不同的时间间隔尺度下 对所构件的字符序列中的 进行统计分析 显示它们均与时间间隔尺度满足幂律关系 这反映了气候波动的无标度性 29 第三步 构建网络引入一个加权网络来描述降水量序列中各波动模态之间的关联性和作用 其中网络的节点就是125个3元字符串的波动模态 网络的边为前一个节点指向它的下一个节点 即一种模态向下一个模态转换 表征了一种降雨过程向另一种降雨过程的转变 连接两个节点的边的权重为它们之间多条互不相交的并联连接通路数 30 例如 在所构建的降水量波动网络中 其符号序列为 eRdDeRdrdeDDDreDDDrDedDdDdedrRreeRrreRedrrDdredDrDDedDereDdDeeRdeeRedrdeDdD 以3元字符串的元结构 eRd DeR drd eDD Dre DDD rDe 作为网络的节点 则网络节点的有向连接形式为 Rd DeR drd eDD Dre DDD rDe dDd Dde drR ree Rrr eRe drr Ddr edD rDD edD ere DdD eeR dee Red rde DdD 31 根据上述步骤 可构建体现日平均气温与日降水量序列各波动模态间相互作用的有向含权网络图 图8 3 3给出了TFN和PFN网络中部分节点的关联图像 32 图8 3 3 a TFN和 b PFN网络中部分节点的关联图像 33 图8 3 3 a 刻画了TFN网络中部分节点之间的联系 其中节点之间线连的粗细反映了节点之间关联程度的强弱 例如 节点RRR与dRR之间的连线最粗 表示这两种气温波动模态之间的关联程度最强 图8 3 3 b 刻画了PFN网络中部分节点之间的联系 例如 节点DDD与RDD之间的连线最粗 表示这两种降水波动模态之间的关联程度最强 34 二 气温与降水波动网络的统计特征分析1 度与度分布在构建的TFN和PFN网络中 节点之间的边是按照时间顺序连接的 所以除了首尾两个节点 其它节点的出度和入度必定是相等的 因此只研究择节点的出度 即一种波动模式和向另一种模式间的转换 中间没有其它节点的中转 所以各种波动模态之间具有短程记忆性 记忆性的强弱可以由度值的大小表示 35 表8 3 1和表8 3 2给出了TFN和PFN网络节点的度大小的排序 结果为TFN网络中的节点RRR dRR ReR 及PFN网络中的节点rre rrr eee err 它们的度比较大 这说明在TFN和PFN网络网络中 这些节点所代表的波动模态在气候变化中起到了重要的直接关联作用 各种波动模态向这几个重要模态转换 或被这几个重要模态转换的频率较高 所以 塔里木盆地的容易发生极端高温 异常干旱的气候事件 36 表8 3 1TFN网络中各种节点的度的排序 37 表8 3 2PFN网络中各节点的度的排序 38 对TFN和PFN网络的节点度进行字频统计 结果在度较大的前17个节点中 TFN中代表急剧上升的网络字符R出现的频率非常高 而代表急剧下降的网络字符D非常缺 从这一侧面可以反映出在全球变暖的大背景之下 急剧上升的气温波动在气温变换中出现的次数越来越多 而在PFN中 代表缓慢上升的字符r出现的频率却很高 说明塔里木河流域的降水总体上呈现出一个较弱的上升趋势 39 图8 3 4给出了TFN和PFN网络节点的度分布及累计度分布 可看出气温和降水波动网络中 节点的度分布整体或部分满足幂律分布 且带有重尾巴 这是随机连接造成的 但只要确定性占有一定的比例 所有幂律分布的随机重尾巴就会被抑制 TFN的节点的度近似服从三段幂率分布 图8 3 4a 1 因此TFN具有无标度特性 但其度的分布极不均匀 各气温波动模态间的重要度相差较大 40 a 1 和b 1 分别为TFN和PFN节点的度分布 a 2 和b 2 分别为TFN和PFN节点的累积度分布图8 3 4TFN和PFN网络节点的度分布及累积度分布 41 经过拟合和统计计算 截断点分别为60 100 第一段指数 第二段指数 第三段指数 PFN的节点的度近似服从幂律分布 图8 3 4b 1 近似呈现线性关系 对线性部分进行拟合可得到指数 这些结果表明 气温和降水波动网络 即TFN和PFN具有无标度网络的特性 42 在半对数坐标系下 TFN和PFN网络近似服从衰减的指数分布 见图8 3 4a 2 和图8 3 4b 2 说明气温和降水波动模态的发生带有一定的随机性 进一步表明它们具有混沌特征 然而 虽然TFN和PFN网络都服从衰减的指数分布 但它们的衰减速率明显不同 TFN快 而PFN慢 这说明气温系统的涨落快 而降水系统的涨落慢 43 综上结果 PFN兼有无标度特性和小世界效应 均既是无标度网络由为小世界网络 而TFN具有分层性的无标度特性和小世界效应 二者为具有无标度特性的小世界网络 这些特性说明 气候过程既具有确定性特征 又具有混沌特征 其自然变化过程既具有统一性有具有多样性 44 2 集群系数及平均路径长度TFN和PFN网络的平均路径长度体现了气温和降水波动模态向另一种模态转换经过的节点数 在以时间顺序连边的气温和降水波动网络中 节点代表的波动模态反映了连续3天的气温和降水变化 若两种波动模态之间转换所经过的节点数越多 则这两种模态转换所需要的时间也就越长 因此 网络的平均路径长度体现出了网络中任意两种模态之间的转换所要经过的平均时间 网络的平均路径长度越长 表明任意两个模态之间的转换 经过中间模态的过渡越多 气候变化过程越复杂 45 表8 3 3给出了TFN和PFN网络的群聚系数C 平均路径长度L及平均节点度 TFN和PFN网络的节点平均度分别约为22 6124和85 616 表明它们大约分别平均与23和86个节点有相互关系 TFN和PFN的平均路径长度分别为4 523和2 667 即TFN和PFN网络中的任意1个节点 分别通过4 5和2 3节点就能影响到其它的节点 TFN和PFN均具有较高的群聚系数 较小的平均路径长度 具有良好 小世界 典型特征 这进一步印证了上述的结论 46 表8 3 3TFN和PFN网络的群聚系数 平均路径长度和平均节点度 47 3 节点的介数TFN和PFN网络中各个节点的介数排序结果 分别见表8 3 4表8 3 5 可以看到 TFN和PFN网络中 各节点的介数值之间的存在一定的差异性 在TFN网络中 节点RRR DDD Re