鄭波盡，代航，胡麗君，孫爽

(中南民族大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，武漢 430074)

真實(shí)世界中的網(wǎng)絡(luò)無(wú)處不在，這些網(wǎng)絡(luò)可以通過(guò)復(fù)雜網(wǎng)絡(luò)理論來(lái)描述，其中包括www，Internet萬(wàn)維網(wǎng)，科學(xué)協(xié)作網(wǎng)絡(luò)和全球機(jī)場(chǎng)網(wǎng)絡(luò)等[1].許多實(shí)驗(yàn)數(shù)據(jù)表明，真實(shí)網(wǎng)絡(luò)可以表現(xiàn)出無(wú)標(biāo)度特性，例如，網(wǎng)絡(luò)節(jié)點(diǎn)度的分布滿足冪律分布[2]，即大多數(shù)節(jié)點(diǎn)是低度節(jié)點(diǎn)，少量節(jié)點(diǎn)是高度節(jié)點(diǎn).為了解釋這一現(xiàn)象，1999年BARABSI和ALBERT[3]提出了無(wú)標(biāo)度網(wǎng)絡(luò)的生成模BA模型[3,4]，該模型能采用優(yōu)先連接機(jī)制[5]，網(wǎng)絡(luò)規(guī)模隨著時(shí)間的推移不斷增大，新節(jié)點(diǎn)的加入會(huì)優(yōu)先連接到高度節(jié)點(diǎn)，能保證生成冪值近似為3的無(wú)標(biāo)度網(wǎng)絡(luò).

然而，許多現(xiàn)實(shí)世界中的網(wǎng)絡(luò)并不是單一規(guī)模的擴(kuò)張，而是動(dòng)態(tài)演化的，主要體現(xiàn)在三個(gè)方面：增加鏈路和節(jié)點(diǎn)，刪除鏈路和節(jié)點(diǎn)，或節(jié)點(diǎn)之間鏈路的動(dòng)態(tài)改變.例如，可以將用戶聊天軟件的聯(lián)系人作為網(wǎng)絡(luò)中的節(jié)點(diǎn)，將聯(lián)系人列表中的好友作為鏈接來(lái)構(gòu)建一個(gè)網(wǎng)絡(luò).盡管軟件聯(lián)系人的容量是一定的，但該網(wǎng)絡(luò)仍然是一個(gè)不斷發(fā)展和不斷變化的網(wǎng)絡(luò)，其中的變化包括：新聯(lián)系人的添加(包括節(jié)點(diǎn)和鏈接)，一些不常用聯(lián)系人的刪除(節(jié)點(diǎn)刪除的同時(shí)鏈接同樣被刪除).蛋白質(zhì)網(wǎng)絡(luò)[6]也是一個(gè)不斷進(jìn)化的網(wǎng)絡(luò)，當(dāng)基因轉(zhuǎn)錄或發(fā)生突變時(shí)，同樣存在節(jié)點(diǎn)和鏈接的添加和刪除.

學(xué)者們?yōu)榱烁玫啬M出真實(shí)網(wǎng)絡(luò)的演化模型，于是在演化過(guò)程中加入出生率和死亡率等參數(shù)來(lái)建造一個(gè)動(dòng)態(tài)的演化環(huán)境，其中，SHI等[7]借鑒BA模型的演化機(jī)制，提出一種網(wǎng)絡(luò)模型可以添加和刪除鏈接和節(jié)點(diǎn)，來(lái)動(dòng)態(tài)地模擬真實(shí)網(wǎng)絡(luò)的演化情況，最終結(jié)果顯示網(wǎng)絡(luò)的結(jié)構(gòu)仍具有無(wú)標(biāo)度特征，并揭示了網(wǎng)絡(luò)演變成無(wú)標(biāo)度網(wǎng)絡(luò)的過(guò)程；但是，刪除和增加機(jī)制并非是隨機(jī)的，其過(guò)程等價(jià)于傳統(tǒng)的BA模型.VURAL等[8]發(fā)現(xiàn)網(wǎng)絡(luò)的演化表現(xiàn)為新節(jié)點(diǎn)和邊的隨機(jī)添加，導(dǎo)致網(wǎng)絡(luò)依賴的結(jié)構(gòu)發(fā)生變化，從而不再是無(wú)標(biāo)度網(wǎng)絡(luò)；FENG等[9,10]在確定了網(wǎng)絡(luò)構(gòu)建機(jī)制的基礎(chǔ)上，對(duì)基于生死過(guò)程的網(wǎng)絡(luò)模型進(jìn)行演化分析，最終通過(guò)對(duì)網(wǎng)絡(luò)結(jié)構(gòu)的分析，表明該模型能生成無(wú)標(biāo)度網(wǎng)絡(luò)；但是，其生死過(guò)程并非一個(gè)隨機(jī)過(guò)程.在隨機(jī)性的干擾下，上述網(wǎng)絡(luò)模型都等價(jià)于傳統(tǒng)的BA模型.

