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

孫立晟，何東之

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

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

孫立晟，何東之

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.1度分布定義

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

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

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

3.2演化模型

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

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

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

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

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

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

Step5：在模型重新連接一條已經(jīng)存在的邊，首先任意選擇一個(gè)節(jié)點(diǎn)i，然后任意選擇一條與之連接的連邊lij，最后以擇優(yōu)概率Π（ki′，α）選擇另一個(gè)節(jié)點(diǎn)i′（i′！=i）與節(jié)點(diǎn)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次，該模型演化成為一個(gè)具有總點(diǎn)數(shù)為N（t）=m0+t和總邊數(shù)為（l+m）t的網(wǎng)絡(luò)模型。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5　結(jié)論

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

［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稿件編號(hào)：201505082

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