改進無標度網絡模型研究

孫立晟，何東之

（北京工業大學 嵌入式軟件與系統研究所，北京　100022）

改進無標度網絡模型研究

孫立晟，何東之

（北京工業大學 嵌入式軟件與系統研究所，北京100022）

基于復雜網絡理論知識研究了無標度網絡的構造算法，并在原有的BA無標度網絡模型的基礎上，通過加入內部邊和重連邊機制使該網絡模型不但具有無標度特性而且具有現實社會網絡的小世界特性，同時給網絡的節點加入初始引力，得出了一種改進的無標度網絡模型。最后，不僅從理論上通過平均場方法驗證了改進模型，而且通過數據仿真驗證該模型。

復雜網絡；無標度網絡；改進無標度網絡；平均場方法

現在越來越多的研究者通過復雜網絡［1］中的小世界網絡［2］模型或無標度網絡［3］模型來研究社會網路，而社會網絡同時具有小世界特性和無標度特性。但是這兩個模型都不能同時體現這兩個網絡特性。因此，本文基于無標度網絡模型的基礎上，通過加入內部邊和重連邊機制，給無標度網絡模型賦予小世界特性。

1　復雜網絡基本屬性

度（Degree）：度指的是網絡中與某個節點直接相連的邊的數量。在有向復雜網絡中，節點的度可以被定義成入度和出度。入度是指所有作為直接連接邊的終點的數量。出度是指所有作為直接連接邊的起點的數量。網絡的平均度被定為網絡中所有節點度的平均值。

其中N代表網絡中節點的總數，E代表網絡中邊的總數。一般情況下網絡的平均度決著網絡的穩定性。

度分布（Degree distribution）：直接與某點相連的邊的數量叫做這個節點的度。設P（k）表示在復雜網絡中隨機取某節點度數是k的概率，則概率分布列｛P（k）｝被叫做網絡度分布。度分布是一個定義容易但又十分重要的數學統計特征量。

平均路徑長度（Average path length）：網絡的平均路徑長度也叫做網絡的平均最短路徑長度或網絡的特征路徑長度。平均路徑長度dij定義為網絡上連接節點i和節點j之間最短路徑上的邊數。

集群系數（Clustering coefficient）：網絡中描述節點間集結成團程度的系數叫做集群系數。如果網絡上的一個節點i與ki個節點相連，則這ki個節點叫做節點i的鄰節點。顯然，在這ki個鄰節點之間最多可能有ki（ki-1）/2條直接連接的邊，如果這ki個鄰節點間實際存在的邊數為Ei，則實際存在的邊數Ei與所有可能存在的邊數ki（ki-1）/2的比值叫做節點i的聚類系數。

度分布、平均路徑長度和集群系數是復雜網絡中最重要的3個特征量，影響著復雜網絡的拓撲結構。度分布能夠表示網絡的連通性，平均路徑長度決定著網絡上的信息傳播速度，集群系數最早出現于社會網絡的小集團特征。

2　無標度網絡模型

在復雜網絡研究中的一大發現就是許多復雜網絡包括社會網絡在內的網絡的度分布都是冪律分布。由于這些網絡中節點的度沒有明顯的特征長度，因此把這些網絡叫做無標度網絡。為了解釋度分布是冪律分布的生成機理，1999年Barabási and Albert在《Science》上發表了開創性文章，提出了無標度網絡（Scale-free networks）［7］的概念和模型。該模型具有增長（Growth）和擇優連接（Preferential attachment）網絡生成機理，并且在網絡生成過程中起著決定性作用。經過許多研究者的研究與驗證，證實現實網絡的冪律度分布特性是由這兩個因素造成的。一方面，一般情況下現實網絡的規模都是可以改變的。例如：一個公司新入職一批員工，因此該公司的人際交互網絡的規模會變大。另一方面，具有擇優連接特性。例如：新入職的員工由于每個人的性格不同，有的人外向，有的人內向，所以外向的人會更快認識公司里的人，在網絡中體現為有更多的節點和這個節點相連。于是，基于增長和擇優連接兩個演化機制，Barabási and Albert原創性地提出著名的BA標準無標度模型，網絡模型生成算法如下：

Step1：增長：模型中初始一定數量節點（m0個），每個時間間隔后，增加一個新的節點，并將這個新節點連接到m（≤m0）個已經在模型中的節點上。

