權重分布對加權網絡效率的影響*

田 柳 狄增如 姚 虹

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