聚類系數大小及分布可調的BBV網絡演化模型

孫雅倩，張達敏，曾　成，徐玉珠

(貴州大學 大數據與信息工程學院,貴州 貴陽 550025)

摘　要：在傳統BBV模型的基礎上，提出了一種改進的BBV網絡演化模型。基本思想是改變網絡增長過程中新節點加入時，新舊節點的連接方式及優先選擇概率。該模型不僅可以調節無標度加權網絡度和強度的分布，還可以通過改變“三角形”連接概率公式中系數的大小，增大網絡的聚類系數并調節網絡聚類系數的分布。即根據實際需要，大范圍調節網絡度分布，精確調節聚類系數大小及分布，其生成機制更符合實際網絡的演化過程。

關鍵詞：BBV演化模型;度分布;聚類系數

doi:10.3969/j.issn.1002-0802.2015.06.013

聚類系數大小及分布可調的BBV網絡演化模型

孫雅倩，張達敏，曾成，徐玉珠

(貴州大學 大數據與信息工程學院,貴州 貴陽 550025)

摘要：在傳統BBV模型的基礎上，提出了一種改進的BBV網絡演化模型。基本思想是改變網絡增長過程中新節點加入時，新舊節點的連接方式及優先選擇概率。該模型不僅可以調節無標度加權網絡度和強度的分布，還可以通過改變“三角形”連接概率公式中系數的大小，增大網絡的聚類系數并調節網絡聚類系數的分布。即根據實際需要，大范圍調節網絡度分布，精確調節聚類系數大小及分布，其生成機制更符合實際網絡的演化過程。

關鍵詞：BBV演化模型;度分布;聚類系數

doi:10.3969/j.issn.1002-0802.2015.06.013

收稿日期：2015-01-21；修回日期：2015-04-28Received date:2015-01-21；Revised date：2015-04-28

基金項目：貴州省省委組織部項目(TZJF-2011-37)；貴州省合作計劃項目([2012]7002號)；貴州大學研究生創新基金項目(研理工2015078)Foundation Item:Cooperative Project of Guizhou Province(TZJF-2011-37); Cooperative Project of Guizhou Privince([2012]7002);Graduate Student Innovation Foundation of Guizhou University

中圖分類號：TP393

文獻標志碼：碼：A

文章編號：號：1002-0802(2015)06-0692-07

Abstract：Based on the traditional BBV model, an improved BBV model is proposed. The main idea is to change the connecting way of between new nodes and old nodes and the probability of priority selection when a new node joins the network in the growth process. This model could adjust the distribution of degree and strength of the weighted scale-free network while increase clustering coefficient of the network and tune the distribution of clustering coefficient by changing the coefficient in “triangle”connection probability formula. To adjust the distribution of degree in a big way and accurately tune the clustering coefficient and its distribution in accordance with actual needs, this generation mechanism is more accordant with the actual network evolution.

作者簡介：

An Evolution Model of BBV Network with Tunable Clustering

Coefficient and Distribution

SUN Ya-qian,ZHANG Da-min,ZENG Cheng,XU Yu-zhu

(School of Big Data and Information Engineering of Guizhou University,Guiyang Guizhou 550025,China)

Key words：BBV evolution model; distribution of degree; clustering coefficient

0引言

隨著時代發展，復雜網絡研究正滲透到我們生活中的各個領域。對于實際生活中的網絡來說，每個節點和邊的重要性并不相同，為了描述邊的異質性，Yook等人提出了一個初步的加權網絡理論模型[1]，給網絡的邊賦上了權值。該模型是在無權網絡的基礎上首次對加權的網絡演化模型理論進行了研究。后來，Barrat,Barthelemy和Vespignani提出了著名的BBV模型[2]，該模型綜合考慮點強度與邊權值加強機制，BBV模型的動態演化利用權驅動方式得以實現[3-4]，該模型的提出掀起了加權網絡的研究熱潮。

隨著無標度加權網絡受到越來越多學者們的重視，一些改進的加權無標度網絡模型相繼被提出[5-10]。其中,很多學者圍繞著調節網絡度分布和聚類系數大小做深入研究，在度分布的調節上主要是在權重優先選擇概率公式中引入調節系數，在聚類系數的調節上以加入三角形連接方式為主[5,9,10]。本文借鑒在BBV網絡中加入三角形連接方式和在權重優先選擇概率公式中引入調節系數的思想，通過在新節點加入時引入一個由當前節點聚類系數和當前網絡平均聚類系數組成的概率公式來決定是否進行三角形連接，加入一個調節系數，改變系數大小可以調節網絡進行三角形連接的概率，并對網絡中每個節點的聚類系數大小進行控制，使聚類系數的分配相對靈活。

