確定性復雜網(wǎng)絡(luò)的加權(quán)方式研究

摘 要：現(xiàn)實世界中很多網(wǎng)絡(luò)都是各個連接間具有不同權(quán)值的加權(quán)網(wǎng)絡(luò)，故找到較好的網(wǎng)絡(luò)加權(quán)方式尤為重要。本文針對陳牧提出的確定性復雜網(wǎng)絡(luò)模型（DCN），采用三種邊權(quán)重賦予方式分別給DCN模型的邊賦值，導出加權(quán)DCN模型的節(jié)點強度公式，計算分析點權(quán)分布規(guī)律，得到普遍賦邊權(quán)方式---邊權(quán)服從節(jié)點度乘積函數(shù)，對實際網(wǎng)絡(luò)的模擬效果較好。

關(guān)鍵詞：DCN模型;加權(quán)網(wǎng)絡(luò);邊權(quán);節(jié)點強度

近年來，復雜網(wǎng)絡(luò)的研究正處于蓬勃發(fā)展的階段。網(wǎng)絡(luò)的性能和結(jié)構(gòu)在不斷的完善，但與現(xiàn)實的網(wǎng)絡(luò)相比，它的構(gòu)造方法和具體表達式顯得過于簡單，沒有考慮網(wǎng)絡(luò)中各條邊的權(quán)重以及有向性問題。為了解決以上模型的不足，陳牧在2007年構(gòu)造了一種同時擁有小世界效應(yīng)和無標度特性的確定性復雜網(wǎng)絡(luò)模型（DCN）能更好的模擬現(xiàn)實網(wǎng)絡(luò)。為了讓DCN網(wǎng)絡(luò)能夠很好的應(yīng)用到實際中去，加權(quán)不失為一種有效的方法。因此，本文采用三種邊權(quán)重賦予方式分別給DCN模型的邊賦值，研究其點權(quán)分布規(guī)律。

一、確定性復雜網(wǎng)絡(luò)（DCN）模型

確定性復雜網(wǎng)絡(luò)的構(gòu)造方法如下，通過n次循環(huán)疊代：

1.從n=0開始，即從一個單節(jié)點（網(wǎng)絡(luò)的主節(jié)點）出發(fā)。

2.當n=1時，在主節(jié)點下方對稱增加兩個葉節(jié)點，并使兩葉節(jié)點與主節(jié)點相連。

3.當n=2時，依上述方法，在前面兩葉節(jié)點的下方分別再對稱增加兩個新節(jié)點，新生成的四個節(jié)點都與他們的根節(jié)點相連。因此，當n=3時，就生成了4*2=8個新節(jié)點。

當進行到n步時，就生成了2n個新節(jié)點，每個節(jié)點與它的n個根節(jié)點相連接，包括一個主根和n-1個次根。依此方法不斷的生長下去，就得到了一個確定性的復雜網(wǎng)絡(luò)（Deterministic Complex Networks），簡稱DCN。

現(xiàn)實網(wǎng)絡(luò)往往展現(xiàn)出較小的平均最短距離和大的聚類系數(shù)，且度分布滿足冪律分布，而這些特點DCN模型都具備，因此DCN模型較之其他網(wǎng)絡(luò)模型能更好的模擬現(xiàn)實網(wǎng)絡(luò)。

二、賦權(quán)方式及點權(quán)分布

加權(quán)網(wǎng)絡(luò)可以用加權(quán)鄰接矩陣W=（wij）表示，其中i， j=1，2，…N，N為網(wǎng)絡(luò)的規(guī)模，即節(jié)點總數(shù)。

度是描述網(wǎng)絡(luò)局部特性的基本參數(shù)，網(wǎng)絡(luò)中任意一個節(jié)點i的度ki，指的是與該節(jié)點相連的其它節(jié)點的數(shù)目，也可以指與該節(jié)點連接的邊數(shù)。

度分布表示節(jié)點度的概率分布函數(shù)P（k），它指的是節(jié)點有k條邊連接的概率。反映了網(wǎng)絡(luò)的一個重要宏觀統(tǒng)計特征。

在加權(quán)網(wǎng)絡(luò)中， 節(jié)點強度或點權(quán)si：表示節(jié)點i的權(quán)重，定義為與節(jié)點i相連的所有邊的權(quán)重之和。

其表達式如下：

（1）

表示所有與節(jié)點i相連的節(jié)點的集合。

