耿星晨 陳瑋

摘 要：運用復(fù)雜網(wǎng)絡(luò)基礎(chǔ)知識，基于BA無標(biāo)度網(wǎng)絡(luò)模型構(gòu)造方法，參考隨機初始吸引度網(wǎng)絡(luò)的優(yōu)點與不足，提出了一種改進的無標(biāo)度網(wǎng)絡(luò)演化模型。該模型以節(jié)點區(qū)分度代替隨機初始吸引度，使舊節(jié)點對于新節(jié)點的單方面吸引轉(zhuǎn)變?yōu)閮晒?jié)點間的相互作用，更突出了不同節(jié)點間的差異性；考慮節(jié)點的實際影響力，以鄰節(jié)點總度數(shù)作為擇優(yōu)連接標(biāo)準(zhǔn)，避免忽視潛在的重要節(jié)點，使網(wǎng)絡(luò)更符合現(xiàn)實情況。通過實驗仿真與分析，驗證了該模型服從冪律分布，初始區(qū)分度對網(wǎng)絡(luò)演化具有重要影響，且模型具有更小的鄰節(jié)點總度數(shù)，網(wǎng)絡(luò)的“貧富懸殊”程度降低，可以模擬更復(fù)雜的現(xiàn)實情況。

關(guān)鍵詞：復(fù)雜網(wǎng)絡(luò)；無標(biāo)度網(wǎng)絡(luò)；鄰節(jié)點度數(shù)；冪律分布；隨機區(qū)分度

DOI：10.11907/rjdk.172982

中圖分類號：TP393

文獻標(biāo)識碼：A 文章編號：1672-7800（2018）006-0190-04

Abstract：Based on the construction method of BA scale-free network model，this paper uses the basic knowledge of complex network and considers the advantages and disadvantages of random initial attraction network to propose an improved scale free network evolution model.In this model， the initial attraction degree is replaced by the division degree，then the old node's unilateral attraction to the new node is transformed into the interaction between the two nodes， which makes the differences between nodes more prominent； it also considers the actual influence of nodes and uses the total degree of neighbor node as the standard of preferential attachment， which avoids the negligence of potential important nodes， and makes the network more realistic.Through simulation and analysis， it verifies the model follows power-law distribution and the initial discrimination has important influence on the network evolution， and the model has a smaller total degree of nodes， the gap of the network between the rich and the poor decreases， it can simulate more complex reality.

Key Words：complex network； scale-free network； adjacent node degree； power law distribution； random division

0 引言

通過復(fù)雜網(wǎng)絡(luò)中的無標(biāo)度網(wǎng)絡(luò)模型研究社會網(wǎng)絡(luò)越來越多[1]。BA無標(biāo)度網(wǎng)絡(luò)模型是由Barabási 和 Albert[2]于1999年提出的一種經(jīng)典的無標(biāo)度網(wǎng)絡(luò)模型，考慮了實際網(wǎng)絡(luò)的增長特性和優(yōu)先連接特性，揭示復(fù)雜網(wǎng)絡(luò)的無標(biāo)度特性，對現(xiàn)實世界的基本特點有較為準(zhǔn)確的模擬[3]。

然而，BA網(wǎng)絡(luò)節(jié)點間的連接概率僅僅依據(jù)原節(jié)點自身的度數(shù)，易造成節(jié)點度數(shù) “貧富差距”過于懸殊。在現(xiàn)實網(wǎng)絡(luò)中，節(jié)點選擇不僅取決于自身度數(shù)，還必須考慮節(jié)點自身特性、實際影響力等因素，因而無法較好地模擬復(fù)雜的現(xiàn)實情況。

文獻[4]提出了基于DMS模型[5]的隨機初始吸引度網(wǎng)絡(luò)模型，通過對節(jié)點加入隨機的初始吸引因子，較好地體現(xiàn)了節(jié)點自身特性對新節(jié)點的影響。該模型雖然對現(xiàn)實模擬起了一定的改善作用，但原節(jié)點對新節(jié)點仍然是單方面吸引，網(wǎng)絡(luò)依然 “貧富差距”懸殊。