實際生活中的網絡種類繁多，不同網絡具有不同的統計特性。例如：電力網、國際航空網的度分布在雙對數坐標下較冪率分布更為均勻[11]，在線社會網，經濟網，科學合作網等具有較大的聚類系數[12]，而傳統BBV模型的度及強度嚴格服從冪率分布，且聚類系數較小。由此可見，我們改進的BBV網絡模型需具備更高的靈活性。本文共引入3個調節系數，通過對這3個系數的合理調節，可以模擬構造多種類型的實際網絡，具有高度靈活性。

1網絡演化模型

模型演化基礎：結合王丹等人提出的將三角形連接機制引入到BBV模型的方法以及潘灶烽、汪小帆提出的GBBV模型的生成方法，在網絡模型進行“三角形”演化的過程中，將當前網絡的平均聚類系數和當前節點的聚類系數綜合考慮進來，即根據當前網絡和當前節點的聚類系數大小來確定加入的新節點是進行三角形連接還是做權重優先選擇連接。

本文提出的網絡模型演化機理如下：

步驟1：設定初始網絡：初始網絡是一個由m0個節點組成，節點之間隨機連接一些邊的網絡。網絡中每條邊的權值均設為w0，因此每個節點的強度為:

(1)

步驟2：增長：每次引入一個新節點，與已經存在的m個節點相連，直至達到所設定的網絡節點數，即網絡規模N。

步驟3：擇優原則：網絡增長過程中，每引入一個新節點n后，以概率:

(2)

選擇一個舊節點i與新加入的節點n連接。si為當前節點i的強度，a是調節系數。a越小，每個舊節點被選中的概率就越接近，網絡的度分布也就越均勻。當a=1時，就退變成傳統BBV網絡中的強度優先選擇概率。

步驟4：執行步驟3后，再以概率:

(3)

三角形連接機制：如果按照步驟3選擇的下一步是三角形連接，則從舊節點i的鄰居節點中以概率 :

(4)

選擇一節點與新節點n相連。這里的選擇概率原則和步驟3的優先原則同出一轍，但此處的系數g對整個網絡度分布的影響力度比a小，主要作用是輔助f調節聚類系數。需要注意的是，若節點i沒有鄰居節點，則按照步驟3的原則增加下一條邊。

網絡賦權原則依舊按照BBV網絡的權重賦予原則進行，具體演化過程如下：

網絡中加入的新邊賦權值大小為w0,加入的新邊(n,i)會引起被連接的舊節點i與其鄰居節點j∈Γ(i)之間的邊權值發生變化。變化規則規定為：

wij→wj+Δwij

(5)

(6)

由于引入新邊(n,i)會給節點i增加流量負擔，跟節點i連接的其他邊，會根據自己的權值wij的大小來幫助節點i分擔流量。此時，節點i的強度調整為：

si→si+δ+wo

(7)

2仿真結果分析

在仿真實驗中，初始網絡大小m0=10，并取m=6,w0=2，網絡規模N=5 000。我們主要對網絡的強度分布，度分布，聚類系數的大小及分布進行討論。需要注意的是，在加權無標度網絡中，節點度分布及強度分布是兩個重要的統計特征。節點的強度反應了該節點的重要程度，傳輸能力等。度和強度的分布均能反映網絡模型的特性。聚類系數反映的是網絡節點的聚集性[12]，可以衡量網絡的集團化程度和連通性等等。

2.1傳統BBV網絡特性分析

用傳統BBV網絡的生成方式生成網絡模型，網絡節點的度分布，強度分布，度與強度的關系以及度-聚類系數關系如圖1所示。

(a)節點強度的分布圖

(b)度分布圖

(c)度-強度變化關系

(d)度-聚類系數相關圖

生成的網絡聚類系數為：0.064 253，從實驗數據我們可以看出，度與強度之間呈線性關系,傳統的BBV網絡聚類系數非常小，節點的強度以及度分布均是嚴格的冪率分布，且冪指數固定不變，這不僅不能完全反映真實網絡的特性，并且構造的網絡模型種類單一，靈活性較差。

