田 柳 狄增如 姚 虹

1)(北京师范大学管理学院系统科学系，北京 100875)

2)(Department of Economics，Maxwell School，Syracuse University，NY 13210，US)

3)(内蒙古农业大学理学院，呼和浩特 010018)

(2010年1月23日收到;2010年5月17日收到修改稿)

权重分布对加权网络效率的影响*

田 柳1)2)狄增如1)姚 虹3)†

1)(北京师范大学管理学院系统科学系，北京 100875)

2)(Department of Economics，Maxwell School，Syracuse University，NY 13210，US)

3)(内蒙古农业大学理学院，呼和浩特 010018)

(2010年1月23日收到;2010年5月17日收到修改稿)

加权网络可以对复杂系统的相互作用结构提供更加细致的刻画，而改变边权也成为调整和改善网络性质与功能的新途径.基于已有无权网络的效率概念，文中给出了相似权和相异权网络的网络效率定义，并研究了权重分布对于网络效率的影响.从平权的规则网络出发，通过改变权重的分布形式考察权重分布对网络效率的影响，结果发现，在规则网络上，权重分布随机性的增加提高了网络效率，而在几种常见的权重分布形式中，指数分布对网络效率的改进最为显著.同时，权重随机化之后网络最小生成树的总权重减小，意味着网络的运输成本随着权重异质性的增加而降低.以上结果为深入理解权重对网络结构与功能的影响提供了基础.

复杂网络，加权网络，权重，网络效率

PACS:89.75.Hc，89.75.Fb

1.引 言

复杂网络是许多复杂系统相互作用结构的抽象，而仅仅由点和边构成的二元网络是其中最简单的抽象，边的存在与否给出了相互作用结构的定性描述，是网络刻画中最本质的部分.但在许多实际系统中，顶点之间相互作用的强度对系统性质有重要的影响，此时我们就必须研究加权网络的性质.这种研究是有意义的，因为带有权重的网络，不管是相似权还是相异权，在现实世界中是普遍存在的，它能够更真实客观的抽象一个复杂系统.同时，有了权重这个新的维度，就多了一种调整网络结构和功能的手段.研究表明，权重的分布会影响网络的结构和动力学行为.权重重新分布可以缩小网络的最短距离、增加集聚系数，使网络表现出小世界效应，并且能够提高网络的同步能力，影响网络的集团结构［1，2］.

对于加权网络，虽然已经发展了一些相应的概念来刻画其结构性质，如加权的最短路径长度L和集聚系数C，但用这些量刻画网络全局和局部结构性质会损失网络的部分信息，因此有必要引入一些新的几何量，在继承L和C对网络描述准确性的基础上，从全局上更准确地刻画加权网络的性质.在无权网络上，Latora等［3］提出了网络效率的概念，仅用这样一个具有明确物理含义的量就能够描述网络的局部和全局性质，并且网络效率在一定程度上是L和C的一阶近似.网络效率概念与网络上的动力学过程，特别是传播过程密切相关.在网络上的传输过程中，网络拓扑结构［4，5］、路由策略［6］以及流量信息［7］都与网络效率有关，而有些网络效率的定义则是直接基于网络所实现的传输功能［8］.鉴于网络效率这一概念的重要性，我们应该把这一概念推广到加权网络上，事实上，加权网络上的传输问题已经得到了大家的关注［9］.

既然边权可以影响网络结构，网络效率作为描述网络结构的新手段，有必要考察边权分布对网络效率的影响.本文不仅考察了相同网络拓扑结构下权重随机分布对网络效率的影响，并且考察了其他常见的5种形式的权重分布，以期寻找较优的权重分布形式.考虑到网络的传输过程，网络的最小生成树在网络传输中起着重要的作用，随机化权重之后，网络结构变化的同时，网络最小生成树结构也发生变化.本文中我们关心的不是最小生成树的连接怎样改变，而是关注分布在最小生成树上的总权重发生了怎样的变化.在最小生成树中，各个节点并不处在相同的地位，那些拥有较高阶数的节点和边在最小生成树，也即整个网络中有着非常重要的地位，考察这些点的利用率可以更明确地刻画这些节点在网络传输过程中的地位和作用.

