8.3--复杂网络分析方法.ppt

第3节复杂网络分析方法复杂网络理论与方法简介应用实例：区域气候变化的复杂网络分析复杂网络（complexnetwork），是复杂系统研究的拓扑基础。近几年发展起来的复杂网络方法，是现代复杂性科学的一个重要分支，它为人们认识系统复杂性提供了一个新的视角。该分支，以具有自组织、自相似、吸引子、小世界、无标度中部分或全部性质的网络为研究对象，主要研究网络的几何性质、拓扑结构，研究网络的结构稳定性、网络演化的统计规律，以及网络形成与演化的动力学机制等。一、复杂网络理论与方法简介（一）复杂网络的概念简而言之，所谓复杂网络即呈现高度复杂性的网络。其复杂性主要表现在以下几个方面：（1）结构复杂，表现在节点数目巨大，网络结构呈现多种不同特征。（2）网络进化，表现在节点或连接的产生与消失。例如WorldwideNetwork，网页或链接随时可能出现或断开，导致网络结构不断发生变化。（3）连接多样性，节点之间的连接权重存在差异，且有可能存在方向性。（4）动力学复杂性，节点集可能属于非线性动力学系统，节点状态随时间发生复杂变化。（5）节点多样性，复杂网络中的节点可以代表任何事物，例如，人际关系构成的复杂网络节点代表单独个体，万维网组成的复杂网络节点代表不同网页。（6）多重复杂性融合，多重复杂性相互影响，导致更为难以预料的结果。（二）复杂网络与传统网络的区别复杂网络与传统的图论网络相比较，具有几个方面的显著不同之处：（1）以节点的数量来说，传统的网络皆属于小网络，节点数不过数十个至上百个（特殊情况才会到百个点），但复杂网络的节点数，少则数千个多则达百万个，数量的增加使得网络的复杂度大大的提高。（2）复杂网络给人们带来了一种新视野，让人们发掘出在复杂的点边关系中所潜伏的规律或普遍存在的特性，以及其物理学、社会学或生物学意义，这是以往的传统网络所不及的。（3）从研究方法来说，传统的网络研究，主要依赖数理推导和作图技巧研究小网络，但是面对数量级倍增的复杂网络，必须借助于计算机完成大量的计算和作图任务。（4）从研究议题而言，复杂网络所涵盖的议题相当广泛，横跨了自然科学和社会科学等领域。（三）复杂网络的基本统计指标复杂网络的基本统计指标，包括：度及其分布特征、平均路径长度、群聚系数、介数等。（1）度与度分布数学图论中定义，网络中一个节点的度，指该节点拥有的边的个数。度分布，是指不同的度在网络中出现的概率分布。通常我们定义网络的度分布，为网络中度数为k的节点个数占节点总个数的比例。)(kP也等于在随机一致的原则下挑选出具有节点度为k的概率。对任一给定的网络，可用直方图来表示，而这直方图就是网络的度分布（以下简称度分布）。网络的度分布的基础上，可以进一步定义网络的累计度分布：)(kPksksPkdP)()(图8.3.1给出了泊松度分布和幂律度分布。其中，泊松分布是一个山峰形的分布，其平均度在网络中拥有最大的出现概率，而随着偏离平均度的程度越大，它出现概率越小。幂律度分布，则呈现出胖尾的直线分布，表示随着度数的增加，拥有这样度数的节点数将随之减少。图8.3.1两种度分布：泊松分布(a)与幂律分布(b)（2）距离与平均路径长度在网络研究中，一般定义：两个节点之间的距离（路径长度）为两个节点间最短路径的长度；网络的直径为任意两个节点之间的最大距离；网络的平均路径长度则是所有节点对之间距离的平均值，它描述了网络中节点之间的分离程度。网络的平均路径长度的计算公式为式中：表示从节点i到节点j的最短路径长度，N表示节点总数。式中的定义包含了从每个节点到其自身的距离（为0），且排除了网络中存在孤立点的问题。jiijdNNL)1(211（8.3.7）ijd（3）群聚系数群聚系数，也称集群系数，是用来衡量一个网络中的节点之间结集成团的程度的指标。节点i的群聚系数的定义如下：网络的群聚系数，被定义为各节点群聚系数的平均值，即：为中心的三点组的个数以节点的三角形个数包含节点iiCiiiCNC1赋权网络（对边赋权），其节点i的群聚系数被定义为:ikjkijkjikijjijiwiaaa),(2)1(1（4）介数介数，分为两种，即节点介数和边介数。节点（边）的介数，是指网络中所有的最短路径中经过该节点（边）的数量比例。介数反映了相应的节点或边在整个网络中的作用和影响力。节点k的介数，可以通过下式计算：式中：为连接节点i和j，且通过节点k的最短路径数；为连接节点i和j的最短路径数。),(),(),(jikkjigjigB),(jigk),(jig（四）小世界网络与无标度网络复杂网络，一般具有两个共性，即小世界网络与无标度网络。1.小世界网络小世界网络，描述了许多复杂网络的一个共性，即：大多数网络尽管规模很大，但是任意两个节（顶）点间却存在一条相当短的路径。例如，在庞大的人际关系网络中，人与人相互认识的很少，但是任何一个人却可以找到一条相当短的路径，去结识他不认识的距他很远的其他人。这正如麦克卢汉所说，地球变得越来越小，“地球村”就是对“小世界”的形象描述。小世界网络的判定准则有两个：（1）平均路径长度短；（2）高集聚系数。许多复杂网络尽管节点数目巨大，但节点之间的特征路径长度则非常小。集聚系数则是用来描述“抱团”现象的，也就是“你朋友之间相互认识的程度”。数学上来说，一个节点的集聚系数等于与它相连的节点中相互连接的点对数与总点对数的比值。高集聚系数实际上保证了较小的特征路径长度。2.无标度网络无标度网络，是指网络的度分布满足幂律分布。也就是说无标度网络的度分布满足幂律性质，即：式中：表示度的概率，为幂指数。幂律分布这一性质，正说明了无标度网络的度分布与一般随机网络的不同。kkdP)()(kdPkd随机网络的度分布属于正态分布，因此有一个特征度数，即大部分节点的度数都接近它。无尺度网络的度分布是呈集散分布，大部分节点之间只有比较少的连接，而少数节点有大量的连接。由于不存在特征度数，因此得名“无尺度”。二、应用实例：区域气候变化的复杂网络分析总步骤：运用粗粒化方法，将塔里木河流域的气候因子序列转化为由5个特征字符{R,r,e,d,D}构成的符号序列。然后以符号序列中的125种3字串组成的气候因子波动模态为网络的节点，并按照时间顺序连边，构建了有向加权的波动网络，进而计算三种网络的度与度分布、聚群系数、最短平均路径长度等动力学统计量，分析网络的复杂性特征。（一）气候波动网络的构建对塔里木河流域23个气象台站的日平均气温和日降水量，以粗粒化方法把逐日平均气温与日降水量序列转化为由5个特征字符{R,r,e,d,D}构成的符号序列。以符号序列中的125种3字串组成的气温和降水量的波动模态为网络的节点（即连续3日的因子波动组合），并按照时间顺序连边，构建一个有向加权的气温波动网络（简记为TFN）和降水波动网络（简记为PFN），进而将气温与降水的波动模态信息蕴含于网络的拓扑结构之中。下面以日降水量序列为例，简要地介绍TFN和PFN网络的构建步骤：第一步：资料准备。以塔里木河流域23个气象台站1961—2011年的逐日降水量，构造时间序列，其中，t代表时间（日期）序号，n代表台站编号，即：t=1,2,3,…,18626，n=1,2,…,23。计算23个气象台站平均的日降水量序列的值，即)(tPn)(tP231)(231)(iitPtP(8.3.13)第二步：粗粒化。计算因子序列的波动序列，即式中：为序列的时间间隔尺度。在本项研究中，取=2，即任意连续的3天之间的降水量波动情况。)(tkttPttPtk)()()((8.3.14)tt运用最小二乘法拟合出降水量时间序列P(t)中连续3日的变化斜率k，即18626,...,4,3)(1))()((1)()3/(1212111ititttPitPtikititititit(8.3.15)计算降水量序列可能出现的波动值的概率式中：为对应一种降水量波动模态x发生的次数，为降水量序列可能出现的波动值的概率。kkNxNumP)((8.3.16))(xNumkP将降水量波动划分为5个等概率区间，把落在这5个区间的分别用符号表示为R，r，e，d，D，即kP)(tk0.18.0,8.06.0,6.04.0,4.02.0,2.00,kkkkkiPDPdPePrPRS(8.3.17)（8.3.17）式中，符号R，r，e，d，D所代表的含义如图8.3.2所示：图8.3.2符号R，r，e，d，D的含义按照上述思想，可把日降水量序列转化为相应的符号序列：对于日平均气温序列，进行类似处理，可以得到其符号序列：)(tP},,,{321SSSSP},,,,{DderRSi)(tT},,,{321SSSST},,,,{DderRSi把气温和降水数值序列转换为符号序列过程中，时间间隔尺度参数的大小代表着时间序列的不同分辨率。对于日平均气温序列和日降水量序列，分别在不同的时间间隔尺度下，对所构件的字符序列中的，，，，进行统计分析，显示它们均与时间间隔尺度满足幂律关系：这反映了气候波动的无标度性。t)(tT)(tPt)(RN)(rN)(eN)(dN)(DN)(tNt第三步：构建网络引入一个加权网络来描述降水量序列中各波动模态之间的关联性和作用，其中网络的节点就是125个3元字符串的波动模态；网络的边为前一个节点指向它的下一个节点，即一种模态向下一个模态转换，表征了一种降雨过程向另一种降雨过程的转变；连接两个节点的边的权重为它们之间多条互不相交的并联连接通路数。例如，在所构建的降水量波动网络中，其符号序列为：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根据上述步骤，可构建体现日平均气温与日降水量序列各波动模态间相互作用的有向含权网络图。图8.3.3给出了TFN和PFN网络中部分节点的关联图像。图8.3.3(a)TFN和(b)PFN网络中部分节点的关联图像图8.3.3(a)刻画了TFN网络中部分节点之间的联系，其中节点之间线连的粗细反映了节点之间关联程度的强弱。例如，节点RRR与dRR之间的连线最粗，表示这两种气温波动模态之间的关联程度最强；图8.3.3(b)刻画了PFN网络中部分节点之间的联系。例如，节点DDD与RDD之间的连线最粗，表示这两种降水波动模态之间的关联程度最强。（二）气温与降水波动网络的统计特征分析1.度与度分布在构建的TFN和PFN网络中，节点之间的边是按照时间顺序连接的，所以除了首尾两个节点，其它节点的出度和入度必定是相等的.因此只研究择节点的出度，即一种波动模式和向另一种模式间的转换，中间没有其它节点的中转，所以各种波动模态之间具有短程记忆性，记忆性的强弱可以由度值的大小表示。表8.3.1和表8.3.2给出了TFN和PFN网络节点的度大小的排序。结果为TFN网络中的节点RRR、dRR、ReR，及PFN网络中的节点rre、rrr、eee、err，它们的度比较大。这说明在TFN和PFN网络网络中，这些节点所代表的波动模态在气候变化中起到了重要的直接关联作用，各种波动模态向这几个重要模态转换，或被这几个重要模态转换的频率较高。所以，塔里木盆地的容易发生极端高温、异常干旱的气候事件。节点RRRdRRReRRRdRDRDRRDDDrRreReRRe度254220218206202192182174172170等级12345678910节点eeRdddr