Step2：擇優連接：在新節點選擇舊節點連接時，令新節點連接舊節點i的概率與舊節點i的度數ki與節點度數總和成正比。經過t時間步后，生成一個具有N=m0+t個節點和mt條邊的BA標準無標度網絡模型。規定：1≤m≤m0。

3　改進的無標度網絡模型

3.1度分布定義

為了對無標度網絡演化模型進行理論分析，首先介紹網絡的度分布定義。由于復雜網絡是動態的演化網絡，并且在網絡的演化過程中存在局部相互作用，所以很難用隨機圖的方法定義網絡的度分布。除了在實證研究和模擬方法中采用的統計方法外，研究者常用的度分布定義有3種［4-6］。根據本文研究內容，以下只介紹其中一種度分布定義。

定義：在t時刻從網絡中任意選擇一個節點，假設P（k，t）表示它的度數為k的概率，則｛P（k，t），k=0，1，2，…｝被叫做在t時刻網絡的度分布。如果極限

則該網絡具有穩定的度分布｛P（k），k=0，1，2，…｝。

3.2演化模型

由于現實社會關系網絡中不僅存在無標度特性，還存在小世界特性，即集聚系數大、平均路徑小的特點。但是在BA無標度網絡模型中，當規模N很大時，集聚系數非常小，而平均路徑卻很大。因而考慮到實際社會關系網絡中的小世界特點，在構造改進的無標度網絡模型時加入內部邊這一機制，從而使所構建的無標度網絡模型具有現實社會中小世界特性。社會關系網中人與人之間的關系都是動態改變的，人與人之間的聯系可能會發生改變，比如，此時個體A和個體B有關系，但下一時刻可能就是個體A和個體B沒有關系，但個體A和個體C有關系，所以根據這一情況在構建模型時加入了刪除連接邊與添加連接邊的機制。在人與人之間建立聯系，每個人都會有選擇的去先接觸對他吸引力更大的人，因而本文在模型中給每個節點加入了初始吸引力機制，同時解決了原有模型中初始加入節點與原有節點隨機連接的問題。

因而在BA無標度模型的基礎上，增加了初始吸引力、增加內部邊、重新連接邊機制來實現現實網絡中人與人之間的關系。改進的模型構造算法：

Step1：初始化m0個孤立節點構成網絡模型，并給每個節點賦予初始吸引力α，所有節點初始吸引力α≥0。

其中kj是節點j的度數，生成了一條內部邊。

Step3：重復Step2，模型中已添加l條這樣的連線。

Step4：在模型中添加一個新的節點，并且該節點與模型中原有的m（≤m0）個節點相連，以Step2的擇優概率選擇模型中原有節點，最終新節點連接到模型中原有的m個不同的節點上。

Step5：在模型重新連接一條已經存在的邊，首先任意選擇一個節點i，然后任意選擇一條與之連接的連邊lij，最后以擇優概率Π（ki′，α）選擇另一個節點i′（i′！=i）與節點j相連接，并用新邊線li′j取代已有邊lij。

Step6：重復Step5過程，直到模型中已經重新連接了n條邊。

模型參數滿足條件：l，m，n；α≥0，1+m＞0。

依次執行 Step1，Step2，Step3，Step4，Step5，Step6步驟 t次，該模型演化成為一個具有總點數為N（t）=m0+t和總邊數為（l+m）t的網絡模型。

從改進的無標度網絡生成過程來看，其演化的過程都是合理的，在每次循環過程中都有新節點和新邊的生成。

下面我們采用平均場方法計算改進的無標度網絡的度分布，以證明該網絡的的度分布滿足標準無標度網絡度分布冪律分布的特點。

依據平均場方法，在模型中任意選擇一個節點i，假設它的度數ki（t）是連續變化，驗證ki（t）的變化率。下面分3部分討論ki（t）的演化過程。

1）在模型已有節點中加入l條新邊，則

其中等號右邊的第一項是對應于新加入邊任意選擇的一個端點是節點i的情況，第二項是對應于新加入邊擇優選擇另一個端點是節點i的情況，它們兩項共同導致節點i的度數增加。

2）在模型中加入一個節點，并且該節點與原有節點中的m個相連，則

其中等號右邊表示模型中已經存在的節點i由于被新節點連接而導致節點i的度數ki增加。