2.权重分布对网络效率的影响

2.1.权重与效率

根据权重意义和赋予方式的不同，权重可以分为两大类:相异权和相似权.通常我们研究得最多的都是与距离相对应的相异权，权重越大表示两个节点之间距离越远;而相似权却恰恰相反，权重越大代表节点之间越紧密，距离越小，这种权重在社会关系网络中普遍存在.比如，在科学家合作网中，权重越大代表两个科学家之间的合作越频繁越紧密.由于这两种权重的根本性质不同，导致相异权和相似权网络的基本统计量定义不同，因此明确相似权和相异权对加权网络的研究很有必要.

相异权和相似权的差异直接影响网络最短路径长度的定义.考虑每条边关联的距离是加权网络分析的重要问题.对于相异权，权重和距离成正比，因此可以把边上的权重直接转化为两点之间的距离，假设(i，j)通过节点 k相连，则 i，j之间的距离 dij=wik+wkj，其中w为权重.对于相似权，权重和距离是成反比的，因此可以令dsik=1/wik，顶点(i，j)的距离就要使用调和平均值dsij=wikwkj/wik+wkj来计算.

给连接赋予权重后，刻画系统性质就多了一个新的维度，同时也为调整和优化网络性质及功能提供了新的手段:除了改变网络的拓扑结构，对加权网络，在给定拓扑结构的基础上，还可以通过调整权重分布或边-权对应关系来影响网络性质，进而优化网络的功能.

在网络研究中，传统的用网络平均最短路径长度L和集聚系数C刻画网络的全局性质和局部特征的方法是要满足一定前提条件的:要求网络是无权的、稀疏的、简单的联通网络，仅仅使用这两个量描述网络结构性质丢失整体和局部的信息.为了取代或者补充原有这些量描述的不足，Latora等［3］给出了一个新的几何特征量来描述网络的性质——网络效率，衡量信息在网络上传播的有效程度.同最短路径和集聚系数描述网络的方法相比，它除了能够包含以上两个统计量包含的信息之外，还具有独特的优势:仅用这一个具有明确物理含义的量就能够代替L和C对网络全局和局部的表述，并能摆脱对网络结构的限制，完全不用去考虑网络是否带有权重、是否连通及网络是否稀疏.并且 C和1/L可以看作是局部效率和全局效率的一阶近似.

2.2.网络效率的定义

假设两个节点离得越近，信息在这两点之间就越容易传播，也就是说网络的权重为相异权.因此两个节点(i，j)之间的效率可以定义为这两点之间距离dij的倒数:eij=1/dij.与平均路径长度相比，即使两个节点之间没有通路相连，仍旧可以定义这两点之间的效率.在非联通的网络中，limdij→∞eij→0，但是这两点的路径长度则为无穷大.将网络所有节点对的效率平均就得到了整个网络的全局效率(Global Efficiency)［3］

从物理上来说，Eglob衡量信息并行传播时系统的效率，而1/L用来解释网络中只有一个信息包连续传播的网络的效率.

类似地，可以给出网络局部效率的定义

其中Gi是节点i的近邻组成的网络.

以上由Latora等给出的网络效率的定义是针对相异权和无权网络提出的.但是由于相异权同距离成正比，而相似权同距离成反比，有必要对相似权的网络的效率定义做相应改变.在相似权网络中，权重越大，节点间的关系越紧密，信息两个节点之间传播的效率越高，因此两个节点间的效率eij不能用(i，j)之间最短路径长度dsij的倒数表示.最简单和直观的是用相似权网络中两个节点的最短路径长度表示，即eij=dsij，相应的网络的全局效率和局部效率都要据此做如下修改:

对于给定的网络拓扑结构，由于目前还不清楚最优的权重和结构的匹配关系，我们没有对修改后的网络效率进行归一化.

Latora提出了网络效率的概念之后，对不同网络拓扑结构的无权网的效率考察发现，规则网对应着较高的局部效率和较低的全局效率，随机网具有较高的全局效率和较低的局部效率，而小世界网络同时具有较高的全局效率和局部效率［3］.这一结论验证了全局效率是平均路径长度的近似，局部效率是集聚系数的近似.对于加权网络，使用效率概念，我们就能够更准确地描述权重对网络性质和功能的影响.

2.3.权重分布对网络效率的影响

有了权重这个维度，我们就可以通过调整权重来调整网络性质和功能.调整权重的方式有两种，一种是保证每一份权值不变即权重的分布形式固定，改变权重和边的对应关系;另一种是保持权重的总量或均值不变，改变权重的分布形式.改变权重的分布形式是调整网络性质的一个重要途径，我们采用后者.研究发现，保持原有的拓扑结构不变，仅仅对权重进行随机化的调整，网络就可以出现同WS(watts-strogatz)一样的小世界效应［10］.并且，权重的分布能够在很大程度上影响网络的结构性质［11］、社团结构的划分［12］和网络的同步能力［13］.

为了考察权重对网络效率的影响，我们以规则网络为基础，应用同WS构造小世界网络类似的方法，对权重随机分布.构造小世界网络时，是以一定的概率对网络的连接重新分布，在这里，我们对权重重新随机分布，用随机化边权代替随机连边的过程［14］.从N个节点，每个节点连接k条边的规则一维网格出发，设初始每条边有相同的权重，W=5，此时权重为δ分布.边权随机分布的过程如下:

1)把每条边的权重W平均分成w/Δw等份(每份为 Δw);

2)以概率P随机抽取每份权重，然后把抽取出来的Wr份权重Δw再等概率随机赋到每条边上;

3)在这个过程中，要求保证每一条边都至少有一个单位权重，以不改变网络的拓扑结构.如果边上的权重恰好只剩下一个单位，这一单位的权重就不会被抽取出来，保证这条边上的权重不为零，使得权重随机化之后网络的拓扑结构与随机化之前保持一致.整个过程中网络的总权重保持不变.

由上述随机化过程可以从理论上得出权重的分布形式［13］.

在随机化权重的整个过程中，节点的连接并没有改变，但是这一操作过程可以改变权重分布，连续得到权重分布为δ分布(P=0)和泊松分布(P=1)之间的各种加权网络，通过分析δ分布和泊松分布的中间过程，就可以了解到权重随机化的影响.在以下关于权重随机化的计算机数值模拟中，为了减小随机因素所导致的涨落，我们给出的结果是20次随机试验的平均.由于标准差较小，在相关结果中没有给出误差区间.

如果网络权重相同，那么经过归一化之后就转化为无权网络，为了方便地考察权重分布对网络效率的影响和计算的方便，我们以每条边权重为5的加权网络做参照进行比较，在网络规模N=1000，每个节点的度为k=20的规则一维网格上，考察权重随机化对网络效率的影响.图1给出了在小世界网络上同时随机化权重时网络效率的变化情况.网络由规则网过渡到小世界网络并最终到随机网络的过程中，网络的局部效率不断降低，同时全局效率增高，在小世界网络上两者都处于比较高的状态.在此基础上，再以概率P=0.5随机分布权重之后，可以发现网络的全局效率和局部效率都得到了显著提高.需要注意的是随机化的过程中始终保证网络的总权重不变，即效率的提高并没有以提高成本为代价.在保证原有网络拓扑结构不变的情况下仅仅通过随机化权重，网络的效率就得到了提高，网络得到了优化.

即使在给定的初始规则网络上，权重的随机化也会对网络的效率带来影响.注意到相异权和相似权的差别，有必要对相异权和相似权的网络分别加以讨论.

