复杂网络9讲-加权网络教程文件.ppt

复杂网络9讲-加权网络8.1 加权网络的统计性质8.2 加权网络的演化模型8.3 权重对网络结构性质的影响主要内容主要内容:2.加权网络上的统计量加权网络上的统计量l权相关性 l最短路径l集聚系数l权相关性1.1.基本概念：基本概念：基本概念：基本概念：点权点权点权点权：无权网中节点度的自然推广 点权 ，即与节点i关联的边权之和。（其中 是节点i 的近邻集合）单位权单位权：,顶点连接的平均权重.权重分布的差异性权重分布的差异性：表示与i相连的边权分布的离散程度。拥有相同点权与单位权的两个节点相比，差异性越大，离散程度越大。点强度分布P（s）与度分布的作用类似，主要是考察节点具有点强度s的概率。边权分布P（w）代表一条边具有权重w的概率。结论2：差异性 与度 k的关系 如果与顶点i关联的边的权重值差别不大，则 与 成正比。如果权值相差较大，那么只有一条边的权重起主要作用，则2.相关性分析相关性分析 加权网络需要进行 度相关性分析度相关性分析 点权相关性分析点权相关性分析 权与度相关性分析权与度相关性分析 度相关性分析：度相关性分析：因为对网络加权不改变节点的度的性质，所以度相关性分析与无权网络中分析相同。在无权网络中：定义节点i的近邻平均度 ，得到度为 的所有节点的近邻平均度 显然 Knn（k）是 k 的函数。那么度相关性可以通过函数 Knn（k）的单调性得到：如果 Knn（k）是无单调性，那么该网络没有度相关性。如果 Knn（k）是增函数，那么该网络是同向匹配网络。（度大的节点倾向于与度大的节点相连）如果 Knn（k）是减函数，那么该网络是负向匹配网络。在加权网络中：定义节点的加权平均近邻度定义节点的加权平均近邻度 考虑权与度的相关性考虑权与度的相关性当 时，具有较大权重的边倾向于连接具有较大度值的点当 时，具有较大权重的边倾向于连接具有较小度值的点所以，对于相互作用强度（权重）给定的边，所以，对于相互作用强度（权重）给定的边，表明它与具有不同度值的顶表明它与具有不同度值的顶点之间的亲和力。点之间的亲和力。最短路径1.加权网络中两点之间的距离与权重的关系加权网络中两点之间的距离与权重的关系：距离是权重的某种函数，这时需要看权重是相似权还是相异权。相异权相异权：定义两点之间的距离相似权相似权：令假设顶点i和k分别通过两条权重分别为 和 的边相连，现求i与k之间的距离。对于相异权：对于相似权：2.最短路径最短路径：两点之间所有连通的路径中距离之和最小的一条或几条路径。无权网无权网：边数最少的路径 最短路径加权网加权网：因为距离不满足三角不等式，所以两边距离之和不一定大于第三边.边数最少的路径 最短路径网络的其他全局统计量，如介数，可以在加权最短路径的基础上进行计算网络的其他全局统计量，如介数，可以在加权最短路径的基础上进行计算集聚系数节点i的聚类系数 反映了该节点邻点的联系的程度。越大，说明该点的邻接点之间的联系越紧密。加权网络中的聚类系数有多种定义方式;Barat 定义：分母上为单位权乘以最大可能的三角形的数目，分子上是实际三角形数目乘以与i相连的边的权重的平均值Onnela 定义：其中 wij 为网络中经最大权重标准化后的数值Petter Holme 分析加权网络的聚类系数，指出它应该满足以下几条要求：1.2.加权网退化为无权网时，聚类系数应与Watts-Strogatz定义的聚类系数的计算结果一致。3.权值为0表示该边不存在。4.包含节点i的三角形中三条边对 的贡献应与边的权重成正比。Watts-Strogatz 定义的聚类系数:加权网的聚类系数加权网的聚类系数：一些加权网络的实证结果1.生物网络 Almaas等人将酵母中的新陈代谢反应看作加权网络进行研究，把从代谢物i到j的流量看作边权 ，观察到流量具有高度非均匀性，在理想的培养下条件下，边权的分布符合幂律分布 其中 ，此外还发现给定两端度值的边的权重平均值和两个端点的度值的关系为 ，其中 。除了全局流量分布的非均匀性外，计算边权差异性 还可以观察到在单个代谢物的层面上边权分布的非均匀性。在此网络上对出度和入度相同的顶点计算边权差异性，发现它们都服从 这是一种介于 和 之间的中间状态，说明一个代谢物参与的化学反应越多，其中的某一个化学反应携带主要流量的可能性就越高。?2.社会网络 以科学家合作网为例，Newman定义了科学家合作网的权重 ，其中p包括数据库中的所有文章，如果i是文章p的作者之一，则 ，否则 ，表示文章p中作者的数目。从平均效果来看，合作者较少时作者之间的相互关系更加紧密。3.技术网络 在一些基础设施网络中，例如Internet,铁路网和航空网中，运输过程中的流量可以转化为权重，Barrat等人分析了全球航空网络，把两机场i和j之间的航班的有效座位数作为机场间的权重 ，而李炜等人在研究中国航空网时，把两机场间的航班数作为机场间的权重。在对不同数据进行研究时，发现这些网络具有小世界网络和无标度网络的特征。特别是度分布表现为如下形式：，其中 ，且 是指数截断函数。与一个机场能够运作的最大航线数有关。点强度分布呈现出幂律尾，并且边权和度具有一定的相关性：平均来讲，边权与边的两端顶点的度值的函数关系为 其中 。点强度和度之间的关系服从幂律函数关系 ，其中 ，这说明机场越大，处理交通流量的能力就越强。经济物理学科学家合作网络的建立和统计分析 科学家之间的合作有多个层次，若希望通过网络分析挖掘科学家在科学研究上的内在关联就必须考虑不同层次的相互作用的贡献，而网络连接权重就就需要综合考虑层次和强度两个方面。考虑科学家交流的三个层次：合著，引用和致谢，记录为 ，作者 与 合作x次，引用作者 的文章y次，并且在 的文章致谢里感谢 z次。事实上，可以把整个数据看做三个不同的网络，合著网络，引用网络和致谢网络，把这三种关系综合在一起考虑，看做一个网络，采用以下赋权方式：，其中 可以取1，2，3 分别对应合著，引用和致谢关系，是三种关系所对应的权重，定义为：直观上说，次数越多关系越亲密，但是随着次数的增加，新事件对亲密程度的贡献越来越小，即新事件对亲密程度的贡献具有边际递减效应。因此采用具有饱和效应的tanh函数将次数转化为权重，来刻画次数和亲密程度的非线性效应。假定三种相互作用对权重的贡献也是不同的，用参数 表示。在研究经济物理学科学家合作网时，分别取值为0.7，0.2，0.1。8.2 加权网络的演化模型边权固定模型边权演化模型应用研究的意义是什么?例:某一新思想的在一个学术领域的产生传播过程中，随着时间的推移,可能会有更多的科学家介入(增长)，同时随着新思想影响程度的加深，已有交流的科学家之间的相互作用强度也会发生变化(权值改变)。静态网络显然已经不能揭示加权网络的演化行为，因此在这里研究网络拓扑结构和权重分布的耦合演化机制，来描述新思想传播过程。边权固定模型1.无标度加权网络模型（无标度加权网络模型（WSF）2001年，Yook和Barabasi提出了类似于BA模型的加权网络生成模型。其定义如下：（1）网络拓扑结构的演化（同BA模型）增长增长：初始时有n0个节点，每个时间间隔加入一个新节点j，并使新节点j与m个已经存在的点连接（m n0）择优连接择优连接：新加入的点与网络中已经存在的点的连接不是等概率的，而是以一种择优的方式选择与自己连接的点。新节点j与节点i连接的概率:（2）赋边权赋边权(基于两个假设:权重Wij正比于节点i的度;所有新节点新节点有相同的点权)新节点与已存在节点之间的每一条连接j i,被赋予一定的权重 ，权重的多少取决于被连接节点i的度i代表新节点j所要连接的点的集合。这时新节点j的点权为1无标度加权网络模型特点无标度加权网络模型特点：拓扑结构与BA模型相同，故度分布点权分布符合幂律分布：其中指数与参数m有关。边权分布ZTZH模型在WSF模型的基础上进行推广，赋边权时综合考虑节点的度和适应度。适应度 ：反应节点i本身的性质，假设其服从0,1上的均匀分布.(当不知道随机变量取值的特点时,假设其服从某一区间上的均匀分布)(1)网络结构拓扑演化同网络结构拓扑演化同WSF网络网络(2)赋边权赋边权:设定一参数p 以概率p按公式 赋边权 以概率1-p按公式 赋边权当p=1时,ZTZH模型=WSF模型当p=1时,边权的赋予完全由节点的适应度决定.ZTZH模型的点强度分布也符合幂律分布 ，但是指数 敏感地依赖于参数p，随着p的增加，从3连续下降。Antal-Krapivsky提出了一个加权网络的演化模型，改进之处是在演化过程中考虑了边权对网络结构演化的影响。规则如下，每个时间间隔有一个节点j加入到网络中，并选择一个老节点建立连接，其连接概率正比于节点的强度：此规则关注点强度对连接的驱动作用，点强度越大的节点被连接到的概率越大。实际网络中，例Internet网络中，新的路由器会根据带宽或流量的处理能力连接到中枢路由器上。由于每个新顶点只有一条边，所以该模型生成的网络是树形结构的。边权演化模型边权固定模型的共同的特点:边权一旦设定不再改变,也就是说网络中边的权重在初始时刻己经给定,而且随着网络规模的增大,边权没有任何变化。这与实际系统中的情况有很大的差异，比如在航空网络中随着航空网络的增大，与新加机场有连接关系的机场的各条航线上的客流量也会有相应的增加，在加权网络中就表现为边权的增加.这时在加权网络的演化模型中需要考虑边权的演化.下面建立基于点权的边权演化模型1.BBV模型模型(1)网络结构拓扑演化网络结构拓扑演化增长：增长：初始时有n0个节点，每边赋权值为w0 每个时间间隔加入一个带有m条边的新节点j，边权也为w0优先连接：优先连接：根据 选择老节点i与新节点j相连（2）边权演化）边权演化 新边 的加入会导致节点i与其邻居节点之间的边权重重新分配。权重为 的新边得加入会给节点i带来一个小的流量增加 ，然后在所有与i相连的边中按权重所占比例分配增量 ，分配情况如图所示。BBV模型的特点分析模型的特点分析：(1).度分布，边权分布，点权分布均服从幂律分布度分布，边权分布，点权分布均服从幂律分布，具体地：度分布：说明BBV模型可以生成幂指数介于2,3之间的无标度网络.边权分布：点权分布：(2).权与度的相关性权与度的相关性点权与网络的拓扑结构有关,其中可以看到:这里2.DM模型模型新加入的点和哪一节点相连？择优的过程。基于度择优，点权择优，其他方式？实例:科学家合作网络,边权设定为能反应合作著作的重要性的数值(它是综合著作的出版时间,著作的影响力等得到的).比如两个科学家在20年前之合作出版了一部著作,那么另外一个科学家与他们合作的几率就会很小.这时网络拓扑演化过程就应该首先考虑到边权大小.DM模型演化规则:网络开始于任意的一组节点和边.(1)择优:在已有的节点中,按照与边权成正比的概率选择一条边 加权:令该边的权值有一个小的增量(2)增长:加入一个新节点,且该节点与所选边的两端连接,并设新边的权重为1DM模型的特点:度分布,边权分布,点权分布均为幂律分布度分布:边权分布:点权分布:总结:BBV模型与模型与DM模型的不同点模型的不同点:择优机制：点权与边权同时考虑？例如：基因网络中，存在某基因活性很高，同时存在一条细胞路径（一条边）非常重要，要加入的新基因既可以和活性高的基因完成一些活动，又可与该边结合进行其他细胞过程的完成，问题是：如何决定新基因的连接？BBV模型和模型和DM模型的共同特点模型的共同特点:拓扑结构上:只考虑新节点与老节点相连 边权是独立于连接之外的一个基本量.也就是说不管连接的具体程度如何,只要有连接,就按照相同的规则来赋边权.但在实际中,所赋边权的大小往往与连接的程度有关,这时应该做相关方面的假设.（即没有考虑边权与度的相关性）BBV模型是以点权为驱动机制,而DM模型是以边权为驱动机制.基于科学家合作机制的加权网络演化模型在科学家合作网络构造过程中作如下的规定:1.每一时刻:新加一个节点 连接既可建立于新节点与老节点之间,还可建立于老节点与老节点之间.2.允许顶点之间重复相连,权重看做是连接次数的一个函数.模型的基本演化规则:具有N个节点的加权网络可以定义为一个N*N的矩阵WN*N,其中的每个元素代表相应节点之间的边权.设边权与连接次数Tij之间存在一个函数关系f,即wij=f(Tij).其中f可取tanh(双曲正切函数),或是线性函数.初始于 n0个节点的完全网,每条边的连接次数初始化为Tij=1,并且把权初始化为wij=f(1),在每一个时间间隔:1.添加一个新节点,同时从网络中随机选取l个不同的老节点.2.l+1个节点中的每一个节点(用n表示)都可以与其他节点建立m个联系.综合考虑节点的度,节点的强度,边权三方面因素得到节点n连接到节点i的概率。表示与节点n的距离（级数）小于等于d的所有近邻集合 3.找到节点i后,节点n和i之间的连接次数按下式进行演化4.边权的演化如下:虽然本模型可以应用于有向网络,但假设模型为无向网络,并且边权与连接次数之间的关系为Wij=Tij8.3 权重对网络结构性质的影响无权网络结构性质的改变：通过改变网络的拓扑结构来实现加权网络结构性质的改变:通过改变网络的拓扑结构和调整权重两种途径来实现网络中有多种统计量来反应网络结构的性质：基本结构：点权，最短路径，聚类系数社团结构调整权重的途径：第一种：权重集合不变，改变权与边的对应关系第二种：权重的总量或是均值不变，改变权重的分布形式权重调整对基本结构性质的影响 1.通过改变权与边的对应关系，研究对基本结构的影响（边权分布不变）2.通过改变权重的分布形式，研究对基本结构的影响权重调整对社团结构性质的影响权重调整对基本结构性质的影响1.通过改变权与边的对应关系，研究对基本结构性质的影响如何表示权与边的对应关系？如何表示权与边的对应关系？给定一个加权网络，引入一个参数p,描述权重和边的匹配关系。将原始网络中权与边的关系降序排列，令p=1表示该原始序列：P=-1表示权与边的关系进行反序排列，称之为反权网络：P=0表示保持边的顺序不变，然后从权重集合中随机抽取一个权重分给该边，称之为随机赋权网络。P可以看作新序列与原来序列的相关系数。该变p值就改变了边与权的对应关系，下面考虑p由1变为0和-1时，基本结构性质有何变化。研究结果：1.通过无权网络和加权网络的点介数和边介数的对比发现：两者在统计分布上定性一致，但在微观上节点或边的位置或数值发生了变化。2.对p=1原始网,p=0随机加权网,p=-1反权网的点权分布，聚类系数分布，边介数，点介数的比较发现：点权分布基本一致，聚类系数分布差别相对明显，边介数分布基本一致，但某一条边的位置在不同网络中差别很大。点介数分布基本一致，高端处变化相对较大，某一点的位置在不同网络中略有改变。结论：原始网络，反权网络，随机权网络以及他们对应的无权网络，各静态统计量的全局分布大致相同，但是细致结构受到了权重的影响。权重和实际网络中的边有特定的匹配关系，不能随便赋权。边的序1101001k1101001k边介数分布，在加权网与无权网中边介数分布差别相对较大，同一条边的介数值相差相对较大。边介数实例：边介数反映了这两个科学家交流对整个新思想的传播的影响。加权网中的边介数更能说明这两个人的交流重要的重要性。1101001k1101001k点的序点介数粗线代表加权网细线代表无权网点介数分布，在加权网和无权网中分布基本一致，只有在高端略有差别，同一个科学家的位置没有变化，但在数值上有明显差别。经济物理学家合作网1101001k1101001k原始网随机赋权网反权网点权分布，三种情况基本一致点的序权重1101001k1101001k点的序聚类系数原始网随机赋权网反权网聚类系数：反权网和随即赋权网的聚类系数都比原始网的聚类系数低1101001k1101001k边的序边介数原始网随机赋权网反权网边介数分布基本相同但同一条边的位置差别较大1101001k1101001k点的序点介数原始网随机赋权网反权网点介数分布：除了高端处略有差别外，分布大致相同，相同顶点的位置略有改变。2.通过改变权重的分布形式，研究对基本结构的影响调整权与边的对应关系没有改变边权的分布，下面介绍如何改变权重分布的方法。构造网络（与构造小世界网络方法类似），再通过对平均路径和平均聚类系数的分析研究网络基本结构性质的变化情况。构造网络：（1）起始于最近邻耦合网络 构造一个包含N个节点的环状规则网络，每个节点与k(k=2m)个邻居相连，每条边赋予相同的相异权重w，例如w=5；其次再把每条边的权重n等分，每份为 (=w/n),例如n=5，则每份权重为1 (2)重分概率p 把每条边上的每份权重 按p的概率抽出，再把抽出的权重放回到从网络中等概率地随机选择的一条边上。要求每条边上都至少有一个单位权重。这样构造的网络不会改变网络连接，但可以把权重为 分布的规则网络转化为权重为泊松分布的网络。结论:通过对比多个p(0P1)对应的多个网络之间的平均路径和平均聚类系数,可以看出网络结构性质的变化.边权的重新分布过程中，随着重分概率的增加,网络的平均最短距离明显减小,而聚类系数略有增加.显然通过对原始权重的重新分布,也可以获得小世界效应.网络密度用 来表示,网络密度不同对应的曲线不同,有何关系?在同一重分概率p下,同一规模下N，随着网络密度的增加,平均最短路径可以达到一个极小值,说明要想得到较短的平均最短距离，应考虑构造稠密网络。间接说明在稠密网络中,权重的作用更加重要。平均最短路径在p一定下随网络密度变化的现象与网络的规模N无关,不同规模下所得的结果定性一致.P=1时,不同网络规模下平均最短路径的变化曲线给定p后,平均最短路径的变化与网络密度的关系