下面以DCN模型為例，采用三種賦權(quán)方式構(gòu)建出加權(quán)DCN模型，并分析其點權(quán)分布特點。

1.邊權(quán)為常數(shù)

我們定義n=5的DCN模型中具有從屬關(guān)系的節(jié)點間邊權(quán)重為1，隔一代的節(jié)點間邊權(quán)重為2，隔兩代的節(jié)點間邊權(quán)重為3，隔三代的節(jié)點間邊權(quán)重為4，隔四代的節(jié)點間邊權(quán)重為5。

由點權(quán)的定義式可以算得各層的節(jié)點強度。結(jié)果顯示，n=5的加權(quán)DCN網(wǎng)絡(luò)的每一個節(jié)點的點權(quán)都比較大，且隨著層數(shù)的增加而遞減，主節(jié)點強度最大，也就是說DCN網(wǎng)絡(luò)中的每一個節(jié)點都比較重要且主節(jié)點起著舉足輕重的作用。因此從整體上來看邊權(quán)為常數(shù)的加權(quán)DCN網(wǎng)絡(luò)的點權(quán)是符合冪律分布的，這與實際的加權(quán)網(wǎng)絡(luò)點權(quán)呈冪律分布符合得較好，因此確定性加權(quán)復雜網(wǎng)絡(luò)能更加生動的描述實際網(wǎng)絡(luò)。

2. 邊權(quán)服從指數(shù)分布

假設(shè)在加權(quán)復雜網(wǎng)絡(luò)中邊的權(quán)重服從指數(shù)分布， 即， 其參數(shù)為>0，服從指數(shù)分布的樣本值均大于零，即， 它與實際網(wǎng)絡(luò)中邊權(quán)重均大于零的情形一致。

對于服從指數(shù)分布邊權(quán)重的加權(quán)網(wǎng)絡(luò)，節(jié)點i的強度分布可看作是ki個相同參數(shù)的指數(shù)分布的和分布的概率密度函數(shù)。

ki個相同參數(shù)的指數(shù)分布的和分布的概率密度函數(shù)為

（2）

其中，，ki是節(jié)點i的度

由式（2）可以算得各參數(shù)下的加權(quán)DCN網(wǎng)絡(luò)節(jié)點強度分布，節(jié)點i的強度服從Gamma分布，s～Ga （ki， θ），因此不具備冪律特征。

3. 邊權(quán)服從節(jié)點度乘積函數(shù)

設(shè)節(jié)點i與節(jié)點j的度分別為ki和kj ，則連接這2個節(jié)點的邊權(quán)重滿足關(guān)系式：，a可有效地調(diào)節(jié)節(jié)點的強度大小。由DCN模型的規(guī)則性和層次感知同一層任意節(jié)點的點權(quán)相同，由點權(quán)定義式

，表示所有與節(jié)點i相連的節(jié)點的集合

我們考慮第i層的某個節(jié)點m，計算m節(jié)點的強度si，即將所有與節(jié)點m相連的邊的權(quán)重求和，分兩部分：

1）節(jié)點m與1層到i-1層直系親屬節(jié)點是直接相連的：

（3）

2）節(jié)點m以下i+1層到n+1層所有直接子親屬節(jié)點與m是直接相連的：

（4）

第i層任意節(jié)點的度，i層節(jié)點總數(shù)，DCN網(wǎng)絡(luò)總節(jié)點數(shù)，因此，加權(quán)DCN網(wǎng)絡(luò)第i層的任意節(jié)點m的強度：

（5）

（6）

此時，加權(quán)DCN網(wǎng)絡(luò)的節(jié)點強度分布規(guī)律如圖1所示。

圖1 邊權(quán)為度乘積分布的確定性復雜加權(quán)網(wǎng)絡(luò)點權(quán)分布

圖1（a）是a=0.5時邊權(quán)服從度乘積分布的加權(quán)DCN網(wǎng)絡(luò)節(jié)點強度分布圖。從圖中可以看出在雙對數(shù)坐標軸下四條點權(quán)分布曲線當呈明顯的線性關(guān)系，亦即與s冪律分布的關(guān)系符合得非常好。

圖1（b）是a=0.02時邊權(quán)服從度乘積分布的加權(quán)DCN網(wǎng)絡(luò)節(jié)點強度分布圖，由圖中四條曲線的分布可看出點權(quán)分布的冪律關(guān)系比圖1（a）更加明顯。