考察发现，随着权重随机调整概率 P的变大，网络的效率不断提高，参见图2和3.权重分布的异质性导致了网络更高效率的出现，因此异质性可以作为寻求网络权重最优分布的参考方向.考虑到网络密度的影响，发现越是稠密的网络权重重新随机 分布的影响越高.

图1 在小世界网络上，权重分布对网络效率的影响 实线和虚线分别表示随机化权重前后的网络效率

图2 规则网上相异权网络效率随随机化概率P的变化 (a)全局效率，(b)局部效率 N=200，从上至下网络密度依次降低，度值分别为 k=40，20，10

图3 规则网上相似权网络效率随随机化概率P的变化 (a)全局效率，(b)局部效率 N=200，从上至下网络密度依次降低，度值分别为:k=40，20，10

由以上分析可知，权重的不同分布对网络的效率是有影响的.那么对于其他形式的权重分布，网络的效率如何变化呢?结果表明，不论权重是相异权还是相似权，是全局效率还是局部效率，在规则网、小世界网和随机网上，网络权重分布为指数分布的时候网络效率最高，参见图4和5.不同权重分布的产生方法如下:从每条边扣除所有的权重，将它们等分为小份，然后以不同分布的概率放回到网络的各边上.不同形式的分布权重的总和都是相等的.

通过考察不同的权重分布对网络的影响发现:与平权的网络相比，仅仅随机调整网络的权重分布就能显著提高网络的效率，由此除了改变网络的拓扑结构之外，又得到了一种新的手段和方法改变网络的属性，提高网络的效率.相比改变网络拓扑结构而言，调整权重是一种更为可行和实际的办法，特别是在某些条件下，网络的拓扑结构不能改变，权重调整可能是唯一的提高网络性能的手段.

图4 相异权网络上不同权重分布形式的网络效率 N=200，度或平均度k=20

图5 在相似权网络上比较不同权重分布形式的网络效率 (a)全局效率，(b)局部效率 N=200，度或平均度k=20

3.最小生成树和网络的效率

事实上，在网络的传输问题中网络效率更重要.而网络的传输总是期待以最小的花费遍历网络中每个节点，这个问题往往就转化为寻找网络最小生成树(MST)问题，MST的总权重就可以看作是网络传输的成本.

网络效率和成本作为一个问题的两个方面，孤立讨论是没有意义的.以增加成本为代价的效率的提高在实际中并不具有优势，因此有必要考察网络随机分布权重提高效率之后其传输成本的变化.

图6 小世界网络上MST总权重(相异权)随权重随机分布概率的变化

图6表明，在小世界网络上，MST的总权重是随着权重随机化概率的提高而减小的.在规则网和随机网络中也得到了定性一致的结论，表明在随机化权重的情况下，网络效率增加的同时最小生成树的总权重在变小，网络效率的提高并未以消耗更多的能量为代价.因此可以说随机化网络权重是一种有效优化网络传输的重要手段.初步研究还发现，在规则网络上权重的随机化还可以提高最小生成树的使用率，这在传输问题中具有重要意义［9，15］.

4.结 论

本文在加权网的基础上，基于已有无权网络的效率概念，给出了相似权和相异权网络的网络效率定义，并研究了权重分布对于网络效率的影响.从平权的规则网络出发，通过改变权重的分布形式考察权重分布对网络效率的影响.结果发现，权重异质性增加提高了网络效率，而边界数高的边更频繁的被利用是效率提高的一个因素.同时权重随机化之后，网络最小生成树的总权重减小，意味着网络的运输成本随着权重异质性增加而降低.以上结果对于深入理解权重对网络结构与功能的影响提供了基础.在研究中我们发现，在无标度网络上，权重随机化对于网络效率的改善并不明显，所以我们在本文中没有展示无标度网络上的模拟结果.其原因有可能是无标度网络本身就是连接异质性很强的网络，而权重异质性的效果就相应减弱了.事实上，除了权重分布的改变外，在给定权重分布的条件下，调整边权与边的对应关系也是改变网络性质的重要途径，给定网络的拓扑结构和网络功能，特别是在无标度网络上寻找最优的权重分布和边权匹配关系，仍然是加权网络研究的一个重要内容.

