物 理 学 报Acta Phys. Sin.Vol. 60，No. 2 ( 2011) 0289012011 中国物理学会 Chinese Physical Societyhttp: / /wulixb. iphy. ac. cn028901-1权重分布对加权网络效率的影响*田柳1) 2)狄增如1)姚虹3) 1) ( 北京师范大学管理学院系统科学系，北京100875)2) ( Department of Economics，Maxwell School，Syracuse University，NY13210，US)3) ( 内蒙古农业大学理学院，呼和浩特010018)( 2010 年 1 月 23 日收到; 2010 年 5 月 17 日收到修改稿)加权网络可以对复杂系统的相互作用结构提供更加细致的刻画， 而改变边权也成为调整和改善网络性质与功能的新途径. 基于已有无权网络的效率概念， 文中给出了相似权和相异权网络的网络效率定义， 并研究了权重分布对于网络效率的影响. 从平权的规则网络出发， 通过改变权重的分布形式考察权重分布对网络效率的影响， 结果发现， 在规则网络上， 权重分布随机性的增加提高了网络效率， 而在几种常见的权重分布形式中， 指数分布对网络效率的改进最为显著. 同时， 权重随机化之后网络最小生成树的总权重减小， 意味着网络的运输成本随着权重异质性的增加而降低. 以上结果为深入理解权重对网络结构与功能的影响提供了基础.关键词:复杂网络，加权网络，权重，网络效率PACS:89. 75. Hc，89. 75. Fb* 国家自然科学基金( 批准号: 70771011， 60974084) 资助的课题. 通讯联系人. E-mail:yaohon163 163. com1. 引言复杂网络是许多复杂系统相互作用结构的抽象， 而仅仅由点和边构成的二元网络是其中最简单的抽象， 边的存在与否给出了相互作用结构的定性描述， 是网络刻画中最本质的部分. 但在许多实际系统中， 顶点之间相互作用的强度对系统性质有重要的影响， 此时我们就必须研究加权网络的性质.这种研究是有意义的， 因为带有权重的网络， 不管是相似权还是相异权， 在现实世界中是普遍存在的， 它能够更真实客观的抽象一个复杂系统. 同时，有了权重这个新的维度， 就多了一种调整网络结构和功能的手段. 研究表明， 权重的分布会影响网络的结构和动力学行为. 权重重新分布可以缩小网络的最短距离、 增加集聚系数， 使网络表现出小世界效应， 并且能够提高网络的同步能力， 影响网络的集团结构 1， 2.对于加权网络， 虽然已经发展了一些相应的概念来刻画其结构性质， 如加权的最短路径长度 L 和集聚系数 C， 但用这些量刻画网络全局和局部结构性质会损失网络的部分信息， 因此有必要引入一些新的几何量， 在继承 L 和 C 对网络描述准确性的基础上， 从全局上更准确地刻画加权网络的性质. 在无权网络上， Latora 等 3提出了网络效率的概念， 仅用这样一个具有明确物理含义的量就能够描述网络的局部和全局性质， 并且网络效率在一定程度上是 L 和 C 的一阶近似. 网络效率概念与网络上的动力学过程， 特别是传播过程密切相关. 在网络上的传输过程中， 网络拓扑结构 4， 5、 路由策略 6以及流量信息 7都与网络效率有关， 而有些网络效率的定义则是直接基于网络所实现的传输功能 8. 鉴于网络效率这一概念的重要性， 我们应该把这一概念推广到加权网络上， 事实上， 加权网络上的传输问题已经得到了大家的关注 9.既然边权可以影响网络结构， 网络效率作为描述网络结构的新手段， 有必要考察边权分布对网络效率的影响. 本文不仅考察了相同网络拓扑结构下权重随机分布对网络效率的影响， 并且考察了其他常见的 5 种形式的权重分布， 以期寻找较优的权重分布形式. 考虑到网络的传输过程， 网络的最小生成树在网络传输中起着重要的作用， 随机化权重之后， 网络结构变化的同时， 网络最小生成树结构也发生变化. 本文中我们关心的不是最小生成树的连物 理 学 报Acta Phys. Sin.Vol. 60，No. 2 ( 2011) 028901028901-2接怎样改变， 而是关注分布在最小生成树上的总权重发生了怎样的变化. 在最小生成树中， 各个节点并不处在相同的地位， 那些拥有较高阶数的节点和边在最小生成树， 也即整个网络中有着非常重要的地位， 考察这些点的利用率可以更明确地刻画这些节点在网络传输过程中的地位和作用.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. 与平均路径长度相比， 即使两个节点之间没有通路相连， 仍旧可以定义这两点之间的效率. 在非联通的网络中， limdijeij0， 但是这两点的路径长度则为无穷大. 将网络所有节点对的 效 率 平 均 就 得 到 了 整 个 网 络 的 全 局 效 率( Global Efficiency) 3Eglob=1 N( N 1) ijeij=1 N( N 1) ij1 /dij， ( 1)从物理上来说， Eglob衡量信息并行传播时系统的效率， 而 1 /L 用来解释网络中只有一个信息包连续传播的网络的效率.类似地， 可以给出网络局部效率的定义Eloc= 1 /N iGEGi，( 2)其中 Gi是节点 i 的近邻组成的网络.以上由 Latora 等给出的网络效率的定义是针对相异权和无权网络提出的. 但是由于相异权同距离成正比， 而相似权同距离成反比， 有必要对相似权的网络的效率定义做相应改变. 在相似权网络中，权重越大， 节点间的关系越紧密， 信息两个节点之间传播的效率越高， 因此两个节点间的效率 eij不能用( i， j) 之间最短路径长度 dsij的倒数表示. 最简单和 直观的是用相似权网络中两个节点的最短路径长度表示， 即 eij= dsij， 相应的网络的全局效率和局部效 率都要据此做如下修改:Eglob=1 N( N 1) ijeij=1 N( N 1) ijdsij. ( 3)对于给定的网络拓扑结构， 由于目前还不清楚最优的权重和结构的匹配关系， 我们没有对修改后的网络效率进行归一化.Latora 提出了网络效率的概念之后， 对不同网络拓扑结构的无权网的效率考察发现， 规则网对应物 理 学 报Acta Phys. Sin.Vol. 60，No. 2 ( 2011) 028901028901-3着较高的局部效率和较低的全局效率， 随机网具有较高的全局效率和较低的局部效率， 而小世界网络同时具有较高的全局效率和局部效率 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次随机试验的平均. 由于标准差较小， 在相关结果中没有给出误差区间.图 1在小世界网络上， 权重分布对网络效率的影响实线和虚线分别表示随机化权重前后的网络效率如果网络权重相同， 那么经过归一化之后就转化为无权网络， 为了方便地考察权重分布对网络效率的影响和计算的方便， 我