基于鄰節(jié)點(diǎn)總度數(shù)與隨機(jī)區(qū)分度的無標(biāo)度網(wǎng)絡(luò)模型研究

耿星晨 陳瑋

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

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

DOI：10.11907/rjdk.172982

中圖分類號：TP393

文獻(xiàn)標(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ò)模型，考慮了實(shí)際網(wǎng)絡(luò)的增長特性和優(yōu)先連接特性，揭示復(fù)雜網(wǎng)絡(luò)的無標(biāo)度特性，對現(xiàn)實(shí)世界的基本特點(diǎn)有較為準(zhǔn)確的模擬[3]。

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

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

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

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

研究表明，包括Internet、人際關(guān)系網(wǎng)和城市交通網(wǎng)在內(nèi)的眾多現(xiàn)實(shí)網(wǎng)絡(luò)，其節(jié)點(diǎn)的度分布函數(shù)具有冪律形式[7-10]。由于這類網(wǎng)絡(luò)節(jié)點(diǎn)的度無明顯的特征長度，所以被稱為無標(biāo)度網(wǎng)絡(luò)[11]。BA無標(biāo)度網(wǎng)絡(luò)模型作為首個(gè)同時(shí)具備節(jié)點(diǎn)增長與優(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模型的隨機(jī)初始吸引度網(wǎng)絡(luò)模型

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

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

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

在該模型中，節(jié)點(diǎn)的度數(shù)和吸引因子共同決定了連邊概率，于是就出現(xiàn)了即使某些節(jié)點(diǎn)度數(shù)不是很大，依舊會因?yàn)樽陨淼奈?qiáng)大而與很多節(jié)點(diǎn)產(chǎn)生連接的現(xiàn)象。

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

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

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

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

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

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

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

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

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

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

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

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

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

4 實(shí)驗(yàn)與仿真

4.1 度分布

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

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

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

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

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

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

5 結(jié)語

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

參考文獻(xiàn)：

[1] 孫立晟，何東之.改進(jìn)無標(biāo)度網(wǎng)絡(luò)模型研究[J].電子設(shè)計(jì)工程，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] 馬路，盧罡，郭俊霞.基于時(shí)變差別適應(yīng)度的網(wǎng)絡(luò)演化模型[J].計(jì)算機(jī)工程，2017，43（4）：94-99.

[4] 鄧競偉.基于隨機(jī)初始吸引度的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].計(jì)算機(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].計(jì)算機(jī)學(xué)報(bào)，2012，35（4）：741-753.

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

[11] 彭俊，李智，孫雨.一種改進(jìn)的無標(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ò)拓?fù)潇氐碾娋W(wǎng)自組織臨界狀態(tài)演化[J].中國電機(jī)工程學(xué)報(bào)，2015，35（22）：5740-5748.

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

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

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

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

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