隨機(jī)地增加和刪除網(wǎng)絡(luò)中的節(jié)點(diǎn)會(huì)導(dǎo)致上述模型不能生成無(wú)標(biāo)度網(wǎng)絡(luò).真實(shí)網(wǎng)絡(luò)是動(dòng)態(tài)演化的，隨著時(shí)間的增長(zhǎng)，網(wǎng)絡(luò)的大小和結(jié)構(gòu)不斷地發(fā)生著變化，隨機(jī)性非常強(qiáng)，例如，節(jié)點(diǎn)死亡后會(huì)被移出網(wǎng)絡(luò)，當(dāng)多個(gè)高度節(jié)點(diǎn)死亡時(shí)，與這些節(jié)點(diǎn)相連的邊都會(huì)被刪除，從而破壞網(wǎng)絡(luò)的無(wú)標(biāo)度特性；同樣，新生節(jié)點(diǎn)的隨機(jī)加入也會(huì)造成網(wǎng)絡(luò)的結(jié)構(gòu)和規(guī)模發(fā)生變化.

在隨機(jī)增加和刪除節(jié)點(diǎn)之后，為了能保證網(wǎng)絡(luò)是無(wú)標(biāo)度的，本文采用優(yōu)化模型的思想[11-15]，提出一種動(dòng)態(tài)演化下的無(wú)標(biāo)度網(wǎng)絡(luò)生成算法(SFNGA)，該算法基于邊度優(yōu)化的多目標(biāo)優(yōu)化策略，在演化過(guò)程中，即使以隨機(jī)方式增刪節(jié)點(diǎn)，只要不停地優(yōu)化網(wǎng)絡(luò)的邊度，使之邊度最大化，就能保證網(wǎng)絡(luò)的結(jié)構(gòu)一直具有無(wú)標(biāo)度特征.本文將對(duì)邊度優(yōu)化這一核心概念進(jìn)行論述，并在數(shù)學(xué)理論和實(shí)驗(yàn)分析的基礎(chǔ)上驗(yàn)證其正確性.

本文的組織結(jié)構(gòu)如下：第一節(jié)將對(duì)動(dòng)態(tài)演化下的傳統(tǒng)模型進(jìn)行分析，說(shuō)明傳統(tǒng)模型不適合隨機(jī)性很強(qiáng)的動(dòng)態(tài)演化；第二節(jié)詳細(xì)介紹本文所提出的SFNGA算法，以及所采用的邊度優(yōu)化策略；第三節(jié)對(duì)本文提出的算法進(jìn)行代碼實(shí)現(xiàn)，并對(duì)結(jié)果進(jìn)行分析；第四節(jié)對(duì)本文進(jìn)行總結(jié).

1 動(dòng)態(tài)演化中的BA模型

為了驗(yàn)證傳統(tǒng)模型在動(dòng)態(tài)演化中的演變情況，以傳統(tǒng)的BA模型為例，作動(dòng)態(tài)演化分析.在演化過(guò)程中加入出生率和死亡率來(lái)模擬動(dòng)態(tài)演化特征，同時(shí)為了保證隨機(jī)性，新生節(jié)點(diǎn)采取隨機(jī)加入的方式，并不遵從優(yōu)先連接機(jī)制.出生節(jié)點(diǎn)的隨機(jī)加入和死亡節(jié)點(diǎn)的刪除會(huì)很大程度地改變網(wǎng)絡(luò)的結(jié)構(gòu).因此，需對(duì)加入出生率和死亡率后的網(wǎng)絡(luò)模型進(jìn)行長(zhǎng)時(shí)間的演化，并對(duì)演化結(jié)束后的網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行表征分析.

實(shí)驗(yàn)條件如下：網(wǎng)絡(luò)大小為N=1000，出生率Birth_Pi= 0.005，新生節(jié)點(diǎn)計(jì)算公式為N·Birth_Pi，即每次新生節(jié)點(diǎn)個(gè)數(shù)為5；死亡率Death_Pi= 0.005，死亡節(jié)點(diǎn)計(jì)算公式為N·Death_Pi，即每次死亡節(jié)點(diǎn)個(gè)數(shù)為5，網(wǎng)絡(luò)中死亡的節(jié)點(diǎn)都是隨機(jī)選擇的；出生和死亡的周期為T(mén)= 10，即每演化10次進(jìn)行一次出生或死亡操作；總演化時(shí)間Time= 10000.

