复杂网络9讲-加权网络.ppt

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