孫立晟，何東之

（北京工業(yè)大學(xué) 嵌入式軟件與系統(tǒng)研究所，北京　100022）

改進無標(biāo)度網(wǎng)絡(luò)模型研究

孫立晟，何東之

（北京工業(yè)大學(xué) 嵌入式軟件與系統(tǒng)研究所，北京100022）

基于復(fù)雜網(wǎng)絡(luò)理論知識研究了無標(biāo)度網(wǎng)絡(luò)的構(gòu)造算法，并在原有的BA無標(biāo)度網(wǎng)絡(luò)模型的基礎(chǔ)上，通過加入內(nèi)部邊和重連邊機制使該網(wǎng)絡(luò)模型不但具有無標(biāo)度特性而且具有現(xiàn)實社會網(wǎng)絡(luò)的小世界特性，同時給網(wǎng)絡(luò)的節(jié)點加入初始引力，得出了一種改進的無標(biāo)度網(wǎng)絡(luò)模型。最后，不僅從理論上通過平均場方法驗證了改進模型，而且通過數(shù)據(jù)仿真驗證該模型。

復(fù)雜網(wǎng)絡(luò)；無標(biāo)度網(wǎng)絡(luò)；改進無標(biāo)度網(wǎng)絡(luò)；平均場方法

現(xiàn)在越來越多的研究者通過復(fù)雜網(wǎng)絡(luò)［1］中的小世界網(wǎng)絡(luò)［2］模型或無標(biāo)度網(wǎng)絡(luò)［3］模型來研究社會網(wǎng)路，而社會網(wǎng)絡(luò)同時具有小世界特性和無標(biāo)度特性。但是這兩個模型都不能同時體現(xiàn)這兩個網(wǎng)絡(luò)特性。因此，本文基于無標(biāo)度網(wǎng)絡(luò)模型的基礎(chǔ)上，通過加入內(nèi)部邊和重連邊機制，給無標(biāo)度網(wǎng)絡(luò)模型賦予小世界特性。

1　復(fù)雜網(wǎng)絡(luò)基本屬性

度（Degree）：度指的是網(wǎng)絡(luò)中與某個節(jié)點直接相連的邊的數(shù)量。在有向復(fù)雜網(wǎng)絡(luò)中，節(jié)點的度可以被定義成入度和出度。入度是指所有作為直接連接邊的終點的數(shù)量。出度是指所有作為直接連接邊的起點的數(shù)量。網(wǎng)絡(luò)的平均度被定為網(wǎng)絡(luò)中所有節(jié)點度的平均值。

其中N代表網(wǎng)絡(luò)中節(jié)點的總數(shù)，E代表網(wǎng)絡(luò)中邊的總數(shù)。一般情況下網(wǎng)絡(luò)的平均度決著網(wǎng)絡(luò)的穩(wěn)定性。

度分布（Degree distribution）：直接與某點相連的邊的數(shù)量叫做這個節(jié)點的度。設(shè)P（k）表示在復(fù)雜網(wǎng)絡(luò)中隨機取某節(jié)點度數(shù)是k的概率，則概率分布列｛P（k）｝被叫做網(wǎng)絡(luò)度分布。度分布是一個定義容易但又十分重要的數(shù)學(xué)統(tǒng)計特征量。

平均路徑長度（Average path length）：網(wǎng)絡(luò)的平均路徑長度也叫做網(wǎng)絡(luò)的平均最短路徑長度或網(wǎng)絡(luò)的特征路徑長度。平均路徑長度dij定義為網(wǎng)絡(luò)上連接節(jié)點i和節(jié)點j之間最短路徑上的邊數(shù)。

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

度分布、平均路徑長度和集群系數(shù)是復(fù)雜網(wǎng)絡(luò)中最重要的3個特征量，影響著復(fù)雜網(wǎng)絡(luò)的拓撲結(jié)構(gòu)。度分布能夠表示網(wǎng)絡(luò)的連通性，平均路徑長度決定著網(wǎng)絡(luò)上的信息傳播速度，集群系數(shù)最早出現(xiàn)于社會網(wǎng)絡(luò)的小集團特征。

2　無標(biāo)度網(wǎng)絡(luò)模型

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

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

Step2：擇優(yōu)連接：在新節(jié)點選擇舊節(jié)點連接時，令新節(jié)點連接舊節(jié)點i的概率與舊節(jié)點i的度數(shù)ki與節(jié)點度數(shù)總和成正比。經(jīng)過t時間步后，生成一個具有N=m0+t個節(jié)點和mt條邊的BA標(biāo)準(zhǔn)無標(biāo)度網(wǎng)絡(luò)模型。規(guī)定：1≤m≤m0。

3　改進的無標(biāo)度網(wǎng)絡(luò)模型