［1］Li Y，Lü L，Luan L 2009Acta Phys.Sin.58 4463(in Chinese)［李 岩、吕 翎、栾 玲2009物理学报 58 4463］

［2］Xu Q X，Xu X J 2009Chin.Phys.B 18 933

［3］Latora V，Marchiori M 2001Phys.Rev.Lett.87 198701

［4］Wu Z X，Peng G，Wong W M，Yeung K H 2008J.Stat.Mech.P11002

［5］Li T，Pei W J，Wang S P 2009Acta Phys.Sin.58 5903(in Chinese)［李 涛、裴文江、王少平2009物理学报 58 5903］

［6］Yan G，Zhou T，Hu B，Fu Z Q，Wang B H 2006Phys.Rev.E 73 046108

［7］Wang D，Jing Y W，Zhang S Y 2008PhysicaA 387 3001

［8］Nagurney A，Qiang Q 2008J.Glob.Opt.40 261

［9］Chen H L，Liu Z X，Chen Z Q，Yuan Z Z 2009Acta Phys.Sin.58 6068(in Chinese)［陈华良、刘忠信、陈增强、袁著祉 2009物理学报58 6068］

［10］Watts D J，Strogatz S H 1998Nature393 440

［11］Li M，Fan Y，Chen J，Gao L，Di Z，Wu J 2005PhysicaA 350 643

［12］Zhang P，Li M，Wu J，Di Z，Fan Y 2006PhysicaA 367 577

［13］Li D，Li M，Wu J，Di Z.，Fan Y 2007Eur.Phys.J.B 57 423

［14］Li M，Fan Y，Wang D，Li D，Wu J，Di Z 2007Phys.Lett.A 364 488

［15］Wu Z，Braunstein A L，Havlin S，Stanley H E 2006Phys.Rev.Lett.96 148702

PACS:89.75.Hc，89.75.Fb

Effect of distribution of weight on the
efficiency of weighted networks*

Tian Liu1)2)Di Zeng-Ru1)Yao Hong3)†
1)(Department of Systems Science，School of Management，Beijing Normal University，Beijing 100875，China)
2)(Department of Economics，Maxwell School，Syracuse University，NY 13210，US)
3)(School of Science，Inner Mongolia Agricultural University，Huhhot 010018，China)
(Received 23 January 2010;revised manuscript received 17 May 2010)

Weighted networks can give more detailed description of interaction between agents of corresponding systems.Link weight also provides another way to improve the properties and functions of networks.Based on the concept of network efficiency in binary networks，in this paper，the efficiency of weighted networks with similarity or dissimilarity weight is defined.The effect of weight distribution on the network efficiency are investigated.From the initial regular network with homogeneous link weights，a method is introduced to randomize the weight distribution over the links.The results demonstrate that the random redistribution of link weight can improve the network efficiency.Moreover，exponential distribution of link weight shows more significant improvement compared with the other common distributions，such as uniform，Poisson，Gauss，and power law distributions.Meanwhile，it is also found that the total weight of the corresponding minimum spanning tree is reduced with the randomization of link weight.That means the cost of transportation is decreased with the increase of link weight heterogeneity.All these results can help us get deeper understanding about the effect of link weight on the property and function of networks.

complex network，weighted network，weight，efficiency of network

*国家自然科学基金(批准号:70771011，60974084)资助的课题.

†通讯联系人.E-mail:yaohon163@163.com

*Project supported by the National Natural Science Foundation of China(Grant Nos.70771011，60974084).

†Corresponding author.E-mail:yaohon163@163.com