權(quán)重分布對加權(quán)網(wǎng)絡(luò)效率的影響*

田 柳 狄增如 姚 虹

1)(北京師范大學管理學院系統(tǒng)科學系，北京 100875)

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

3)(內(nèi)蒙古農(nóng)業(yè)大學理學院，呼和浩特 010018)

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

權(quán)重分布對加權(quán)網(wǎng)絡(luò)效率的影響*

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

1)(北京師范大學管理學院系統(tǒng)科學系，北京 100875)

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

3)(內(nèi)蒙古農(nóng)業(yè)大學理學院，呼和浩特 010018)

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

加權(quán)網(wǎng)絡(luò)可以對復(fù)雜系統(tǒng)的相互作用結(jié)構(gòu)提供更加細致的刻畫，而改變邊權(quán)也成為調(diào)整和改善網(wǎng)絡(luò)性質(zhì)與功能的新途徑.基于已有無權(quán)網(wǎng)絡(luò)的效率概念，文中給出了相似權(quán)和相異權(quán)網(wǎng)絡(luò)的網(wǎng)絡(luò)效率定義，并研究了權(quán)重分布對于網(wǎng)絡(luò)效率的影響.從平權(quán)的規(guī)則網(wǎng)絡(luò)出發(fā)，通過改變權(quán)重的分布形式考察權(quán)重分布對網(wǎng)絡(luò)效率的影響，結(jié)果發(fā)現(xiàn)，在規(guī)則網(wǎng)絡(luò)上，權(quán)重分布隨機性的增加提高了網(wǎng)絡(luò)效率，而在幾種常見的權(quán)重分布形式中，指數(shù)分布對網(wǎng)絡(luò)效率的改進最為顯著.同時，權(quán)重隨機化之后網(wǎng)絡(luò)最小生成樹的總權(quán)重減小，意味著網(wǎng)絡(luò)的運輸成本隨著權(quán)重異質(zhì)性的增加而降低.以上結(jié)果為深入理解權(quán)重對網(wǎng)絡(luò)結(jié)構(gòu)與功能的影響提供了基礎(chǔ).

復(fù)雜網(wǎng)絡(luò)，加權(quán)網(wǎng)絡(luò)，權(quán)重，網(wǎng)絡(luò)效率

PACS:89.75.Hc，89.75.Fb

1.引 言

復(fù)雜網(wǎng)絡(luò)是許多復(fù)雜系統(tǒng)相互作用結(jié)構(gòu)的抽象，而僅僅由點和邊構(gòu)成的二元網(wǎng)絡(luò)是其中最簡單的抽象，邊的存在與否給出了相互作用結(jié)構(gòu)的定性描述，是網(wǎng)絡(luò)刻畫中最本質(zhì)的部分.但在許多實際系統(tǒng)中，頂點之間相互作用的強度對系統(tǒng)性質(zhì)有重要的影響，此時我們就必須研究加權(quán)網(wǎng)絡(luò)的性質(zhì).這種研究是有意義的，因為帶有權(quán)重的網(wǎng)絡(luò)，不管是相似權(quán)還是相異權(quán)，在現(xiàn)實世界中是普遍存在的，它能夠更真實客觀的抽象一個復(fù)雜系統(tǒng).同時，有了權(quán)重這個新的維度，就多了一種調(diào)整網(wǎng)絡(luò)結(jié)構(gòu)和功能的手段.研究表明，權(quán)重的分布會影響網(wǎng)絡(luò)的結(jié)構(gòu)和動力學行為.權(quán)重重新分布可以縮小網(wǎng)絡(luò)的最短距離、增加集聚系數(shù)，使網(wǎng)絡(luò)表現(xiàn)出小世界效應(yīng)，并且能夠提高網(wǎng)絡(luò)的同步能力，影響網(wǎng)絡(luò)的集團結(jié)構(gòu)［1，2］.