該演化算法的偽代碼描述如下：

Input：N,BP,DP,T,Time;

Initialize a BA networkG(A);

fori=1 toTimedo

ifi%T==0 do

BirthandDeath(G(A),N,BP,DP);

end if

end for

為了保證演化過(guò)程中網(wǎng)絡(luò)規(guī)模的變化不影響實(shí)驗(yàn)結(jié)果的分析，假設(shè)出生率=死亡率，進(jìn)行10000次的動(dòng)態(tài)演化后，對(duì)節(jié)點(diǎn)度的概率分布做雙對(duì)數(shù)表征，判斷其結(jié)構(gòu)的變化.實(shí)驗(yàn)結(jié)果如圖1所示，均為度的概率分布和網(wǎng)絡(luò)的拓?fù)鋱D，其中圖1(a)為演化前的網(wǎng)絡(luò)節(jié)點(diǎn)度的概率分布圖和網(wǎng)絡(luò)拓?fù)鋱D，很明顯，演化前度分布服從冪律分布，并且網(wǎng)絡(luò)拓?fù)浔憩F(xiàn)出無(wú)標(biāo)度特征；圖1(b)為演化后的網(wǎng)絡(luò)節(jié)點(diǎn)度的概率分布圖和網(wǎng)絡(luò)拓?fù)鋱D，可以看出演化結(jié)束后，高度節(jié)點(diǎn)的數(shù)量相比演化前有很大程度的降低，節(jié)點(diǎn)度的概率分布并不服從冪律分布，并且從網(wǎng)絡(luò)的拓?fù)鋱D可以看出，很多節(jié)點(diǎn)從網(wǎng)絡(luò)中脫離開(kāi)來(lái)，說(shuō)明新生節(jié)點(diǎn)和死亡節(jié)點(diǎn)導(dǎo)致網(wǎng)絡(luò)結(jié)構(gòu)發(fā)生了很大的變化.所以傳統(tǒng)的BA模型并不能在動(dòng)態(tài)演化中維持網(wǎng)絡(luò)結(jié)構(gòu)不變，不能避免隨機(jī)性的干擾.

(a)演化前 (b)演化后

2 SFNGA算法

在隨機(jī)性的干擾下，傳統(tǒng)的演化模型不能生成無(wú)標(biāo)度網(wǎng)絡(luò).為了抵抗隨機(jī)性的干擾，本文基于邊度優(yōu)化的多目標(biāo)優(yōu)化策略，來(lái)得到無(wú)標(biāo)度網(wǎng)絡(luò).

2.1 邊度的定義

圖2 邊度的描述

2.2 邊度優(yōu)化策略

根據(jù)邊度的定義，將優(yōu)化模型描述為：一個(gè)連通的無(wú)向網(wǎng)絡(luò)使其網(wǎng)絡(luò)中節(jié)點(diǎn)的總度不變，使其網(wǎng)絡(luò)的邊度之和最大化.在網(wǎng)絡(luò)的隨機(jī)演化中，使網(wǎng)絡(luò)朝著最大化邊度這一目標(biāo)優(yōu)化.其數(shù)學(xué)模型可以表示為：

(1)

其中，A是網(wǎng)絡(luò)變量；F(A)是網(wǎng)絡(luò)的邊度；N是網(wǎng)絡(luò)的總節(jié)點(diǎn)數(shù)；xi(A)是網(wǎng)絡(luò)中節(jié)點(diǎn)i的度；函數(shù)δij(A)表示節(jié)點(diǎn)i和節(jié)點(diǎn)j之間是否存在連接，如果存在值為1，否則值為0；a和b是非負(fù)常量.

無(wú)標(biāo)度網(wǎng)絡(luò)的度分布滿足冪律分布，隨機(jī)選取一個(gè)節(jié)點(diǎn)，它的度d正好是自然數(shù)k的概率滿足P(k)～k-γ.于是，將網(wǎng)絡(luò)中節(jié)點(diǎn)的度看成隨機(jī)變量，將公式(1)中的xi看成隨機(jī)變量，同時(shí)假設(shè)xi≈xj，于是：

其中xi表示第i個(gè)節(jié)點(diǎn)的度，并滿足xi=C(X)，所以公式(1)可以近似為：