3）在模型中重新連接n條已經存在的邊，則

其中重新連接邊的過程中首先選擇一條邊的一個端點，它會被一個新的端點替代，等號右邊的第一項就對應于這個被替代的節點i，因而節點i的度數ki會減少，第二項對應于節點i是新節點替代舊點過程中新節點的情況，它會導致節點i的度數ki增加。

當節點i在第ti次循環時進入模型，則模型中節點i的度數初始為ki（ti）=m。則方程的解為：將3種情況一起考慮，得出的動力學方程：

網絡模型度的概率分布為：

假設在相同的時間間隔將新的節點加入到模型中，所以各個節點加入模型的時間都是隨機的。它進入網絡模型的循環次數ti服從區間［0，t］上的均勻分布，

當t次循環生成網絡模型過程中度分布為：

因此，指數γ∈（2，3）。

這個極限分布是該網絡的度分布，其中γ叫做度指數，γ∈（2，3）。

所以此網絡模型符合無標度網絡特性，是一個穩定網絡模型。

4　數據仿真

為證實上述算法可以生成無標度網絡模型，設定初始參數進行數據仿真。由于算法受時間限制，令網絡模型中初始網絡節點個數m0=3，增加內部邊數l=3，初始吸引力α=0.2，引入新節點時新生成的邊數m=3，重新連接已有邊數n=3，圖1和圖2分別是網絡演化過程中度大小概率分布圖。

圖1　規模為2000改進的網絡度分布概率

圖2　規模為3000改進的網絡度分布概率

由圖1、圖2改進的網絡模型的不同規模的節點度分布概率圖可知，模型中節點度的概率分布呈遞減趨勢，并且發現度數為5的節點分布概率最大，度數在5到10之間節點分布概率逐漸減少，度數大于10的節點分布概率很小，概率值基本相同。

通過實驗結果分析可知，改進的網絡模型的度分布曲線圖整體上滿足冪律分布，符合無標度網絡特性，所以是改進的網絡模型是一個無標度網絡模型。

5　結論

本文在原有無標度網絡模型的基礎上，加入內部邊和重連邊機制，使改進的無標度網絡同時具有了小世界特性，為今后研究者通過網絡模型更準確地仿真社會網絡提供了基礎，達到最初的研究目的。

［1］Chen P Y，Chen K C.Information epidemics in complex networks with opportunistic links and dynamic topology［C］// GlobalTelecommunicationsConference（GLOBECOM 2010），2010 IEEE.IEEE，2010：1-6.

［2］Watts D J，Strogatz S H.Collective dynamics of‘smallworld'networks［J］.Nature，1998，393（6684）：440-442.

［3］Barabási A L，Albert R.Emergence of scaling in random networks［J］.Science，1999，286（5439）：509-512.

［4］Barabási A L，Albert R，Jeong H.Mean-field theory for scale-free random networks［J］.Physica A：Statistical Mechanicsand its Applications，1999，272（1）：173-187.

［5］Sheela L，Sudha S，Balamurugan N B.Parameter extraction of singleelectrontransistorbasedonMasterEquationapproach［C］//Emerging Trends in VLSI，Embedded System，Nano Electronics and Telecommunication System（ICEVENT），2013 International Conference on.IEEE，2013：1-5.

［6］Sen Q.Scale-free topology structure in ad hoc networks［C］// Communication Technology，2008.ICCT 2008.11th IEEE International Conference on.IEEE，2008：21-24.

Research on improved scale-free networks model

SUN Li-sheng，HE Dong-zhi
（Institute of Embedded Software and Systems，Beijing University of Technology，Beijing 100022，China）

Based on complex networks theory，this paper studies construction algorithm of the scale-free networks.On the basic of the original BA scale-free networks model，the network model adds internal side edges and reconnection mechanism so that it has not only a scale-free property but also a small-world property of the real social networks.The network's nodes are added initially attractive at the same time，and this paper obtains an improved scale-free networks'model.Finally，the improved scale-free networksmodel is vertified by mean-field methods theoretically and data simulation.

complex networks；scale-free networks；improved scale-free networks；mean-field methods

TN919

A

1674－6236（2016）06-0115-03

2015-05-10稿件編號：201505082

孫立晟（1988—），男，天津人，碩士研究生。研究方向：嵌入式軟件與系統。