對于加權(quán)網(wǎng)絡(luò)，雖然已經(jīng)發(fā)展了一些相應(yīng)的概念來刻畫其結(jié)構(gòu)性質(zhì)，如加權(quán)的最短路徑長度L和集聚系數(shù)C，但用這些量刻畫網(wǎng)絡(luò)全局和局部結(jié)構(gòu)性質(zhì)會損失網(wǎng)絡(luò)的部分信息，因此有必要引入一些新的幾何量，在繼承L和C對網(wǎng)絡(luò)描述準確性的基礎(chǔ)上，從全局上更準確地刻畫加權(quán)網(wǎng)絡(luò)的性質(zhì).在無權(quán)網(wǎng)絡(luò)上，Latora等［3］提出了網(wǎng)絡(luò)效率的概念，僅用這樣一個具有明確物理含義的量就能夠描述網(wǎng)絡(luò)的局部和全局性質(zhì)，并且網(wǎng)絡(luò)效率在一定程度上是L和C的一階近似.網(wǎng)絡(luò)效率概念與網(wǎng)絡(luò)上的動力學過程，特別是傳播過程密切相關(guān).在網(wǎng)絡(luò)上的傳輸過程中，網(wǎng)絡(luò)拓撲結(jié)構(gòu)［4，5］、路由策略［6］以及流量信息［7］都與網(wǎng)絡(luò)效率有關(guān)，而有些網(wǎng)絡(luò)效率的定義則是直接基于網(wǎng)絡(luò)所實現(xiàn)的傳輸功能［8］.鑒于網(wǎng)絡(luò)效率這一概念的重要性，我們應(yīng)該把這一概念推廣到加權(quán)網(wǎng)絡(luò)上，事實上，加權(quán)網(wǎng)絡(luò)上的傳輸問題已經(jīng)得到了大家的關(guān)注［9］.

既然邊權(quán)可以影響網(wǎng)絡(luò)結(jié)構(gòu)，網(wǎng)絡(luò)效率作為描述網(wǎng)絡(luò)結(jié)構(gòu)的新手段，有必要考察邊權(quán)分布對網(wǎng)絡(luò)效率的影響.本文不僅考察了相同網(wǎng)絡(luò)拓撲結(jié)構(gòu)下權(quán)重隨機分布對網(wǎng)絡(luò)效率的影響，并且考察了其他常見的5種形式的權(quán)重分布，以期尋找較優(yōu)的權(quán)重分布形式.考慮到網(wǎng)絡(luò)的傳輸過程，網(wǎng)絡(luò)的最小生成樹在網(wǎng)絡(luò)傳輸中起著重要的作用，隨機化權(quán)重之后，網(wǎng)絡(luò)結(jié)構(gòu)變化的同時，網(wǎng)絡(luò)最小生成樹結(jié)構(gòu)也發(fā)生變化.本文中我們關(guān)心的不是最小生成樹的連接怎樣改變，而是關(guān)注分布在最小生成樹上的總權(quán)重發(fā)生了怎樣的變化.在最小生成樹中，各個節(jié)點并不處在相同的地位，那些擁有較高階數(shù)的節(jié)點和邊在最小生成樹，也即整個網(wǎng)絡(luò)中有著非常重要的地位，考察這些點的利用率可以更明確地刻畫這些節(jié)點在網(wǎng)絡(luò)傳輸過程中的地位和作用.

2.權(quán)重分布對網(wǎng)絡(luò)效率的影響

2.1.權(quán)重與效率

根據(jù)權(quán)重意義和賦予方式的不同，權(quán)重可以分為兩大類:相異權(quán)和相似權(quán).通常我們研究得最多的都是與距離相對應(yīng)的相異權(quán)，權(quán)重越大表示兩個節(jié)點之間距離越遠;而相似權(quán)卻恰恰相反，權(quán)重越大代表節(jié)點之間越緊密，距離越小，這種權(quán)重在社會關(guān)系網(wǎng)絡(luò)中普遍存在.比如，在科學家合作網(wǎng)中，權(quán)重越大代表兩個科學家之間的合作越頻繁越緊密.由于這兩種權(quán)重的根本性質(zhì)不同，導(dǎo)致相異權(quán)和相似權(quán)網(wǎng)絡(luò)的基本統(tǒng)計量定義不同，因此明確相似權(quán)和相異權(quán)對加權(quán)網(wǎng)絡(luò)的研究很有必要.