2.2改進模型中各個系數對網絡特性的影響

在新節點與舊節點連接時的強度優先選擇概率公式中引入系數a,當a取不同值時對應的節點強度分布,度分布,度與強度的關系如圖2所示。

(a)節點強度的分布圖

(b)度分布圖

(c)度-強度變化關系

運行程序得出，a=0.2，a=1，a=3時網絡的聚類系數分別為0.002 613 8，0.079 82，0.999 17。圖2中的(c)圖表明，系數a的引入并未改變節點度與強度之間的關系，而大多數真實網絡度與強度正符合這種線性關系[1]。分析圖2(b)發現，a=0.2時，網絡節點的度接近指數分布，原因是網絡中每個舊節點被新節點連接的概率接近相等，這意味著網絡中的度分布比較平均，這點從圖2(c)可以看出。而a的值越大，強度大的舊節點被連接的概率就越大，大部分節點的度將變小，少數節點的度會很大。但a的值無論大小，網絡的強度分布都服從冪率分布，改變的只是分布指數。而對于度分布來說，當a的值越來越小時，其度分布會逐漸趨于擴展指數分布，該實驗結果符合前人研究所得的結論。需要注意的是，a=0.5是度分布從擴展指數分布過度到冪率分布的分界值[11]。

上述實驗發現，引入參數a后，僅僅對調節節點的度及強度分布有意義，卻無法準確調節網絡的聚類系數，一些研究人員通過三角形連接的方式來增大網絡的聚類系數，并得到較為滿意的結論。但傳統的三角形連接方式，雖然可以調節聚類系數大小，卻沒有考慮到當前節點和當前網絡的聚類系數大小關系，從而無法精確調節聚類系數的分布。本文提出的網絡模型生成方法中，當網絡中加入新節點時，先根據強度優先概率選出一個舊節點與之連接，之后根據當前舊節點的聚類系數和整個網絡的聚類系數大小情況以一定概率進行三角形連接，此概率公式中引入了一個系數f. 在進行三角形連接時，當前節點將從自己的鄰居節點中以概率k=s(j)g/sum(s(j)g)選擇一個自己的鄰居節點與新節點相連。此處，先討論改變系數f對網絡度分布、強度分布、聚類系數大小的影響，實驗結果如圖3所示。

(a)節點強度的分布圖

(b)度分布圖

圖3是在系數a=1，g=1時，探究系數f對網絡基本特性的影響。運行程序后得到，當f=0.2,f=1,f=3時對應的聚類系數大小分別為0.290 44,0.456 65,0.564 4。聚類系數比同等規模下的傳統無標度網絡高出數倍。從圖3可以看出，系數f無論怎么變化網絡節點的度及強度分布依舊服從冪率分布，也就是說系數f的大小對度和強度的分布影響不大。

系數g的作用是，當a的值不變時，可以微調度分布，且對聚類系數大小也有影響，a,g,f這3個系數合作可以大范圍精確的調節網絡的度分布，聚類系數大小和和聚類系數大小分布。

(a)節點強度的分布圖

(b)度分布圖

運行程序后得到，g=0.1,g=1和g=3時對應的聚類系數大小分別是，0.203 83,0.467 71,0.221 57。從實驗結果可以看出，g的取值無論大小，網絡的度分布及強度分布均服從冪率分布，當a和f的值為1時，g的值增大或減小都會使得聚類系數減小，而且波動范圍較大。當a和f的值固定時，調節g的值可以改變聚類系數，因此，如果想得到聚類系數大小和度分布可以任意調整的網絡模型，只要協調好a,f,g這3個系數的大小即可。

以上實驗結果是驗證各系數對整個網絡強度分布，度分布及聚類系數大小的調節。接下來討論引入系數f對聚類系數分布的影響。圖5是在系數a=0.5,g=0的前提下實驗得出的結果。

圖5　引入系數f對網絡聚類系數分布的影響

圖5中顯示的實驗結果表明，在系數a和g的值固定不變的情況下，系數f取不同值會得到不同的網絡聚類系數分布。當系數f取值較小時，三角形連接概率會很小。因此，網絡中各個節點的聚類系數都較小，大多分布在0.01左右，且a=0.5時網絡度分布較均勻，聚類系數分布也就相對均勻。調節f的值，此處取f=1,可以增大網絡的聚類系數，還可以使聚類系數和度的相關圖整體趨勢近似于冪率分布?？梢?，調節系數f可以有效控制網絡聚類系數的大小和聚類系數的分布。

