在一些基础设施网络中，例如Internet,铁路网和航空网中， 运输过程中的流量可以转化为权重，Barrat等人分析了全 球航空网络，把两机场i和j之间的航班的有效座位数作为 机场间的权重 ，而ij 李炜等人在研究中国航空网时， 把两机场间的航班数作为机场间的权重。在对不同数据进 行研究时，发现这些网络具有小世界网络和无标度网络的 特征。特别是度分布表现为如下形式： p(k ) k f (k / kx ) ，其中 2.0 ，且 f (k / kx ) 是指数截 断函数。与一个机场能够运作的最大航线数有关。点强度 分布呈现出幂律尾，并且边权和度具有一定的相关性：平 均来讲，边权与边的两端顶点的度值的函数关系为 ij ~ (kik j ) 其中 0.5 。点强度和度之间的关系服从 幂律函数关系 s(k) Ak ，其中 1.5 ，这说明机场越大， 处理交通流量的能力就越强。
16
• 经济物理学科学家合作网络的建立和统计分析
科学家之间的合作有多个层次，若希望通过网络分析挖掘 科学家在科学研究上的内在关联就必须考虑不同层次的相 互作用的贡献，而网络连接权重就就需要综合考虑层次和 强度两个方面。考虑科学家交流的三个层次：合著，引用 和致谢，记录为 (S1, S2 , x, y, z) ，作者 S1与S 2 合作x次， 引用作者 的S文2 章y次，并且在 的S文1 章致谢里感谢 z次。S事2 实上，可以把整个数据看做三个不同的网络，合 著网络，引用网络和致谢网络，把这三种关系综合在一起 考虑，看做一个网络，采用以下赋权方式：
例:为研究某一新思想的在一个学术领域的产生传播,研究科学家之间通 过文献相互作用的网络。相互作用分为三个层次:合作,引文,致谢 (无权 网中能体现相互作用的三个层次吗?) 。 我们可以根据不同的作用关系做三个网络:合作网络,引文网络,致谢网络. 但即便对于同一个网络比如引文网络,引文次数不同所代表的相互作用 关系不同。(无权网中能表现相互作用的强度吗?) 这时必须考虑赋边权,表示相联系的强度. 另外,我们希望在同一个网络中研究这三个层次的相互作用,还应该考虑 加权的方式. 当系统中包含同一属性的不同层次的关系的时候,必须仔细研究加权方 式.
时，具有较大权重的边倾向于连接具有较大度值的点
当
kw nn,i
knn,i
时，具有较大权重的边倾向于连接具有较小度值的点
所以，对于相互作用强度（权重）给定的边，
kw nn,i
表明它与具有不同度值的顶
点之间的和力。
10
• 最短路径
1.加权网络中两点之间的距离与权重的关系：
距离是权重的某种函数，这时需要看权重是相似权还是相异权。
19
• 边权固定模型
1.无标度加权网络模型（WSF） 2001年，Yook和Barabasi提出了类似于BA模型的加权网络生成模型。
其定义如下：
（1）网络拓扑结构的演化（同BA模型） 增长：初始时有n0个节点，每个时间间隔加入一个新节点j，并使新节点j
与m个已经存在的点连接（m≤ n0 ） 择优连接：新加入的点与网络中已经存在的点的连接不是等概率的，而是
j,k
wij
其中 wij 为网络中经最大权重标准化后的数值
12
Petter Holme 分析加权网络的聚类系数，指出它应该满足以下几条要求：
1. C w [0,1]
2.加权网退化为无权网时，聚类系数应与Watts-Strogatz定义的聚类系数的计 算结果一致。
3.权值为0表示该边不存在。
4.包含节点i的三角形中三条边对 C w (i) 的贡献应与边的权重成正比。
第八讲 加权网络
2010.11.13 李凯凯
1
主要内容: • 8.1 加权网络的统计性质 • 8.2 加权网络的演化模型 • 8.3 权重对网络结构性质的影响
2
8.1加权网络的统计性质
1. 加权网络的加权的必要性与方式 2. 加权网络上的统计量
3
1. 网络加权的必要性与赋权方式
网络加权的必要性:
向于与度大的节点相连）
如果 Knn（k） 是减函数，那么该网络是负向匹配网络。
knn (k)
k nn,i
1
1
knn,i
ki
kj
jNi
ki
aij k j
jV
9
在加权网络中：
定义节点的加权平均近邻度
kw nn,i
1 Si
aij wij k j
jN j
考虑权与度的相关性
当
kw nn,i
knn,i
相异权：定义两点之间的距离 lij wij
相似权：令
lij
1 wij
假设顶点i和k分别通过两条权重分别为
wij
间的距离。
和 wjk 的边相连，现求i与k之
对于相异权： lik wij w jk
对于相似权：lik
1 1 1
wij
w jk
2.最短路径：两点之间所有连通的路径中距离之和最小的一条或几条路径。
密.(例:科学家合作网中,把次数作为权重,得到相似 权) 注意: 在计算两点间的距离和聚类系数时,边权的意 义不同,计算方式也不同.
5
2.加权网络上的统计量 权相关性 最短路径 集聚系数
6
权相关性
1.基本概念：
点权：无权网中节点度的自然推广
点权 Si wij ，即与节点i i关联的边权之和。（ 其中Ni 是节点i
14
• 2.社会网络
以科学家合作网为例，Newman定义了科学家合
作网的权重 ij
p
ip
p j
/(np
1)
，其中p包括数据
库中的所有文章，如果i是文章p的作者之一，
则
，否则 ip 1
ip 0
， n p 表示文章p中作者
的数目。从平均效果来看，合作者较少时作者之
间的相互关系更加紧密。
15
• 3.技术网络
22
Antal-Krapivsky提出了一个加权网络的演化模型， 改进之处是在演化过程中考虑了边权对网络结构 演化的影响。规则如下，每个时间间隔有一个节 点j加入到网络中，并选择一个老节点建立连接， 其连接概率正比于节点的强度：
ji
si l sl
此规则关注点强度对连接的驱动作用，点强度越 大的节点被连接到的概率越大。实际网络中，例 Internet网络中，新的路由器会根据带宽或流量 的处理能力连接到中枢路由器上。由于每个新顶 点只有一条边，所以该模型生成的网络是树形结 构的。
wij wij ，其中 可以取{1，2，3} 分别对应合著，
引用和致谢关系， wij 是三种关系所对应的权重，定义
为：wij tanh(Tij )
17
• 直观上说，次数越多关系越亲密，但是随着次数 的增加，，新事件对亲密程度的贡献越来越小， 即新事件对亲密程度的贡献具有边际递减效应。 因此采用具有饱和效应的tanh函数将次数转化为 权重，来刻画次数和亲密程度的非线性效应。假 定三种相互作用对权重的贡献也是不同的，用参 数 表 示。在研究经济物理学科学家合作网时， 分别取1,值为2 ,0.37，0.2，0.1。
7
结论2：差异性 Yi与度 k的关系
如果与顶点i关联的边的权重值差别不大，则 Yi 与
1 ki
成正比。
Yi
[ wij S jNi i
]2
[
wij ]2 w ki
ki
wij 2 1
w 2 ki2
ki
如果权值相差较大，那么只有一条边的权重起主要作用，则
Yi 1
8
2.相关性分析 加权网络需要进行 度相关性分析 点权相关性分析 权与度相关性分析
的近邻集合）
jNi
单权位重权分：布的Ui 差 Sk异ii, 性顶：点Yi连接jN的i[ wS平iij ]均2 表权示重与. i相连的边权分布的离散程度。
拥有相同点权与单位权的两个节点相比，差异性越大，离散程度越大。
点强度分布P（s）与度分布的作用类似，主要是考察节点具有点强度s的 概率。
边权分布P（w）代表一条边具有权重w的概率。
量取值的特点时,假设其服从某一区间上的均匀分布)
(1)网络结构拓扑演化同WSF网络
(2)赋边权:设定一参数p 以概率p按公式
w ji
ki ki
i
以概率1-p按公式
w ji
i i
当p=1时, ZTZH模型=WSF模型 i
赋边权 赋边权
当p=1时,边权的赋予完全由节点的适应度决定.
ZTZH模型的点强度分布也符合幂律分布 p(s) srs ，但是指数 rs 敏感地依赖于参 数p，随着p的增加，rs 从3连续下降。
Watts-Strogatz 定义的聚类系数:
aij a jk aki
C (i) j,k
aij aki
j ,k
wij w jk wki
加权网的聚类系数：
C
w H
j,k
m ax ij
wij
wij wik
j,k
13
一些加权网络的实证结果
• 1.生物网络
Almaas等人将酵母中的新陈代谢反应看作加权网络进行 研究，把从代谢物i到j的流量看作边权 ，观察到流量具有 高度非均匀性，在理想的培养下条件下，边权的分布符合 幂律分布 p()(0 ) 其中 0 0.0003 ， 1.5 此外还发现给定两端度值的边的权重平均值和两个端点的 度值的关系为 ij ~ (kik j ) ，其中 0.5。除了全局流量 分布的非均匀性外，计算边权差异性 Yi 还可以观察到在 单个代谢物的层面上边权分布的非均匀性。在此网络上对 出度和入度相同的顶点计算边权差异性，发现它们都服从 Yi ~ k 0.27 这是一种介于Y (k) const 和 Y (k) ~ k 1 之间的中间 状态，说明一个代谢物参与的化学反应越多，其中的某一 个化学反应携带主要流量的可能性就越高。??