針對上述不足，本文基于BA無標(biāo)度網(wǎng)絡(luò)模型，從節(jié)點的實際影響力出發(fā)，考慮不同節(jié)點間的雙向選擇性，通過鄰節(jié)點總度數(shù)與隨機區(qū)分度對傳統(tǒng)模型進行改進。

1 傳統(tǒng)BA無標(biāo)度網(wǎng)絡(luò)

研究表明，包括Internet、人際關(guān)系網(wǎng)和城市交通網(wǎng)在內(nèi)的眾多現(xiàn)實網(wǎng)絡(luò)，其節(jié)點的度分布函數(shù)具有冪律形式[7-10]。由于這類網(wǎng)絡(luò)節(jié)點的度無明顯的特征長度，所以被稱為無標(biāo)度網(wǎng)絡(luò)[11]。BA無標(biāo)度網(wǎng)絡(luò)模型作為首個同時具備節(jié)點增長與優(yōu)先連接的網(wǎng)絡(luò)模型，具有明顯的小世界特性[12]，其穩(wěn)態(tài)度分布函數(shù)為：

顯然其度指數(shù)與網(wǎng)絡(luò)規(guī)模m是無關(guān)的。BA無標(biāo)度模型構(gòu)造算法如下：

2 基于DMS模型的隨機初始吸引度網(wǎng)絡(luò)模型

傳統(tǒng)BA無標(biāo)度網(wǎng)絡(luò)僅僅通過節(jié)點的度數(shù)大小決定連接概率，對于現(xiàn)實網(wǎng)絡(luò)的情況過于簡化。為了對現(xiàn)實網(wǎng)絡(luò)進行更深入的研究和分析[10-11]，需要對節(jié)點本身的特性進行明確表達。網(wǎng)絡(luò)中的舊節(jié)點會對新加入的節(jié)點產(chǎn)生某種吸引力，吸引力大小只與自身特性有關(guān)。將節(jié)點內(nèi)在具有的對新節(jié)點的吸引力定義為吸引因子[12]，用α表示，某個節(jié)點i的吸引因子表示為α-i，由此提出隨機初始吸引度網(wǎng)絡(luò)模型，該網(wǎng)絡(luò)演化過程為：

（1）最初時網(wǎng)絡(luò)存在m-0個節(jié)點，這些節(jié)點隨機獲取了一個吸引因子，在每個時間步加入一個新節(jié)點，新節(jié)點會與已存在的m個舊節(jié)點連接，m≤m-0。

（2）新節(jié)點與已存在的某個舊節(jié)點i相連接的概率：

在該模型中，節(jié)點的度數(shù)和吸引因子共同決定了連邊概率，于是就出現(xiàn)了即使某些節(jié)點度數(shù)不是很大，依舊會因為自身的吸引力強大而與很多節(jié)點產(chǎn)生連接的現(xiàn)象。

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

3.1 隨機初始區(qū)分度因子

雖然隨機初始吸引度網(wǎng)絡(luò)中的舊節(jié)點對新節(jié)點有著不同的吸引力，但由于舊節(jié)點的吸引度值仍然是定值，則對于以后出現(xiàn)的所有新節(jié)點，吸引度較大的舊節(jié)點始終保持吸引力的優(yōu)勢，這種特性加劇了各節(jié)點度數(shù)的差異性。在眾多現(xiàn)實網(wǎng)絡(luò)中，例如合作關(guān)系網(wǎng)絡(luò)，人與人之間的聯(lián)系常常是雙向選擇的，即新舊節(jié)點的互相吸引才會使雙方擁有更大的連接可能性。