相異權(quán)和相似權(quán)的差異直接影響網(wǎng)絡(luò)最短路徑長度的定義.考慮每條邊關(guān)聯(lián)的距離是加權(quán)網(wǎng)絡(luò)分析的重要問題.對于相異權(quán)，權(quán)重和距離成正比，因此可以把邊上的權(quán)重直接轉(zhuǎn)化為兩點之間的距離，假設(shè)(i，j)通過節(jié)點 k相連，則 i，j之間的距離 dij=wik+wkj，其中w為權(quán)重.對于相似權(quán)，權(quán)重和距離是成反比的，因此可以令dsik=1/wik，頂點(i，j)的距離就要使用調(diào)和平均值dsij=wikwkj/wik+wkj來計算.

給連接賦予權(quán)重后，刻畫系統(tǒng)性質(zhì)就多了一個新的維度，同時也為調(diào)整和優(yōu)化網(wǎng)絡(luò)性質(zhì)及功能提供了新的手段:除了改變網(wǎng)絡(luò)的拓撲結(jié)構(gòu)，對加權(quán)網(wǎng)絡(luò)，在給定拓撲結(jié)構(gòu)的基礎(chǔ)上，還可以通過調(diào)整權(quán)重分布或邊-權(quán)對應(yīng)關(guān)系來影響網(wǎng)絡(luò)性質(zhì)，進而優(yōu)化網(wǎng)絡(luò)的功能.

在網(wǎng)絡(luò)研究中，傳統(tǒng)的用網(wǎng)絡(luò)平均最短路徑長度L和集聚系數(shù)C刻畫網(wǎng)絡(luò)的全局性質(zhì)和局部特征的方法是要滿足一定前提條件的:要求網(wǎng)絡(luò)是無權(quán)的、稀疏的、簡單的聯(lián)通網(wǎng)絡(luò)，僅僅使用這兩個量描述網(wǎng)絡(luò)結(jié)構(gòu)性質(zhì)丟失整體和局部的信息.為了取代或者補充原有這些量描述的不足，Latora等［3］給出了一個新的幾何特征量來描述網(wǎng)絡(luò)的性質(zhì)——網(wǎng)絡(luò)效率，衡量信息在網(wǎng)絡(luò)上傳播的有效程度.同最短路徑和集聚系數(shù)描述網(wǎng)絡(luò)的方法相比，它除了能夠包含以上兩個統(tǒng)計量包含的信息之外，還具有獨特的優(yōu)勢:僅用這一個具有明確物理含義的量就能夠代替L和C對網(wǎng)絡(luò)全局和局部的表述，并能擺脫對網(wǎng)絡(luò)結(jié)構(gòu)的限制，完全不用去考慮網(wǎng)絡(luò)是否帶有權(quán)重、是否連通及網(wǎng)絡(luò)是否稀疏.并且 C和1/L可以看作是局部效率和全局效率的一階近似.

2.2.網(wǎng)絡(luò)效率的定義

假設(shè)兩個節(jié)點離得越近，信息在這兩點之間就越容易傳播，也就是說網(wǎng)絡(luò)的權(quán)重為相異權(quán).因此兩個節(jié)點(i，j)之間的效率可以定義為這兩點之間距離dij的倒數(shù):eij=1/dij.與平均路徑長度相比，即使兩個節(jié)點之間沒有通路相連，仍舊可以定義這兩點之間的效率.在非聯(lián)通的網(wǎng)絡(luò)中，limdij→∞eij→0，但是這兩點的路徑長度則為無窮大.將網(wǎng)絡(luò)所有節(jié)點對的效率平均就得到了整個網(wǎng)絡(luò)的全局效率(Global Efficiency)［3］

從物理上來說，Eglob衡量信息并行傳播時系統(tǒng)的效率，而1/L用來解釋網(wǎng)絡(luò)中只有一個信息包連續(xù)傳播的網(wǎng)絡(luò)的效率.