因此，對于邊權(quán)服從節(jié)點度乘積函數(shù)的加權(quán)DCN網(wǎng)絡(luò)，其節(jié)點強度分布整體上來看是服從冪律分布的，這與實際加權(quán)網(wǎng)絡(luò)是相符的。

前面提到按照節(jié)點度乘積的方式給DCN網(wǎng)絡(luò)賦值時，邊權(quán)公式中的參數(shù)a可根據(jù)實際情況取不同的值，從而達到有效調(diào)節(jié)節(jié)點強度大小的目的。我們從邊權(quán)服從節(jié)點度乘積函數(shù)的加權(quán)DCN網(wǎng)絡(luò)在不同a下的點權(quán)分布規(guī)律中可以看到其點權(quán)分布在一定范圍內(nèi)均服從冪律分布，a越小，冪律關(guān)系越明顯;而且當a逐漸變大時該加權(quán)DCN網(wǎng)絡(luò)的節(jié)點強度亦迅速增長，從而可以根據(jù)實際加權(quán)網(wǎng)絡(luò)的要求設(shè)定合適的a值來進行模擬。

可以得到點權(quán)與節(jié)點度是關(guān)聯(lián)的，且S（k）隨著k近似的以冪律形式增長。

因此，我們按節(jié)點度乘積方式給DCN網(wǎng)絡(luò)的邊賦值后，獲得了確定性加權(quán)復雜網(wǎng)絡(luò)的一些特點：（1）節(jié)點強度是服從冪律分布的，且隨著參數(shù)a的減小，冪律特征越明顯;（2）對于給定規(guī)模的加權(quán)DCN網(wǎng)絡(luò)，當a逐漸變大時節(jié)點強度迅速增長，從而能夠設(shè)置不同的參數(shù)用于模擬不同的實際加權(quán)網(wǎng)絡(luò)，很方便、靈活;（3）點權(quán)與節(jié)點度是關(guān)聯(lián)的，且S（k）隨著k以冪律形式增長，a越小冪律關(guān)系越明顯，從而可根據(jù)實際加權(quán)網(wǎng)絡(luò)的要求設(shè)置不同的a值，有效調(diào)節(jié)網(wǎng)絡(luò)節(jié)點強度的大小以適合于實際網(wǎng)絡(luò)。

三、結(jié)語

本文研究了三種邊權(quán)重賦予方式下加權(quán)DCN模型的點權(quán)分布規(guī)律。我們發(fā)現(xiàn)當邊權(quán)服從指數(shù)分布時，加權(quán)DCN網(wǎng)絡(luò)的節(jié)點強度是服從Gamma分布的，不具備冪律特征;而當邊權(quán)為常數(shù)或者服從節(jié)點度乘積函數(shù)時，加權(quán)DCN網(wǎng)絡(luò)的點權(quán)分布均滿足冪律關(guān)系，這與真實世界的網(wǎng)絡(luò)符合得較好。另外，從我們研究加權(quán)DCN網(wǎng)絡(luò)的結(jié)果可以看出，三種邊權(quán)賦予方式中，邊權(quán)服從節(jié)點度乘積方式最貼合實際的需要，不僅點權(quán)分布P（s）是冪律關(guān)系的，而且點權(quán)與節(jié)點度之間也滿足冪律關(guān)系，最值得稱贊的是該方式中有一個可以根據(jù)實際需要有效調(diào)節(jié)點權(quán)大小的參數(shù)a，通過改變a的值就能讓你的網(wǎng)絡(luò)更加接近實際網(wǎng)絡(luò)，從而達到很好的模擬效果。因此，在分析加權(quán)DCN網(wǎng)絡(luò)的其它特征量時均可采用該方式賦邊權(quán)重。

參考文獻：

[1] Watts D.J.， Strogatz S.H.. Collective dynamics of small-world networks. Nature， 1998， 393（6684）： 440-442.

[2] Barabási A.L.， Albert R.. Emergence of scaling in random networks. Science， 1999， 286（5439）： 509-512.

作者簡介：魯芬（1982-），女，漢族，籍貫：湖北武漢人，學歷：碩士，單位：武昌工學院信息工程學院，教師，研究方向：物理教育及復雜網(wǎng)絡(luò)。

備注：*武漢工業(yè)學院工商學院校級科研課題（編號：2010KY04）