田 柳 狄增如 姚 虹

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

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

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

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

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

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

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

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

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

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

加權(quán)網(wǎng)絡(luò)可以對(duì)復(fù)雜系統(tǒng)的相互作用結(jié)構(gòu)提供更加細(xì)致的刻畫(huà)，而改變邊權(quán)也成為調(diào)整和改善網(wǎng)絡(luò)性質(zhì)與功能的新途徑.基于已有無(wú)權(quán)網(wǎng)絡(luò)的效率概念，文中給出了相似權(quán)和相異權(quán)網(wǎng)絡(luò)的網(wǎng)絡(luò)效率定義，并研究了權(quán)重分布對(duì)于網(wǎng)絡(luò)效率的影響.從平權(quán)的規(guī)則網(wǎng)絡(luò)出發(fā)，通過(guò)改變權(quán)重的分布形式考察權(quán)重分布對(duì)網(wǎng)絡(luò)效率的影響，結(jié)果發(fā)現(xiàn)，在規(guī)則網(wǎng)絡(luò)上，權(quán)重分布隨機(jī)性的增加提高了網(wǎng)絡(luò)效率，而在幾種常見(jiàn)的權(quán)重分布形式中，指數(shù)分布對(duì)網(wǎng)絡(luò)效率的改進(jìn)最為顯著.同時(shí)，權(quán)重隨機(jī)化之后網(wǎng)絡(luò)最小生成樹(shù)的總權(quán)重減小，意味著網(wǎng)絡(luò)的運(yùn)輸成本隨著權(quán)重異質(zhì)性的增加而降低.以上結(jié)果為深入理解權(quán)重對(duì)網(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)的抽象，而僅僅由點(diǎn)和邊構(gòu)成的二元網(wǎng)絡(luò)是其中最簡(jiǎn)單的抽象，邊的存在與否給出了相互作用結(jié)構(gòu)的定性描述，是網(wǎng)絡(luò)刻畫(huà)中最本質(zhì)的部分.但在許多實(shí)際系統(tǒng)中，頂點(diǎn)之間相互作用的強(qiáng)度對(duì)系統(tǒng)性質(zhì)有重要的影響，此時(shí)我們就必須研究加權(quán)網(wǎng)絡(luò)的性質(zhì).這種研究是有意義的，因?yàn)閹в袡?quán)重的網(wǎng)絡(luò)，不管是相似權(quán)還是相異權(quán)，在現(xiàn)實(shí)世界中是普遍存在的，它能夠更真實(shí)客觀的抽象一個(gè)復(fù)雜系統(tǒng).同時(shí)，有了權(quán)重這個(gè)新的維度，就多了一種調(diào)整網(wǎng)絡(luò)結(jié)構(gòu)和功能的手段.研究表明，權(quán)重的分布會(huì)影響網(wǎng)絡(luò)的結(jié)構(gòu)和動(dòng)力學(xué)行為.權(quán)重重新分布可以縮小網(wǎng)絡(luò)的最短距離、增加集聚系數(shù)，使網(wǎng)絡(luò)表現(xiàn)出小世界效應(yīng)，并且能夠提高網(wǎng)絡(luò)的同步能力，影響網(wǎng)絡(luò)的集團(tuán)結(jié)構(gòu)［1，2］.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

考察發(fā)現(xiàn)，隨著權(quán)重隨機(jī)調(diào)整概率 P的變大，網(wǎng)絡(luò)的效率不斷提高，參見(jiàn)圖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)重重新隨機(jī) 分布的影響越高.

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

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

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

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

通過(guò)考察不同的權(quán)重分布對(duì)網(wǎng)絡(luò)的影響發(fā)現(xiàn):與平權(quán)的網(wǎng)絡(luò)相比，僅僅隨機(jī)調(diào)整網(wǎng)絡(luò)的權(quán)重分布就能顯著提高網(wǎng)絡(luò)的效率，由此除了改變網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)之外，又得到了一種新的手段和方法改變網(wǎng)絡(luò)的屬性，提高網(wǎng)絡(luò)的效率.相比改變網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)而言，調(diào)整權(quán)重是一種更為可行和實(shí)際的辦法，特別是在某些條件下，網(wǎng)絡(luò)的拓?fù)浣Y(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.最小生成樹(shù)和網(wǎng)絡(luò)的效率

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

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

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

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

4.結(jié) 論

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

［1］Li Y，Lü L，Luan L 2009Acta Phys.Sin.58 4463(in Chinese)［李 巖、呂 翎、欒 玲2009物理學(xué)報(bào) 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物理學(xué)報(bào) 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)［陳華良、劉忠信、陳增強(qiáng)、袁著祉 2009物理學(xué)報(bào)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

*國(guó)家自然科學(xué)基金(批準(zhǔn)號(hào):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