類似地，可以給出網(wǎng)絡(luò)局部效率的定義

其中Gi是節(jié)點i的近鄰組成的網(wǎng)絡(luò).

以上由Latora等給出的網(wǎng)絡(luò)效率的定義是針對相異權(quán)和無權(quán)網(wǎng)絡(luò)提出的.但是由于相異權(quán)同距離成正比，而相似權(quán)同距離成反比，有必要對相似權(quán)的網(wǎng)絡(luò)的效率定義做相應(yīng)改變.在相似權(quán)網(wǎng)絡(luò)中，權(quán)重越大，節(jié)點間的關(guān)系越緊密，信息兩個節(jié)點之間傳播的效率越高，因此兩個節(jié)點間的效率eij不能用(i，j)之間最短路徑長度dsij的倒數(shù)表示.最簡單和直觀的是用相似權(quán)網(wǎng)絡(luò)中兩個節(jié)點的最短路徑長度表示，即eij=dsij，相應(yīng)的網(wǎng)絡(luò)的全局效率和局部效率都要據(jù)此做如下修改:

對于給定的網(wǎng)絡(luò)拓撲結(jié)構(gòu)，由于目前還不清楚最優(yōu)的權(quán)重和結(jié)構(gòu)的匹配關(guān)系，我們沒有對修改后的網(wǎng)絡(luò)效率進行歸一化.

Latora提出了網(wǎng)絡(luò)效率的概念之后，對不同網(wǎng)絡(luò)拓撲結(jié)構(gòu)的無權(quán)網(wǎng)的效率考察發(fā)現(xiàn)，規(guī)則網(wǎng)對應(yīng)著較高的局部效率和較低的全局效率，隨機網(wǎng)具有較高的全局效率和較低的局部效率，而小世界網(wǎng)絡(luò)同時具有較高的全局效率和局部效率［3］.這一結(jié)論驗證了全局效率是平均路徑長度的近似，局部效率是集聚系數(shù)的近似.對于加權(quán)網(wǎng)絡(luò)，使用效率概念，我們就能夠更準確地描述權(quán)重對網(wǎng)絡(luò)性質(zhì)和功能的影響.

2.3.權(quán)重分布對網(wǎng)絡(luò)效率的影響

有了權(quán)重這個維度，我們就可以通過調(diào)整權(quán)重來調(diào)整網(wǎng)絡(luò)性質(zhì)和功能.調(diào)整權(quán)重的方式有兩種，一種是保證每一份權(quán)值不變即權(quán)重的分布形式固定，改變權(quán)重和邊的對應(yīng)關(guān)系;另一種是保持權(quán)重的總量或均值不變，改變權(quán)重的分布形式.改變權(quán)重的分布形式是調(diào)整網(wǎng)絡(luò)性質(zhì)的一個重要途徑，我們采用后者.研究發(fā)現(xiàn)，保持原有的拓撲結(jié)構(gòu)不變，僅僅對權(quán)重進行隨機化的調(diào)整，網(wǎng)絡(luò)就可以出現(xiàn)同WS(watts-strogatz)一樣的小世界效應(yīng)［10］.并且，權(quán)重的分布能夠在很大程度上影響網(wǎng)絡(luò)的結(jié)構(gòu)性質(zhì)［11］、社團結(jié)構(gòu)的劃分［12］和網(wǎng)絡(luò)的同步能力［13］.

為了考察權(quán)重對網(wǎng)絡(luò)效率的影響，我們以規(guī)則網(wǎng)絡(luò)為基礎(chǔ)，應(yīng)用同WS構(gòu)造小世界網(wǎng)絡(luò)類似的方法，對權(quán)重隨機分布.構(gòu)造小世界網(wǎng)絡(luò)時，是以一定的概率對網(wǎng)絡(luò)的連接重新分布，在這里，我們對權(quán)重重新隨機分布，用隨機化邊權(quán)代替隨機連邊的過程［14］.從N個節(jié)點，每個節(jié)點連接k條邊的規(guī)則一維網(wǎng)格出發(fā)，設(shè)初始每條邊有相同的權(quán)重，W=5，此時權(quán)重為δ分布.邊權(quán)隨機分布的過程如下:

1)把每條邊的權(quán)重W平均分成w/Δw等份(每份為 Δw);

2)以概率P隨機抽取每份權(quán)重，然后把抽取出來的Wr份權(quán)重Δw再等概率隨機賦到每條邊上;

3)在這個過程中，要求保證每一條邊都至少有一個單位權(quán)重，以不改變網(wǎng)絡(luò)的拓撲結(jié)構(gòu).如果邊上的權(quán)重恰好只剩下一個單位，這一單位的權(quán)重就不會被抽取出來，保證這條邊上的權(quán)重不為零，使得權(quán)重隨機化之后網(wǎng)絡(luò)的拓撲結(jié)構(gòu)與隨機化之前保持一致.整個過程中網(wǎng)絡(luò)的總權(quán)重保持不變.

由上述隨機化過程可以從理論上得出權(quán)重的分布形式［13］.

在隨機化權(quán)重的整個過程中，節(jié)點的連接并沒有改變，但是這一操作過程可以改變權(quán)重分布，連續(xù)得到權(quán)重分布為δ分布(P=0)和泊松分布(P=1)之間的各種加權(quán)網(wǎng)絡(luò)，通過分析δ分布和泊松分布的中間過程，就可以了解到權(quán)重隨機化的影響.在以下關(guān)于權(quán)重隨機化的計算機數(shù)值模擬中，為了減小隨機因素所導(dǎo)致的漲落，我們給出的結(jié)果是20次隨機試驗的平均.由于標準差較小，在相關(guān)結(jié)果中沒有給出誤差區(qū)間.

如果網(wǎng)絡(luò)權(quán)重相同，那么經(jīng)過歸一化之后就轉(zhuǎn)化為無權(quán)網(wǎng)絡(luò)，為了方便地考察權(quán)重分布對網(wǎng)絡(luò)效率的影響和計算的方便，我們以每條邊權(quán)重為5的加權(quán)網(wǎng)絡(luò)做參照進行比較，在網(wǎng)絡(luò)規(guī)模N=1000，每個節(jié)點的度為k=20的規(guī)則一維網(wǎng)格上，考察權(quán)重隨機化對網(wǎng)絡(luò)效率的影響.圖1給出了在小世界網(wǎng)絡(luò)上同時隨機化權(quán)重時網(wǎng)絡(luò)效率的變化情況.網(wǎng)絡(luò)由規(guī)則網(wǎng)過渡到小世界網(wǎng)絡(luò)并最終到隨機網(wǎng)絡(luò)的過程中，網(wǎng)絡(luò)的局部效率不斷降低，同時全局效率增高，在小世界網(wǎng)絡(luò)上兩者都處于比較高的狀態(tài).在此基礎(chǔ)上，再以概率P=0.5隨機分布權(quán)重之后，可以發(fā)現(xiàn)網(wǎng)絡(luò)的全局效率和局部效率都得到了顯著提高.需要注意的是隨機化的過程中始終保證網(wǎng)絡(luò)的總權(quán)重不變，即效率的提高并沒有以提高成本為代價.在保證原有網(wǎng)絡(luò)拓撲結(jié)構(gòu)不變的情況下僅僅通過隨機化權(quán)重，網(wǎng)絡(luò)的效率就得到了提高，網(wǎng)絡(luò)得到了優(yōu)化.

即使在給定的初始規(guī)則網(wǎng)絡(luò)上，權(quán)重的隨機化也會對網(wǎng)絡(luò)的效率帶來影響.注意到相異權(quán)和相似權(quán)的差別，有必要對相異權(quán)和相似權(quán)的網(wǎng)絡(luò)分別加以討論.