這里對每個節(jié)點隨機加入一個反映其本身特性的參數(shù)β（0≤β≤β-max），叫作節(jié)點區(qū)分度因子，表示該節(jié)點與某種指標(biāo)的不同程度。當(dāng)β為0時，該節(jié)點的自身特征與標(biāo)準(zhǔn)情況完全一致；當(dāng)β為β-max時，則與標(biāo)準(zhǔn)情況的所有特征都不同。舊節(jié)點i的區(qū)分度因子為β-i，新加入節(jié)點p的區(qū)分度因子為β-p，兩者間的實際吸引力以Δβ-ip表示：

顯然，兩個節(jié)點的β值越接近，兩者間的相似度越高越容易發(fā)生連接，這與人際交往中的“人以群分”現(xiàn)象很相似。

3.2 鄰節(jié)點總度數(shù)與實際影響力

一般認(rèn)為，節(jié)點度數(shù)越大，節(jié)點在網(wǎng)絡(luò)中就越重要[13]，新節(jié)點會傾向于與度數(shù)大的節(jié)點進行連接，造成度數(shù)大的節(jié)點隨著時間步的推移度數(shù)越來越大[14-15]。但是，實際網(wǎng)絡(luò)中存在著一種如圖1所示的常見現(xiàn)象，節(jié)點2和節(jié)點3具有較大度數(shù)，但它們的鄰節(jié)點卻都是度數(shù)很小的節(jié)點，而節(jié)點1雖然本身的度數(shù)很小，但它所連接的節(jié)點卻都是度數(shù)較大的節(jié)點。在信息傳播網(wǎng)絡(luò)[16]、社交網(wǎng)絡(luò)等現(xiàn)實網(wǎng)絡(luò)中，節(jié)點1往往比節(jié)點2和節(jié)點3擁有更大的潛在影響力[17]，應(yīng)當(dāng)獲得更大的連接概率。因此，按照BA網(wǎng)絡(luò)或隨機初始吸引度網(wǎng)絡(luò)方法，僅僅只考慮節(jié)點本身的度數(shù)，極易忽略這類潛在的重要節(jié)點。

為了更好地模擬現(xiàn)實網(wǎng)絡(luò)，凸顯潛在的重要節(jié)點，就需考慮各節(jié)點的鄰節(jié)點總度數(shù)，用L-i表示節(jié)點i的鄰節(jié)點總度數(shù)，則：

3.3 改進的網(wǎng)絡(luò)演化模型

基于鄰節(jié)點總度數(shù)以及節(jié)點間不同的吸引關(guān)系，本文對BA無標(biāo)度網(wǎng)絡(luò)模型的構(gòu)造規(guī)則進行修改，得到一種改進的演化模型，生成規(guī)則如下：

3.4 鄰節(jié)點總度數(shù)數(shù)學(xué)分析

顯然，方差越小，各節(jié)點度數(shù)與平均度數(shù)的偏離程度越小，{k-j}越穩(wěn)定。所以當(dāng)∑jL-j變小時，方差也隨之變小，各節(jié)點度數(shù)間的差異也會變小。

通過上述分析可知，初始條件相同時，網(wǎng)絡(luò)的鄰節(jié)點總度數(shù)越小，則節(jié)點度數(shù)間的差異越小，連邊的分布越均勻，網(wǎng)絡(luò)的“貧富差距”程度越小。

4 實驗與仿真

4.1 度分布

用MATLAB實現(xiàn)該算法，對改進后的網(wǎng)絡(luò)模型進行仿真。設(shè)置初始參數(shù)m-0=3，m=3，N=3 000，考慮到節(jié)點區(qū)分度的隨機性對最終結(jié)果帶來的可能影響，始終令初始區(qū)分度因子β服從（0，1）的均勻分布。經(jīng)過多次實驗后，得到改進模型的度分布概率如圖2所示，節(jié)點度為3的概率最大，之后呈現(xiàn)下降趨勢，而度數(shù)超過10的節(jié)點概率都很小，趨近于0，此結(jié)果表明該模型服從冪律分布，屬于無標(biāo)度網(wǎng)絡(luò)。