2.3改進模型實用性研究及系數選擇原則

圖6是給系數a,f,g賦上不同值時得到的相應特性圖，不同特性可以描述不同類型的網絡，從而說明此模型生成方法的靈活性和實用性。

(a)節點強度的分布圖

(b)度分布圖

(c)度-聚類系數相關圖

這三組數據從上到下所對應的聚類系數大小分別是：0.714 6、0.138 34、0.421 87。從圖中可以看出，這幾組數據得到的度分布以及強度分布均符合冪率分布特性，不同之處主要在于網絡聚類系數大小及聚類系數與度的關系分布。分析發現，a=0.5,f=5,g=3和a=1,f=3,g=1這兩組系數所生成網絡的度和聚類系數相關圖具有平頭特征，而多種真實網絡都具有這一特征[13-14]。前者可以描述校園人際關系網等網絡。該類網絡特點是：強度分布和度分布服從冪率分布特征，冪指數較大，整個網絡的平均聚類系數很大且聚類系數和度的相關性會具有“平頭”特征[9]，大多數節點的聚類系數聚集在某一范圍內，這是因為同學之間大多互相認識，尤其是人際關系圈子較小的同學，其認識的人互相認識的可能性更大。后者適合描述類似于Internet網絡中自治層等類型的真實網絡[9]。a=0.5,f=1,g=0時所對應的聚類系數與度的相關圖近似服從冪率分布，此時的模型適合描述集群現象比較突出的網絡。

真實網絡都擁有自身的結構特點，而傳統BBV網絡僅限于描述度、強度和聚類系數均服從冪率分布的網絡，卻無法描述圖2和圖6中顯示的度分布均勻和聚類系數分布具有“平頭”特征的網絡。可見，改進的演化模型可通過調節這三個系數的大小，適應更多網絡類型。

結合2.2節的仿真結果，規定系數選擇原則如下：

當a=1，f=0時，該模型就變為傳統BBV模型，此時用于描述度分布，聚類系數分布均服從冪率特性且聚類系數較小的網絡。當a<0.5,f>1,g>0時，該模型適于描述度分布較均勻，聚類系數較大且分布具有“平頭”特征的網絡，使a>0.5，f和g的取值范圍不變，則網絡的聚類系數特性依舊不變，網絡度分布服從冪率特性，若要想聚類系數分布也服從冪率特性特性可使g=0。

3結語

本文僅把網絡的度分布，強度分布及聚類系數幾個復雜網絡的基本特性作為出發點，但實際中的網絡更為復雜，且需要考慮多方面因素，生成模型方法還需要進一步完善。此外，本文或許存在不妥之處，還望各位專家和學者們批評指正。

參考文獻：

[1]Yook S H，Jeong H，Barabási A L. Weighted Evolving Networks[J]. Physical Review Letters，2001，86(25):5835-5838.

[2]Barabási A L，Barthelemy M，Vespignani A. Weighted Evolving Networks:Coupling Topology and Weight Dynamics[J]. Physical Review Letters，2004，92(22):228701.

[3]楊珉，張家玥，張達敏. 復雜網絡拓撲結構的網絡模型研究綜述[J].通信技術，2014,47(12):1354-1359.

YANG Min, ZHANG Jia-yue, ZHANG Da-min. Review of Complex Networks Topology Structure and Network Models Research[J]. Communications Technology, 2014,47(12):1354-1359.

[4]王翠君,王紅. 復雜網絡的研究進展綜述[J].計算機與信息技術,2007(31):417-418.

WANG Cui-jun, WANG Hong. Research Progress Outline of the Complex Network .[J]. Science & Technology Information, 2007(31):417-418.

[5]潘灶烽，汪小帆.一種可大范圍調節聚類系數的加權無標度網絡模型[J].物理學報,2006,55(08):4058-4064.

PAN Zao-feng, WANG Xiao-fan. A Weighted Scale-free Network Model with Large-Scale Tunable Clustering.[J]. ACTA Phys Sin,2006,55 (08): 4058-4064.

