確定性復雜網絡的加權方式研究

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

關鍵詞：DCN模型;加權網絡;邊權;節點強度

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

一、確定性復雜網絡（DCN）模型

確定性復雜網絡的構造方法如下，通過n次循環疊代：

1.從n=0開始，即從一個單節點（網絡的主節點）出發。

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

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

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

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

二、賦權方式及點權分布

加權網絡可以用加權鄰接矩陣W=（wij）表示，其中i， j=1，2，…N，N為網絡的規模，即節點總數。

度是描述網絡局部特性的基本參數，網絡中任意一個節點i的度ki，指的是與該節點相連的其它節點的數目，也可以指與該節點連接的邊數。

度分布表示節點度的概率分布函數P（k），它指的是節點有k條邊連接的概率。反映了網絡的一個重要宏觀統計特征。

在加權網絡中， 節點強度或點權si：表示節點i的權重，定義為與節點i相連的所有邊的權重之和。

其表達式如下：

（1）

表示所有與節點i相連的節點的集合。

下面以DCN模型為例，采用三種賦權方式構建出加權DCN模型，并分析其點權分布特點。

1.邊權為常數

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

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

2. 邊權服從指數分布

假設在加權復雜網絡中邊的權重服從指數分布， 即， 其參數為>0，服從指數分布的樣本值均大于零，即， 它與實際網絡中邊權重均大于零的情形一致。

對于服從指數分布邊權重的加權網絡，節點i的強度分布可看作是ki個相同參數的指數分布的和分布的概率密度函數。

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

（2）

其中，，ki是節點i的度

由式（2）可以算得各參數下的加權DCN網絡節點強度分布，節點i的強度服從Gamma分布，s～Ga （ki， θ），因此不具備冪律特征。

3. 邊權服從節點度乘積函數

設節點i與節點j的度分別為ki和kj ，則連接這2個節點的邊權重滿足關系式：，a可有效地調節節點的強度大小。由DCN模型的規則性和層次感知同一層任意節點的點權相同，由點權定義式

，表示所有與節點i相連的節點的集合

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

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

（3）

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

（4）

第i層任意節點的度，i層節點總數，DCN網絡總節點數，因此，加權DCN網絡第i層的任意節點m的強度：

（5）

（6）

此時，加權DCN網絡的節點強度分布規律如圖1所示。

圖1 邊權為度乘積分布的確定性復雜加權網絡點權分布

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

圖1（b）是a=0.02時邊權服從度乘積分布的加權DCN網絡節點強度分布圖，由圖中四條曲線的分布可看出點權分布的冪律關系比圖1（a）更加明顯。

因此，對于邊權服從節點度乘積函數的加權DCN網絡，其節點強度分布整體上來看是服從冪律分布的，這與實際加權網絡是相符的。

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

可以得到點權與節點度是關聯的，且S（k）隨著k近似的以冪律形式增長。

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

三、結語

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

參考文獻：

[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-），女，漢族，籍貫：湖北武漢人，學歷：碩士，單位：武昌工學院信息工程學院，教師，研究方向：物理教育及復雜網絡。

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