4.2 區(qū)分度因子β的影響

當(dāng)保持初始參數(shù)值（m-0=3，m=3，N=1 000）不變時，使α、β分別服從（0，α-max）、（0，β-max）的均勻分布，多次實驗后的結(jié)果取平均值，分別得到兩種模型的節(jié)點度數(shù)最大值、最小度數(shù)節(jié)點占總節(jié)點數(shù)的比例隨α-max、β-max的變化關(guān)系，如圖3、圖4所示。實驗結(jié)果表明：同等規(guī)模的網(wǎng)絡(luò)，對于較小的α-max，隨機初始吸引度模型的節(jié)點度數(shù)最大值與度最小節(jié)點的比例變化較為明顯，但隨著α-max增大到一定程度后，它們幾乎不再受α影響；而β的取值范圍不斷增大時，改進模型的節(jié)點度數(shù)最大值與度最小節(jié)點的比例都會逐漸下降，整個網(wǎng)絡(luò)的“貧富差距”逐漸改善，但網(wǎng)絡(luò)依舊服從冪律分布。這是由于隨著網(wǎng)絡(luò)規(guī)模的不斷變大，隨機因子對擇優(yōu)概率的影響逐漸減小，因此通過適當(dāng)增大隨機因子的取值范圍可以使其影響力保持得更久。但隨機初始吸引度模型的單方面吸引使α的早期節(jié)點獲得更多的連接，模型的“貧富差距”仍然很大。本模型的雙向選擇性使得網(wǎng)絡(luò)演化時連邊的分布更加均勻，在需要重點考慮節(jié)點間相互作用的實際問題中，對β選擇恰當(dāng)?shù)娜≈捣秶?，可以實現(xiàn)對不同現(xiàn)實情況的模擬。

4.3 鄰節(jié)點總度數(shù)比較

對于相同規(guī)模的初始全連通網(wǎng)絡(luò)（m-0、m、N相同），BA模型、隨機初始吸引度模型和本文模型最終的總度數(shù)相同，前兩種模型中將節(jié)點分為大度數(shù)節(jié)點和小度數(shù)節(jié)點兩類，而本文則從度數(shù)k-i和鄰節(jié)點總度數(shù)L-i兩方面考慮，這樣節(jié)點大致分為4類：k-i大L-i大、k-i大L-i小、k-i小L-i大、k-i小L-i小，若忽略隨機因子帶來的影響，則第一類優(yōu)先連接，第二類與第三類的擇優(yōu)概率視具體情況而定，第四類連接概率最小，從而使得BA模型中大度數(shù)節(jié)點的連邊在本模型中會被潛在的重要節(jié)點（第三類）分走一些。因此，理論上本模型的連邊分布會更加分散，即前兩種模型的鄰節(jié)點總度數(shù)之和普遍大于本模型。

令m-0=3，m=1，這樣可以出現(xiàn)更多的潛在重要節(jié)點，為降低α、β的影響，令它們服從（0，1）的均勻分布，3種模型整體的鄰節(jié)點總度數(shù)的平均值隨網(wǎng)絡(luò)規(guī)模N的變化關(guān)系如圖5所示。圖5結(jié)果表明：總體而言，本模型的鄰節(jié)點總度數(shù)是最小的，說明網(wǎng)絡(luò)中的潛在重要節(jié)點獲得了更多的連邊，從而使網(wǎng)絡(luò)邊的分布相對均勻，更符合現(xiàn)實情況。

5 結(jié)語