3.1度分布定義

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

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

則該網(wǎng)絡(luò)具有穩(wěn)定的度分布｛P（k），k=0，1，2，…｝。

3.2演化模型

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

因而在BA無標(biāo)度模型的基礎(chǔ)上，增加了初始吸引力、增加內(nèi)部邊、重新連接邊機制來實現(xiàn)現(xiàn)實網(wǎng)絡(luò)中人與人之間的關(guān)系。改進的模型構(gòu)造算法：

Step1：初始化m0個孤立節(jié)點構(gòu)成網(wǎng)絡(luò)模型，并給每個節(jié)點賦予初始吸引力α，所有節(jié)點初始吸引力α≥0。

其中kj是節(jié)點j的度數(shù)，生成了一條內(nèi)部邊。

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

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

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

Step6：重復(fù)Step5過程，直到模型中已經(jīng)重新連接了n條邊。

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

依次執(zhí)行 Step1，Step2，Step3，Step4，Step5，Step6步驟 t次，該模型演化成為一個具有總點數(shù)為N（t）=m0+t和總邊數(shù)為（l+m）t的網(wǎng)絡(luò)模型。

從改進的無標(biāo)度網(wǎng)絡(luò)生成過程來看，其演化的過程都是合理的，在每次循環(huán)過程中都有新節(jié)點和新邊的生成。

下面我們采用平均場方法計算改進的無標(biāo)度網(wǎng)絡(luò)的度分布，以證明該網(wǎng)絡(luò)的的度分布滿足標(biāo)準(zhǔn)無標(biāo)度網(wǎng)絡(luò)度分布冪律分布的特點。

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

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

其中等號右邊的第一項是對應(yīng)于新加入邊任意選擇的一個端點是節(jié)點i的情況，第二項是對應(yīng)于新加入邊擇優(yōu)選擇另一個端點是節(jié)點i的情況，它們兩項共同導(dǎo)致節(jié)點i的度數(shù)增加。

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

其中等號右邊表示模型中已經(jīng)存在的節(jié)點i由于被新節(jié)點連接而導(dǎo)致節(jié)點i的度數(shù)ki增加。

3）在模型中重新連接n條已經(jīng)存在的邊，則

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

當(dāng)節(jié)點i在第ti次循環(huán)時進入模型，則模型中節(jié)點i的度數(shù)初始為ki（ti）=m。則方程的解為：將3種情況一起考慮，得出的動力學(xué)方程：

網(wǎng)絡(luò)模型度的概率分布為：

假設(shè)在相同的時間間隔將新的節(jié)點加入到模型中，所以各個節(jié)點加入模型的時間都是隨機的。它進入網(wǎng)絡(luò)模型的循環(huán)次數(shù)ti服從區(qū)間［0，t］上的均勻分布，

當(dāng)t次循環(huán)生成網(wǎng)絡(luò)模型過程中度分布為：

因此，指數(shù)γ∈（2，3）。

這個極限分布是該網(wǎng)絡(luò)的度分布，其中γ叫做度指數(shù)，γ∈（2，3）。

所以此網(wǎng)絡(luò)模型符合無標(biāo)度網(wǎng)絡(luò)特性，是一個穩(wěn)定網(wǎng)絡(luò)模型。

4　數(shù)據(jù)仿真

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

圖1　規(guī)模為2000改進的網(wǎng)絡(luò)度分布概率

圖2　規(guī)模為3000改進的網(wǎng)絡(luò)度分布概率

由圖1、圖2改進的網(wǎng)絡(luò)模型的不同規(guī)模的節(jié)點度分布概率圖可知，模型中節(jié)點度的概率分布呈遞減趨勢，并且發(fā)現(xiàn)度數(shù)為5的節(jié)點分布概率最大，度數(shù)在5到10之間節(jié)點分布概率逐漸減少，度數(shù)大于10的節(jié)點分布概率很小，概率值基本相同。

通過實驗結(jié)果分析可知，改進的網(wǎng)絡(luò)模型的度分布曲線圖整體上滿足冪律分布，符合無標(biāo)度網(wǎng)絡(luò)特性，所以是改進的網(wǎng)絡(luò)模型是一個無標(biāo)度網(wǎng)絡(luò)模型。

5　結(jié)論

本文在原有無標(biāo)度網(wǎng)絡(luò)模型的基礎(chǔ)上，加入內(nèi)部邊和重連邊機制，使改進的無標(biāo)度網(wǎng)絡(luò)同時具有了小世界特性，為今后研究者通過網(wǎng)絡(luò)模型更準(zhǔn)確地仿真社會網(wǎng)絡(luò)提供了基礎(chǔ)，達到最初的研究目的。

［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—），男，天津人，碩士研究生。研究方向：嵌入式軟件與系統(tǒng)。