令γ=1+a+b，可以得到P(X)=CX-γ+δ，δ為一個(gè)常數(shù).當(dāng)C為一個(gè)常數(shù)時(shí)，該公式滿足無(wú)標(biāo)度網(wǎng)絡(luò)的冪律分布公式，度分布指數(shù)為γ，因此，最終得到的網(wǎng)絡(luò)是無(wú)標(biāo)度網(wǎng)絡(luò).

隨機(jī)網(wǎng)絡(luò)通過(guò)控制網(wǎng)絡(luò)的總度不變，不斷優(yōu)化網(wǎng)絡(luò)中節(jié)點(diǎn)的連邊，使網(wǎng)絡(luò)總邊度最大化，從而達(dá)到由隨機(jī)網(wǎng)絡(luò)演化成無(wú)標(biāo)度網(wǎng)絡(luò)的目的.首先，初始化一個(gè)隨機(jī)網(wǎng)絡(luò)G(A)，這個(gè)網(wǎng)絡(luò)的總度為n(n為固定值)，網(wǎng)絡(luò)總的邊度為edge_degree_sum1；然后，隨機(jī)刪除網(wǎng)絡(luò)中的一條邊并隨機(jī)連接一條邊，此時(shí)，網(wǎng)絡(luò)發(fā)生改變，再次計(jì)算網(wǎng)絡(luò)總邊度為edge_degree_sum2；如果edge_degree_sum1

圖3 邊度優(yōu)化方式

2.3 算法描述

SFNGA算法采用邊度優(yōu)化策略，以用戶給定的網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)、出生率、死亡率、出生和死亡的周期、優(yōu)化次數(shù)和演化時(shí)間作為輸入?yún)?shù)，最終演化結(jié)束后得到一個(gè)無(wú)標(biāo)度網(wǎng)絡(luò).算法的主要過(guò)程為：首先根據(jù)輸入的網(wǎng)絡(luò)大小N初始化一個(gè)隨機(jī)網(wǎng)絡(luò)；然后每達(dá)到一個(gè)出生和死亡的周期就進(jìn)行一次節(jié)點(diǎn)的刪除和節(jié)點(diǎn)的加入，這個(gè)過(guò)程是隨機(jī)進(jìn)行的；出生死亡操作完成之后，進(jìn)行邊度的優(yōu)化；演化結(jié)束便可得到一個(gè)無(wú)標(biāo)度網(wǎng)絡(luò).該算法過(guò)程描述如下：

Step1：初始化一個(gè)節(jié)點(diǎn)為N的隨機(jī)網(wǎng)絡(luò)，每個(gè)節(jié)點(diǎn)的度1≤degree≤E的網(wǎng)絡(luò)G(A)，其中N和E為常數(shù)，隨機(jī)設(shè)定；

Step2：出生率和死亡率的加入.設(shè)置出生率Birth_Pi和死亡率Death_Pi的數(shù)值，指定一個(gè)周期T，當(dāng)達(dá)到一個(gè)周期時(shí)，網(wǎng)絡(luò)會(huì)進(jìn)行一次節(jié)點(diǎn)的隨機(jī)刪除和隨機(jī)加入，每次新生的節(jié)點(diǎn)個(gè)數(shù)為N·Birth_Pi，死亡的節(jié)點(diǎn)個(gè)數(shù)為N·Death_Pi，上述參數(shù)可以隨意設(shè)定；

Step3：對(duì)網(wǎng)絡(luò)G(A)進(jìn)行邊度的優(yōu)化.首先記錄網(wǎng)絡(luò)G(A)的邊度之和為edge_degree_sum1，然后隨機(jī)選擇網(wǎng)絡(luò)中的4個(gè)節(jié)點(diǎn)(i,j,k,l)，進(jìn)入優(yōu)化的前提條件是節(jié)點(diǎn)i與j之間有邊，k與l之間沒(méi)有邊，如果不滿足，則繼續(xù)尋找，直到滿足為止；刪除節(jié)點(diǎn)i和j之間的邊，然后將節(jié)點(diǎn)k與l進(jìn)行連接形成一個(gè)新的網(wǎng)絡(luò)G(B)；最后，再次計(jì)算網(wǎng)絡(luò)G(B)的邊度之和為edge_degree_sum2，如果edge_degree_sum2>edge_degree_sum1，則讓G(B)替代G(A)，否則網(wǎng)絡(luò)仍然為G(A).進(jìn)而，還可以設(shè)置每個(gè)單位時(shí)間優(yōu)化的邊數(shù)來(lái)控制整個(gè)演化過(guò)程中總的優(yōu)化邊數(shù)，單位時(shí)間優(yōu)化邊數(shù)為Edge_Num；

Step4：演化的總時(shí)長(zhǎng)為T(mén)IME，當(dāng)演化時(shí)間t