本文在傳統(tǒng)BA無標(biāo)度網(wǎng)絡(luò)基礎(chǔ)上，提出了以鄰節(jié)點總度數(shù)和節(jié)點之間區(qū)分度為主要標(biāo)準(zhǔn)的無標(biāo)度網(wǎng)絡(luò)演化模型。通過賦予節(jié)點隨機的區(qū)分度因子，使節(jié)點的自身特點更加突出，節(jié)點間的連接具有了雙向選擇性；用鄰節(jié)點總度數(shù)代替節(jié)點本身的度數(shù)，使?jié)撛谥匾?jié)點得到了較大的連接概率，更加符合現(xiàn)實情況。根據(jù)實際情況，對模型中的參數(shù)進行適當(dāng)設(shè)置，可以模擬多種現(xiàn)實網(wǎng)絡(luò)，該模型為人們在更復(fù)雜的背景下模擬社會網(wǎng)絡(luò)提供了參考。

參考文獻：

[1] 孫立晟，何東之.改進無標(biāo)度網(wǎng)絡(luò)模型研究[J].電子設(shè)計工程，2016，24（6）：115-120.

[2] A L BARABASI，R.ALBERT. Emergence of scaling in random networks[J]. Science，1999，286（5439）：509-512.

[3] 馬路，盧罡，郭俊霞.基于時變差別適應(yīng)度的網(wǎng)絡(luò)演化模型[J].計算機工程，2017，43（4）：94-99.

[4] 鄧競偉.基于隨機初始吸引度的BA無標(biāo)度網(wǎng)絡(luò)演化模型研究[D].長春：東北師范大學(xué)，2009.

[5] DOROGOVTSEV S N，MENDES J F F，SAMUKHIN A N.Structure of growing networks with preferential linking[J]. Physical Review Letters，2000，85（21）：4633-4636.

[6] 郭鵬飛，張捷，呂明，等.無線通信網(wǎng)絡(luò)的建模及故障傳播[J].計算機工程與應(yīng)用，2015，51（3）：1-5.

[7] STEFAN L，BJORN G，DIRK H. Scaling law s in the spatial structure of urban road networks[J]. Physica A，2006，363（1）：89-95.

[8] MEDINA MATTA I，BYERS J. On the origin of power laws in Internet topologies[J]. ACM SIGCOMM Comput Commun Rev，2000，30（2）：18-28.

[9] 竇炳琳，李澍淞，張世永.基于結(jié)構(gòu)的社會網(wǎng)絡(luò)分析[J].計算機學(xué)報，2012，35（4）：741-753.

[10] 朱志良，邱媛源，李丹程，等.一種Web服務(wù)復(fù)雜網(wǎng)絡(luò)的構(gòu)建方法[J].小型微型計算機系統(tǒng)，2012，33（2）：199-205.

[11] 彭俊，李智，孫雨.一種改進的無標(biāo)度網(wǎng)絡(luò)演化模型[J].航天制造技術(shù)，2008（1）：40-50.

[12] CHEN F，CHEN Z Q，WANG X F，et al. The average path length of scale free networks[J]. Communications in Nonlinear Science and Numerical Simulation，2008，13（7）：1405-1410.

[13] 劉文穎，蔡萬通，張寧，等.基于加權(quán)網(wǎng)絡(luò)拓撲熵的電網(wǎng)自組織臨界狀態(tài)演化[J].中國電機工程學(xué)報，2015，35（22）：5740-5748.

[14] 高鵬，胡劍波，魏高樂.變權(quán)重的城市軌道交通復(fù)雜網(wǎng)絡(luò)魯棒性分析[J].計算機仿真，2013，30（9）：153-156.

[15] 田田，吳俊，譚躍進.基于自然連通度的復(fù)雜網(wǎng)絡(luò)抗毀性仿真優(yōu)化研究[J].復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)，2013，10（2）：88-94.

[16] 朱曉霞，劉萌萌，趙雪.復(fù)雜網(wǎng)絡(luò)中的信息傳播機制研究[J].情報科學(xué)，2017，35（5）：42-45.

[17] 趙之瀅，于海，朱志良，等.基于網(wǎng)絡(luò)社團結(jié)構(gòu)的節(jié)點傳播影響力分析[J].計算機學(xué)報，2014，37（4）：753-766.

（責(zé)任編輯：杜能鋼）