考察發(fā)現(xiàn)，隨著權(quán)重隨機調(diào)整概率 P的變大，網(wǎng)絡(luò)的效率不斷提高，參見圖2和3.權(quán)重分布的異質(zhì)性導(dǎo)致了網(wǎng)絡(luò)更高效率的出現(xiàn)，因此異質(zhì)性可以作為尋求網(wǎng)絡(luò)權(quán)重最優(yōu)分布的參考方向.考慮到網(wǎng)絡(luò)密度的影響，發(fā)現(xiàn)越是稠密的網(wǎng)絡(luò)權(quán)重重新隨機 分布的影響越高.

圖1 在小世界網(wǎng)絡(luò)上，權(quán)重分布對網(wǎng)絡(luò)效率的影響 實線和虛線分別表示隨機化權(quán)重前后的網(wǎng)絡(luò)效率

圖2 規(guī)則網(wǎng)上相異權(quán)網(wǎng)絡(luò)效率隨隨機化概率P的變化 (a)全局效率，(b)局部效率 N=200，從上至下網(wǎng)絡(luò)密度依次降低，度值分別為 k=40，20，10

圖3 規(guī)則網(wǎng)上相似權(quán)網(wǎng)絡(luò)效率隨隨機化概率P的變化 (a)全局效率，(b)局部效率 N=200，從上至下網(wǎng)絡(luò)密度依次降低，度值分別為:k=40，20，10

由以上分析可知，權(quán)重的不同分布對網(wǎng)絡(luò)的效率是有影響的.那么對于其他形式的權(quán)重分布，網(wǎng)絡(luò)的效率如何變化呢?結(jié)果表明，不論權(quán)重是相異權(quán)還是相似權(quán)，是全局效率還是局部效率，在規(guī)則網(wǎng)、小世界網(wǎng)和隨機網(wǎng)上，網(wǎng)絡(luò)權(quán)重分布為指數(shù)分布的時候網(wǎng)絡(luò)效率最高，參見圖4和5.不同權(quán)重分布的產(chǎn)生方法如下:從每條邊扣除所有的權(quán)重，將它們等分為小份，然后以不同分布的概率放回到網(wǎng)絡(luò)的各邊上.不同形式的分布權(quán)重的總和都是相等的.

通過考察不同的權(quán)重分布對網(wǎng)絡(luò)的影響發(fā)現(xiàn):與平權(quán)的網(wǎng)絡(luò)相比，僅僅隨機調(diào)整網(wǎng)絡(luò)的權(quán)重分布就能顯著提高網(wǎng)絡(luò)的效率，由此除了改變網(wǎng)絡(luò)的拓撲結(jié)構(gòu)之外，又得到了一種新的手段和方法改變網(wǎng)絡(luò)的屬性，提高網(wǎng)絡(luò)的效率.相比改變網(wǎng)絡(luò)拓撲結(jié)構(gòu)而言，調(diào)整權(quán)重是一種更為可行和實際的辦法，特別是在某些條件下，網(wǎng)絡(luò)的拓撲結(jié)構(gòu)不能改變，權(quán)重調(diào)整可能是唯一的提高網(wǎng)絡(luò)性能的手段.

圖4 相異權(quán)網(wǎng)絡(luò)上不同權(quán)重分布形式的網(wǎng)絡(luò)效率 N=200，度或平均度k=20

圖5 在相似權(quán)網(wǎng)絡(luò)上比較不同權(quán)重分布形式的網(wǎng)絡(luò)效率 (a)全局效率，(b)局部效率 N=200，度或平均度k=20

3.最小生成樹和網(wǎng)絡(luò)的效率

事實上，在網(wǎng)絡(luò)的傳輸問題中網(wǎng)絡(luò)效率更重要.而網(wǎng)絡(luò)的傳輸總是期待以最小的花費遍歷網(wǎng)絡(luò)中每個節(jié)點，這個問題往往就轉(zhuǎn)化為尋找網(wǎng)絡(luò)最小生成樹(MST)問題，MST的總權(quán)重就可以看作是網(wǎng)絡(luò)傳輸?shù)某杀?