Input：N,BP,DP,T,Times;

Initialize a random networkG(A);

while count

G(B)=G(A);

sum1 =CalEdgeDegree(G(A));

Delete an edge fromG(B);

Linked an edge fromG(B);

sum2 =CalEdgeDegree(G(B));

ifsum1

G(A)=G(B);

count++;

else

continue;

if count%T==0 do

BirthandDeath(G(A),N,BP,DP);

end if

end for

Output(G(A)).

3 實(shí)驗(yàn)仿真

根據(jù)本文2.3節(jié)對(duì)SFNGA算法的描述，可以對(duì)該算法進(jìn)行代碼實(shí)現(xiàn)，因此，只需要輸入?yún)?shù)就可以得到指定規(guī)模的無(wú)標(biāo)度網(wǎng)絡(luò).為了驗(yàn)證算法的正確性，分別輸入表1中所設(shè)置的參數(shù)來(lái)生成指定的網(wǎng)絡(luò)，其中，BP表示出生率，DP表示死亡率，E表示每次優(yōu)化的邊數(shù)，T表示出生和死亡周期，Time是演化的時(shí)間.為了避免網(wǎng)絡(luò)規(guī)模影響實(shí)驗(yàn)結(jié)果，就需要控制每個(gè)周期T內(nèi)出生節(jié)點(diǎn)個(gè)數(shù)等于死亡節(jié)點(diǎn)個(gè)數(shù)，即BP=DP.演化結(jié)束之后分別對(duì)生成的5個(gè)網(wǎng)絡(luò)進(jìn)行分析.

本文分別對(duì)表1中的5個(gè)網(wǎng)絡(luò)進(jìn)行10000次動(dòng)態(tài)演化，演化結(jié)束后對(duì)網(wǎng)絡(luò)所有節(jié)點(diǎn)的度作概率統(tǒng)計(jì)，并將統(tǒng)計(jì)結(jié)果用雙對(duì)數(shù)表征，對(duì)所有網(wǎng)絡(luò)的結(jié)構(gòu)作拓?fù)浞治?如圖4所示：每個(gè)網(wǎng)絡(luò)的雙對(duì)數(shù)圖中都包含該網(wǎng)絡(luò)的結(jié)構(gòu)拓?fù)鋱D，可以看出，網(wǎng)絡(luò)大小為300、500、800、1000和2000的冪指數(shù)γ分別為1.545、2.014、1.956、2.056和1.653，符合無(wú)標(biāo)度網(wǎng)絡(luò)的冪率特征；網(wǎng)絡(luò)拓?fù)鋱D呈現(xiàn)出低度節(jié)點(diǎn)分布在最外圍、度越高的節(jié)點(diǎn)逐漸向網(wǎng)絡(luò)內(nèi)部聚集的現(xiàn)象，其中，網(wǎng)絡(luò)中絕大多數(shù)為低度節(jié)點(diǎn)，只有少量高度節(jié)點(diǎn)在網(wǎng)絡(luò)內(nèi)部.綜合以上分析可知，演化的最終結(jié)果都是無(wú)標(biāo)度網(wǎng)絡(luò).

表1 數(shù)據(jù)參數(shù)

圖4 實(shí)驗(yàn)結(jié)果圖

4 結(jié)論

在動(dòng)態(tài)演化下，出生率和死亡率的加入往往會(huì)改變網(wǎng)絡(luò)的結(jié)構(gòu)特征，節(jié)點(diǎn)的隨機(jī)刪除和新生節(jié)點(diǎn)的隨機(jī)加入會(huì)破壞無(wú)標(biāo)度網(wǎng)絡(luò)的網(wǎng)絡(luò)結(jié)構(gòu).本文提出動(dòng)態(tài)演化下的無(wú)標(biāo)度網(wǎng)絡(luò)生成算法SFNGA，該算法在動(dòng)態(tài)演化中仍能保證網(wǎng)絡(luò)結(jié)構(gòu)不受出生率和死亡率這些隨機(jī)因素的影響，保證最終生成的網(wǎng)絡(luò)為無(wú)標(biāo)度網(wǎng)絡(luò).同時(shí)該算法能根據(jù)用戶給定的網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)、出生率、死亡率、出生和死亡的周期、優(yōu)化次數(shù)和演化時(shí)間作為輸入?yún)?shù)，生成一個(gè)指定大小的無(wú)標(biāo)度網(wǎng)絡(luò)，實(shí)驗(yàn)證明了該算法的正確性.它可用于疾病傳播、輿情傳播、人工道德網(wǎng)絡(luò)建模等領(lǐng)域.