复杂网络9讲-加权网络

第八讲加权网络2010.11.13李凯凯•8.1加权网络的统计性质•8.2加权网络的演化模型•8.3权重对网络结构性质的影响主要内容:8.1加权网络的统计性质1.加权网络的加权的必要性与方式2.加权网络上的统计量1.网络加权的必要性与赋权方式网络加权的必要性:例:为研究某一新思想的在一个学术领域的产生传播,研究科学家之间通过文献相互作用的网络。相互作用分为三个层次:合作,引文,致谢(无权网中能体现相互作用的三个层次吗?)。我们可以根据不同的作用关系做三个网络:合作网络,引文网络,致谢网络.但即便对于同一个网络比如引文网络,引文次数不同所代表的相互作用关系不同。(无权网中能表现相互作用的强度吗?)这时必须考虑赋边权,表示相联系的强度.另外,我们希望在同一个网络中研究这三个层次的相互作用,还应该考虑加权的方式.当系统中包含同一属性的不同层次的关系的时候,必须仔细研究加权方式.加权的方式:根据相关的物理量(例如:电阻网络边上的权值代表电阻值,邮递员问题中的距离)根据相互作用的某种属性(例如:科学家通过文献相互作用,把引文的次数作为权重)边权按照意义划分:相异权:权值越大,两点之间的距离越大,关系越疏远.(例:邮递员问题中的距离)相似权:权值越大,两点之间的距离越小,关系越亲密.(例:科学家合作网中,把次数作为权重,得到相似权)注意:在计算两点间的距离和聚类系数时,边权的意义不同,计算方式也不同.2.加权网络上的统计量权相关性最短路径集聚系数权相关性i1.基本概念：点权：无权网中节点度的自然推广点权，即与节点i关联的边权之和。（其中是节点i的近邻集合）单位权：,顶点连接的平均权重.权重分布的差异性：表示与i相连的边权分布的离散程度。拥有相同点权与单位权的两个节点相比，差异性越大，离散程度越大。点强度分布P（s）与度分布的作用类似，主要是考察节点具有点强度s的概率。边权分布P（w）代表一条边具有权重w的概率。iNjijiwSiNiiikSUiNjiijiSwY2][结论2：差异性与度k的关系如果与顶点i关联的边的权重值差别不大，则与成正比。如果权值相差较大，那么只有一条边的权重起主要作用，则iYik1iiijiNjiijiijikkwwkkwwSwYi1][][222221iYiY2.相关性分析加权网络需要进行度相关性分析点权相关性分析权与度相关性分析度相关性分析：因为对网络加权不改变节点的度的性质，所以度相关性分析与无权网络中分析相同。在无权网络中：定义节点i的近邻平均度，得到度为的所有节点的近邻平均度显然Knn（k）是k的函数。那么度相关性可以通过函数Knn（k）的单调性得到：如果Knn（k）是无单调性，那么该网络没有度相关性。如果Knn（k）是增函数，那么该网络是同向匹配网络。（度大的节点倾向于与度大的节点相连）如果Knn（k）是减函数，那么该网络是负向匹配网络。innk,k)(kknninnk,VjjijiNjjiinnkakkkki11,在加权网络中：定义节点的加权平均近邻度考虑权与度的相关性当时，具有较大权重的边倾向于连接具有较大度值的点当时，具有较大权重的边倾向于连接具有较小度值的点所以，对于相互作用强度（权重）给定的边，表明它与具有不同度值的顶点之间的亲和力。jNjjijijiwinnkwaSk1,innwinnkk,,innwinnkk,,winnk,•最短路径1.加权网络中两点之间的距离与权重的关系：距离是权重的某种函数，这时需要看权重是相似权还是相异权。相异权：定义两点之间的距离相似权：令假设顶点i和k分别通过两条权重分别为和的边相连，现求i与k之间的距离。对于相异权：对于相似权：2.最短路径：两点之间所有连通的路径中距离之和最小的一条或几条路径。无权网：边数最少的路径最短路径加权网：因为距离不满足三角不等式，所以两边距离之和不一定大于第三边.边数最少的路径最短路径网络的其他全局统计量，如介数，可以在加权最短路径的基础上进行计算ijijwlijijwl1ijwjkwjkijikwwljkijikwwl111集聚系数节点i的聚类系数反映了该节点邻点的联系的程度。越大，说明该点的邻接点之间的联系越紧密。加权网络中的聚类系数有多种定义方式;Barat定义：分母上为单位权乘以最大可能的三角形的数目，分子上是实际三角形数目乘以与i相连的边的权重的平均值Onnela定义：其中wij为网络中经最大权重标准化后的数值kjkijkijiiwo)()1(1)(iCiCkijkijkjjkijiiwBaaawwksC,2)1(1ijwPetterHolme分析加权网络的聚类系数，指出它应该满足以下几条要求：1.2.加权网退化为无权网时，聚类系数应与Watts-Strogatz定义的聚类系数的计算结果一致。3.权值为0表示该边不存在。4.包含节点i的三角形中三条边对的贡献应与边的权重成正比。Watts-Strogatz定义的聚类系数:加权网的聚类系数：]1,0[wC)(iCwkjkiijkjkijkijaaaaaiC,,)(kjikijijijkjkijkijwH一些加权网络的实证结果•1.生物网络Almaas等人将酵母中的新陈代谢反应看作加权网络进行研究，把从代谢物i到j的流量看作边权，观察到流量具有高度非均匀性，在理想的培养下条件下，边权的分布符合幂律分布其中，此外还发现给定两端度值的边的权重平均值和两个端点的度值的关系为，其中。除了全局流量分布的非均匀性外，计算边权差异性还可以观察到在单个代谢物的层面上边权分布的非均匀性。在此网络上对出度和入度相同的顶点计算边权差异性，发现它们都服从这是一种介于和之间的中间状态，说明一个代谢物参与的化学反应越多，其中的某一个化学反应携带主要流量的可能性就越高。??)()(0p0003.005.1)(~jiijkk5.0iY27.0~kYiconstkY)(1~)(kkY•2.社会网络以科学家合作网为例，Newman定义了科学家合作网的权重，其中p包括数据库中的所有文章，如果i是文章p的作者之一，则，否则，表示文章p中作者的数目。从平均效果来看，合作者较少时作者之间的相互关系更加紧密。)1/(ppjppiijn0pi1pipn•3.技术网络在一些基础设施网络中，例如Internet,铁路网和航空网中，运输过程中的流量可以转化为权重，Barrat等人分析了全球航空网络，把两机场i和j之间的航班的有效座位数作为机场间的权重，而李炜等人在研究中国航空网时，把两机场间的航班数作为机场间的权重。在对不同数据进行研究时，发现这些网络具有小世界网络和无标度网络的特征。特别是度分布表现为如下形式：，其中，且是指数截断函数。与一个机场能够运作的最大航线数有关。点强度分布呈现出幂律尾，并且边权和度具有一定的相关性：平均来讲，边权与边的两端顶点的度值的函数关系为其中。点强度和度之间的关系服从幂律函数关系，其中，这说明机场越大，处理交通流量的能力就越强。ij)/()(xkkfkkp0.2)/(xkkf)(~jiijkk5.0Akks)(5.1•经济物理学科学家合作网络的建立和统计分析科学家之间的合作有多个层次，若希望通过网络分析挖掘科学家在科学研究上的内在关联就必须考虑不同层次的相互作用的贡献，而网络连接权重就就需要综合考虑层次和强度两个方面。考虑科学家交流的三个层次：合著，引用和致谢，记录为，作者与合作x次，引用作者的文章y次，并且在的文章致谢里感谢z次。事实上，可以把整个数据看做三个不同的网络，合著网络，引用网络和致谢网络，把这三种关系综合在一起考虑，看做一个网络，采用以下赋权方式：，其中可以取{1，2，3}分别对应合著，引用和致谢关系，是三种关系所对应的权重，定义为：),,,,(21zyxSS1S2S2S1S2Sijijww)tanh(ijijTwijw•直观上说，次数越多关系越亲密，但是随着次数的增加，，新事件对亲密程度的贡献越来越小，即新事件对亲密程度的贡献具有边际递减效应。因此采用具有饱和效应的tanh函数将次数转化为权重，来刻画次数和亲密程度的非线性效应。假定三种相互作用对权重的贡献也是不同的，用参数表示。在研究经济物理学科学家合作网时，分别取值为0.7，0.2，0.1。321,,8.2加权网络的演化模型•边权固定模型•边权演化模型•应用研究的意义是什么?例:某一新思想的在一个学术领域的产生传播过程中，随着时间的推移,可能会有更多的科学家介入(增长)，同时随着新思想影响程度的加深，已有交流的科学家之间的相互作用强度也会发生变化(权值改变)。静态网络显然已经不能揭示加权网络的演化行为，因此在这里研究网络拓扑结构和权重分布的耦合演化机制，来描述新思想传播过程。•边权固定模型1.无标度加权网络模型（WSF）2001年，Yook和Barabasi提出了类似于BA模型的加权网络生成模型。其定义如下：（1）网络拓扑结构的演化（同BA模型）增长：初始时有n0个节点，每个时间间隔加入一个新节点j，并使新节点j与m个已经存在的点连接（m≤n0）择优连接：新加入的点与网络中已经存在的点的连接不是等概率的，而是以一种择优的方式选择与自己连接的点。新节点j与节点i连接的概率:（2）赋边权(基于两个假设:权重Wij正比于节点i的度;所有新节点有相同的点权)新节点与已存在节点之间的每一条连接ji,被赋予一定的权重，权重的多少取决于被连接节点i的度{i‘}代表新节点j所要连接的点的集合。这时新节点j的点权为1lliijkkijwiiijikkw无标度加权网络模型特点：拓扑结构与BA模型相同，故度分布点权分布符合幂律分布：其中指数与参数m有关。边权分布3)(kkpsrssp)(ZTZH模型在WSF模型的基础上进行推广，赋边权时综合考虑节点的度和适应度。适应度：反应节点i本身的性质，假设其服从[0,1]上的均匀分布.(当不知道随机变量取值的特点时,假设其服从某一区间上的均匀分布)(1)网络结构拓扑演化同WSF网络(2)赋边权:设定一参数p以概率p按公式赋边权以概率1-p按公式赋边权当p=1时,ZTZH模型=WSF模型当p=1时,边权的赋予完全由节点的适应度决定.ZTZH模型的点强度分布也符合幂律分布，但是指数敏感地依赖于参数p，随着p的增加，从3连续下降。iiiijikkwiiijiwsrssp)(srsrAntal-Krapivsky提出了一个加权网络的演化模型，改进之处是在演化过程中考虑了边权对网络结构演化的影响。规则如下，每个时间间隔有一个节点j加入到网络中，并选择一个老节点建立连接，其连接概率正比于节点的强度：此规则关注点强度对连接的驱动作用，点强度越大的节点被连接到的概率越大。实际网络中，例Internet网络中，新的路由器会根据带宽或流量的处理能力连接到中枢路由器上。由于每个新顶点只有一条边，所以该模型生成的网络是树形结构的。lliijss•边权演化模型边权固定模型的共同的特点:边权一旦设定不再改变,也就是说网络中边的权重在初始时刻己经给定,而且随着网络规模的增大,边权没有任何变化。这与实际系统中的情况有很大的差异，比如在航空网络中随着航空网络的增大，与新加机场有连接关系的机场的各条航线上的客流量也会有相应的增加，在加权网络中就表现为边权的增加.这时在加权网络的演化模型中需要考虑边权的演化.下面建立基于点权的边权演化模型1.BBV模型(1)网络结构拓扑演化增长：初始时有n0个节点，每边赋权值为w0每个时间间隔加入一个带有m条边的新节点j，边权也为w0优先连接：根据选择老节点i与新节点j相连lliijSS•（2）边权演化新边的加入会导致节点i与其邻居节点之间的边权重重新分配。权