網(wǎng)絡(luò)效率和成本作為一個問題的兩個方面，孤立討論是沒有意義的.以增加成本為代價的效率的提高在實際中并不具有優(yōu)勢，因此有必要考察網(wǎng)絡(luò)隨機分布權(quán)重提高效率之后其傳輸成本的變化.

圖6 小世界網(wǎng)絡(luò)上MST總權(quán)重(相異權(quán))隨權(quán)重隨機分布概率的變化

圖6表明，在小世界網(wǎng)絡(luò)上，MST的總權(quán)重是隨著權(quán)重隨機化概率的提高而減小的.在規(guī)則網(wǎng)和隨機網(wǎng)絡(luò)中也得到了定性一致的結(jié)論，表明在隨機化權(quán)重的情況下，網(wǎng)絡(luò)效率增加的同時最小生成樹的總權(quán)重在變小，網(wǎng)絡(luò)效率的提高并未以消耗更多的能量為代價.因此可以說隨機化網(wǎng)絡(luò)權(quán)重是一種有效優(yōu)化網(wǎng)絡(luò)傳輸?shù)闹匾侄?初步研究還發(fā)現(xiàn)，在規(guī)則網(wǎng)絡(luò)上權(quán)重的隨機化還可以提高最小生成樹的使用率，這在傳輸問題中具有重要意義［9，15］.

4.結(jié) 論

本文在加權(quán)網(wǎng)的基礎(chǔ)上，基于已有無權(quán)網(wǎng)絡(luò)的效率概念，給出了相似權(quán)和相異權(quán)網(wǎng)絡(luò)的網(wǎng)絡(luò)效率定義，并研究了權(quán)重分布對于網(wǎng)絡(luò)效率的影響.從平權(quán)的規(guī)則網(wǎng)絡(luò)出發(fā)，通過改變權(quán)重的分布形式考察權(quán)重分布對網(wǎng)絡(luò)效率的影響.結(jié)果發(fā)現(xiàn)，權(quán)重異質(zhì)性增加提高了網(wǎng)絡(luò)效率，而邊界數(shù)高的邊更頻繁的被利用是效率提高的一個因素.同時權(quán)重隨機化之后，網(wǎng)絡(luò)最小生成樹的總權(quán)重減小，意味著網(wǎng)絡(luò)的運輸成本隨著權(quán)重異質(zhì)性增加而降低.以上結(jié)果對于深入理解權(quán)重對網(wǎng)絡(luò)結(jié)構(gòu)與功能的影響提供了基礎(chǔ).在研究中我們發(fā)現(xiàn)，在無標度網(wǎng)絡(luò)上，權(quán)重隨機化對于網(wǎng)絡(luò)效率的改善并不明顯，所以我們在本文中沒有展示無標度網(wǎng)絡(luò)上的模擬結(jié)果.其原因有可能是無標度網(wǎng)絡(luò)本身就是連接異質(zhì)性很強的網(wǎng)絡(luò)，而權(quán)重異質(zhì)性的效果就相應(yīng)減弱了.事實上，除了權(quán)重分布的改變外，在給定權(quán)重分布的條件下，調(diào)整邊權(quán)與邊的對應(yīng)關(guān)系也是改變網(wǎng)絡(luò)性質(zhì)的重要途徑，給定網(wǎng)絡(luò)的拓撲結(jié)構(gòu)和網(wǎng)絡(luò)功能，特別是在無標度網(wǎng)絡(luò)上尋找最優(yōu)的權(quán)重分布和邊權(quán)匹配關(guān)系，仍然是加權(quán)網(wǎng)絡(luò)研究的一個重要內(nèi)容.

［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，F(xiàn)u 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，F(xiàn)an Y，Chen J，Gao L，Di Z，Wu J 2005PhysicaA 350 643

［12］Zhang P，Li M，Wu J，Di Z，F(xiàn)an Y 2006PhysicaA 367 577

［13］Li D，Li M，Wu J，Di Z.，F(xiàn)an Y 2007Eur.Phys.J.B 57 423

［14］Li M，F(xiàn)an 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)資助的課題.

?通訊聯(lián)系人.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