[6]ZHOU Jian,LI Shi-wei,CHENG Ke-qin.BBV Weighted Network Evolving Model Reseach based on Local World[J]. Computer Engineering and Applications,2011,47(14),95-98.

[7]李穩國,鄧曙光,崔治等.可調路徑長度和簇系數的加權無標度網絡模型研究[J].湖南城市學院學報: 自然科學版,2011,20(02):60-62.

LI Wen-guo, DENG Shu-guang, CUI Zhi,et al . Growing Weighted Scale-Free Network with Tunable Length and Clustering Coefficient[J]. Journal ofHunan City University，2011,20(02):60-62.

[8]逯鵬,張姍姍,高慶一.基于共同鄰居的點權有限BBV模型研究[J].計算機科學，2014,41(04):49-52.

LU Peng, ZHANG Shan-shan, GAO Qing-yi.Research on BBV Mode with Limited Node Strength based on Common Neighbors[J].Computer Science,2014,41(04):49-52.

[9]王丹,金小崢.可調聚類系數加權無標度網絡建模及其擁塞問題研究[J].物理學報，2012，61(22)：228901.

WANG Dan, JING Xiao-zheng .On Weightd Scale-Free Network Model with Tunable Clustering and Congestion[J]. Acta Phys Sin，2012，61(22)：228901.

[10]劉慧，李增揚，陸君安.局域演化的加權網絡模型[J].復雜系統與復雜性科學，2006,3(01)：36-43.

LIU Hui, LI Zeng-Yang, LU Jun-an.Weighted Scale-Free Network Model with Evolving Local-World[J].Complex Systems and Complexity Science,2006,3(01):36-43.

[11]彭俊，李智，孫雨.一種改進的無標度網絡演化模型[J]. 計算機應用，2008,02(01)：40-50.

PENG Jun，LI Zhi ,Sun Yu. An Improved Scale-free Network Evolution Model [J].Jounarl of Computer Applications, 2008,02(01)：40-50.

[12]胡海波, 王科, 徐玲等. 基于復雜網絡理論的在線社會網絡分析[J]. 復雜系統與復雜性科學, 2008, 05(02): 1-14.

HU Hai-bo , WANG Ke,XU Ling，et al.Analysis of Online Social Networks based on Complex Network Theory[J].Complex Systems and Complexity Science,2008,05(02):1-14.

[13]AlbertRéka，Jeong Hawoong，Barabási Albert-László. Internet: Diameter of the World-Wide Web[J].Natuure,1999,401(6749):130-131.

[14]Ravasz Erzsébet, Barabási Albert-László.Hierarchical Organization in Complex Networks [J]. Physical Review E, 2003,67(02):026112.

孫雅倩(1990—)，女，碩士研究生，主要研究方向為復雜網絡；

張達敏(1967—)，男，教授，主要研究方向為計算機應用技術、網絡擁塞控制、病毒傳播機制;

曾成(1989—)，男，碩士研究生，主要研究方向為復雜網絡；

徐玉珠(1992—)，女，碩士研究生，主要研究方向為復雜網絡。

術語百科Technical Terms

計算智能

計算智能(CI，Computational Intelligence)是受到大自然智慧和人類智慧的啟發而設計出的一類算法的統稱。典型的計算智能算法有神經計算中的人工神經網絡算法，模糊計算中的模糊邏輯，進化計算中的遺傳算法、蟻群優化算法、粒子群優化算法、螢火蟲群優化算法，以及單點搜索優化中的模擬退火算法等。作為人工智能的一個重要領域，計算智能因其智能性、并行性和健壯性，具備了很好的自適應能力和很強的全局搜索能力。在科學研究和工程實踐中，對于遇到的一些NP(Non-deterministic Polynomial)難問題，計算智能算法可以在求解時間和求解精度上取得平衡。這些算法或模仿生物界的進化過程，或模仿生物的生理構造和身體機能，或模仿動物的群體行為，或模仿人類的思維、語言和記憶過程的特性，或模仿自然界的物理現象，通過模擬大自然和人類的智慧實現對問題的優化求解，在可接受的時間內求解出可以接受的解。 目前，計算智能已經在算法理論和算法性能方面取得了很多突破性的進展，并且已經在通信網絡、優化計算、模式識別、圖像處理、自動控制、經濟管理、生物醫學等許多領域取得了成功的應用。