超網(wǎng)絡(luò)模型構(gòu)建中優(yōu)先連接方法研究

孟 磊,冶忠林,趙海興,楊燕琳

(1.青海師范大學(xué) 計算機(jī)學(xué)院,西寧 810016; 2.青海省藏文信息處理與機(jī)器翻譯重點實驗室,西寧 810008;3.藏文信息處理教育部重點實驗室,西寧 810008)

0 概述

隨著復(fù)雜網(wǎng)絡(luò)的興起與迅速發(fā)展,其為網(wǎng)絡(luò)的研究提供一個新方向,并對現(xiàn)實世界有了更好的認(rèn)知。自Watts-Strogatz模型[1]與Barabási-Albert模型[2]被提出以來,學(xué)術(shù)界對復(fù)雜網(wǎng)絡(luò)的研究不斷深入,其研究領(lǐng)域也在不斷擴(kuò)展。近年來,復(fù)雜網(wǎng)絡(luò)作為一種能夠很好地描述復(fù)雜的自然科學(xué)和社會系統(tǒng)的工具,已經(jīng)廣泛應(yīng)用于交通網(wǎng)絡(luò)、生物網(wǎng)絡(luò)、科研合作網(wǎng)絡(luò)和社會網(wǎng)絡(luò)等網(wǎng)絡(luò)中。然而,到目前為止,復(fù)雜網(wǎng)絡(luò)還沒有統(tǒng)一的定義。錢學(xué)森給出了復(fù)雜網(wǎng)絡(luò)一個較嚴(yán)格的定義,即具有自組織、自相似、吸引子、小世界、無標(biāo)度中部分或全部性質(zhì)的網(wǎng)絡(luò)稱為復(fù)雜網(wǎng)絡(luò)。研究復(fù)雜網(wǎng)絡(luò),實際上是研究其拓?fù)浣Y(jié)構(gòu),圖論是專門用于刻畫和分析網(wǎng)絡(luò)特性的學(xué)科,復(fù)雜網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)可以抽象成圖論中的普通圖來研究[3]。在復(fù)雜網(wǎng)絡(luò)中,通常把實際系統(tǒng)中的不同個體看作節(jié)點,系統(tǒng)中個體之間的關(guān)系看作邊,每條邊只能與2個節(jié)點相關(guān)聯(lián)。

然而,隨著實際網(wǎng)絡(luò)的發(fā)展,邊和節(jié)點的數(shù)量與類型越來越多,網(wǎng)絡(luò)結(jié)構(gòu)也就越復(fù)雜。因此,復(fù)雜網(wǎng)絡(luò)已不能完全描述復(fù)雜系統(tǒng)的特征,在現(xiàn)實生活中復(fù)雜網(wǎng)絡(luò)已經(jīng)不能真實反映出現(xiàn)實世界的特征。例如,在科學(xué)協(xié)作網(wǎng)絡(luò)中,一條邊只能描述2個作者之間的協(xié)作,但是不能描述是否有2個或者更多的作者是同一篇文章的共同作者。在食物網(wǎng)絡(luò)中,一條邊只能表示物種之間具有共同的獵物,但是并不知道具有共同獵物的整個物種群的構(gòu)成。在蛋白質(zhì)網(wǎng)絡(luò)中,一條邊只能表示2個復(fù)合物之間具有相同的蛋白質(zhì),但是對于該蛋白質(zhì)的其他任何信息均不能得知[4]。文獻(xiàn)[5-6]討論了由用戶、資源和標(biāo)簽推薦3種異質(zhì)節(jié)點組成的異質(zhì)網(wǎng)絡(luò),這3種節(jié)點很難用復(fù)雜網(wǎng)絡(luò)來描述。為了解決該問題,表示這些系統(tǒng)的一種自然方法是使用圖的一般形式——超圖[7],可以用節(jié)點表示個體,用邊表示這些個體具有共同的某種特性,這樣圖能夠表達(dá)出網(wǎng)絡(luò)的更多信息。文獻(xiàn)[8]提出了超圖理論的基本概念和性質(zhì),在超圖中,一條超邊可以包含2個以上的節(jié)點,保留了圖的原始特性。基于超圖理論的超網(wǎng)絡(luò)不僅能夠有效揭示各種節(jié)點和超邊之間的相互影響與相互作用,而且能夠有效描述這些真實系統(tǒng)。

近年來,隨著人們對超圖理論的深入研究,基于超圖結(jié)構(gòu)的超網(wǎng)絡(luò)迅速發(fā)展,學(xué)者們構(gòu)建了不同的超網(wǎng)絡(luò)演化模型并對其特性進(jìn)行分析。文獻(xiàn)[9]構(gòu)建一種基于超圖結(jié)構(gòu)的超網(wǎng)絡(luò)動態(tài)演化模型,該超網(wǎng)絡(luò)模型每次增加若干個新節(jié)點,這若干個新節(jié)點與原始網(wǎng)絡(luò)中的一個舊節(jié)點相結(jié)合生成一條新的超邊。文獻(xiàn)[10]構(gòu)建另一種超網(wǎng)絡(luò)動態(tài)演化模型,該模型每次只增加一個新節(jié)點,這一個新節(jié)點與原始網(wǎng)絡(luò)中的若干個舊節(jié)點相結(jié)合生成一條新的超邊。文獻(xiàn)[11]構(gòu)建超網(wǎng)絡(luò)和復(fù)雜網(wǎng)絡(luò)的統(tǒng)一演化模型,并研究超網(wǎng)絡(luò)無標(biāo)度特性演化機(jī)理和拓?fù)湫再|(zhì)。文獻(xiàn)[12]提出一種新的超網(wǎng)絡(luò)演化模型,在該模型中不僅有新節(jié)點的加入,還包含了舊節(jié)點與舊超邊的消失。文獻(xiàn)[13]給出了非均勻超網(wǎng)絡(luò)模型的構(gòu)建方法,并分析非均勻超網(wǎng)絡(luò)模型的演化和拓?fù)湫再|(zhì)。文獻(xiàn)[14]根據(jù)建立的超網(wǎng)絡(luò)演化模型分析供應(yīng)鏈的演化機(jī)制。文獻(xiàn)[15]基于科研作者的合作方式,用超圖理論構(gòu)建一個科研合作超網(wǎng)絡(luò)演化模型,結(jié)果發(fā)現(xiàn)作者的超度分布符合冪律分布。文獻(xiàn)[16]從唐詩的韻腳、韻母角度研究,構(gòu)建唐詩超網(wǎng)絡(luò)模型,發(fā)現(xiàn)唐詩超網(wǎng)絡(luò)的超度分布具有無標(biāo)度性質(zhì)且具有很高的聚集特性和異配性。文獻(xiàn)[17]構(gòu)建蛋白復(fù)合物超網(wǎng)絡(luò)模型,通過對該模型進(jìn)行特征分析,獲取了識別關(guān)鍵蛋白的方法。

上述超網(wǎng)絡(luò)演化模型均是基于優(yōu)先連接構(gòu)建得到的,這種優(yōu)先連接機(jī)制使得被選擇的舊節(jié)點超度大于新節(jié)點,且超度分布符合冪律分布。本文通過分析現(xiàn)有超網(wǎng)絡(luò)模型演化過程,采用賭輪法和鏈表法對優(yōu)先選擇進(jìn)行了詳細(xì)描述,利用基于這2種方法構(gòu)建的均勻超網(wǎng)絡(luò)模型和隨機(jī)超網(wǎng)絡(luò)模型,分析這2種超網(wǎng)絡(luò)模型超度冪律分布斜率的規(guī)律性質(zhì),并且討論了參數(shù)的取值對模型構(gòu)建的影響。

1 超網(wǎng)絡(luò)

目前,對超網(wǎng)絡(luò)的定義主要有基于網(wǎng)絡(luò)的超網(wǎng)絡(luò)和基于超圖理論的超網(wǎng)絡(luò)2種。其中,基于網(wǎng)絡(luò)的超網(wǎng)絡(luò)[18-19]是指連接方式較復(fù)雜、規(guī)模較大的網(wǎng)絡(luò),或者是一個網(wǎng)絡(luò)中嵌套著另一個網(wǎng)絡(luò)的多層大型網(wǎng)絡(luò)。這種由多層網(wǎng)絡(luò)組成的超網(wǎng)絡(luò)最早由美國科學(xué)家NAGURNEY等人提出,將高于而又超于現(xiàn)存網(wǎng)絡(luò)的網(wǎng)絡(luò)稱為超網(wǎng)絡(luò),該超網(wǎng)絡(luò)一般具有多層特性、多級特征、多屬性或多準(zhǔn)則等特性。基于超圖理論的超網(wǎng)絡(luò)是指可以用超圖表示的超網(wǎng)絡(luò),這類超網(wǎng)絡(luò)可以將其轉(zhuǎn)化為超圖來研究,運用超圖的定義及性質(zhì)分析研究超網(wǎng)絡(luò),以解決生活中的實際問題[20]。

超圖的關(guān)聯(lián)矩陣的定義為[21]:超圖H=(V,E)的關(guān)聯(lián)矩陣B是一個|V|×|E|的矩陣,如果節(jié)點vi在超邊ei中,則bij=1,否則bij=0。超圖H=(V,E)的節(jié)點超度分布是指超圖H中節(jié)點超度的概率分布或頻率分布。

2 超網(wǎng)絡(luò)模型構(gòu)建方法

2.1 均勻超網(wǎng)絡(luò)演化模型

在超圖理論中,將每條超邊中所包含節(jié)點數(shù)相同的超圖稱為均勻超圖,均勻超圖是最簡單、最常見的一種超圖。均勻超圖對應(yīng)到超網(wǎng)絡(luò)中即為均勻超網(wǎng)絡(luò),根據(jù)超網(wǎng)絡(luò)模型演化過程中節(jié)點的增加與選擇方式,主要分為以下3種均勻超網(wǎng)絡(luò)模型:

1)每次選擇一個舊節(jié)點生成一條新超邊[9]:開始網(wǎng)絡(luò)中只有較少的m0個節(jié)點和包含這m0個節(jié)點的一條超邊,在每個時間間隔t內(nèi)給網(wǎng)絡(luò)添加m1個新節(jié)點,這m1個新節(jié)點與網(wǎng)絡(luò)中已有的一個舊節(jié)點相結(jié)合并生成一條新的超邊。選取舊節(jié)點的概率為節(jié)點的超度與原始超網(wǎng)絡(luò)中所有節(jié)點超度之和的比值。

2)每次增加一個新節(jié)點與舊節(jié)點生成一條新超邊[10]:開始網(wǎng)絡(luò)中只有較少的m0個節(jié)點和包含這m0個節(jié)點的一條超邊,在每個時間間隔t內(nèi)給網(wǎng)絡(luò)添加一個新節(jié)點,這一個新節(jié)點與網(wǎng)絡(luò)中已有的m2(m2≤m0)個舊節(jié)點生成一條新的超邊。選取舊節(jié)點的概率為節(jié)點的超度與原始超網(wǎng)絡(luò)中所有節(jié)點超度之和的比值。

3)超網(wǎng)絡(luò)統(tǒng)一演化模型[11]:文獻(xiàn)[11]建立了統(tǒng)一的均勻超網(wǎng)絡(luò)模型,開始網(wǎng)絡(luò)中有較少的m0個節(jié)點及包含這些節(jié)點數(shù)的一條超邊,當(dāng)有m1個新節(jié)點加入網(wǎng)絡(luò)中時,這m1個節(jié)點與網(wǎng)絡(luò)中已有的m2(m2≤m0)個舊節(jié)點生成一條新超邊,總共生成m(m≤m0)條超邊,且不出現(xiàn)重邊。選取舊節(jié)點的概率為節(jié)點的超度與原始超網(wǎng)絡(luò)中所有節(jié)點超度之和的比值。

2.2 隨機(jī)超網(wǎng)絡(luò)演化模型

在超圖理論中,除了均勻超圖以外,還有隨機(jī)超圖。隨機(jī)超圖是指超圖中每條超邊所包含的節(jié)點數(shù)是不相同的,對應(yīng)到超網(wǎng)絡(luò)中即為隨機(jī)超網(wǎng)絡(luò)。日常生活中的很多超網(wǎng)絡(luò)都是隨機(jī)超網(wǎng)絡(luò),因此對隨機(jī)超網(wǎng)絡(luò)進(jìn)行研究具有現(xiàn)實意義。文獻(xiàn)[21]主要描述了以下3種隨機(jī)超網(wǎng)絡(luò)模型:

1)等概率生成的隨機(jī)超網(wǎng)絡(luò)演化模型:開始網(wǎng)絡(luò)中只有較少的m0個節(jié)點和包含這m0個節(jié)點的一條超邊,在每個時間間隔t內(nèi)給網(wǎng)絡(luò)中添加一個新節(jié)點,從0到m0-1之間等概率的取一個隨機(jī)正整數(shù)n(0≤n≤m0-1),將添加的一個新節(jié)點與這n個舊節(jié)點生成一條新的超邊。選取這n個舊節(jié)點的概率為節(jié)點的超度與原始超網(wǎng)絡(luò)中所有節(jié)點超度之和的比值。

上述3種超網(wǎng)絡(luò)模型是通過網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)而構(gòu)建的,根據(jù)不同結(jié)構(gòu)構(gòu)建的基于超圖結(jié)構(gòu)的超網(wǎng)絡(luò)模型,且均勻超網(wǎng)絡(luò)模型和隨機(jī)超網(wǎng)絡(luò)模型都是通過優(yōu)先連接策略構(gòu)建得到的。

3 優(yōu)先連接策略

優(yōu)先選擇原理為:每次選取連接節(jié)點i的概率∏dH(i)為節(jié)點i的超度dH(i)與原始超網(wǎng)絡(luò)中已有節(jié)點j的超度之和的比值,可表示為:

(1)

在超網(wǎng)絡(luò)模型構(gòu)建方法中,通過改變超網(wǎng)絡(luò)模型演化過程中節(jié)點的增加與選擇,構(gòu)建出不同的超網(wǎng)絡(luò)演化模型。近年來,對超網(wǎng)絡(luò)模型演化過程中節(jié)點的增加方式研究較多,而對如何實現(xiàn)在演化過程中的優(yōu)先連接沒有具體說明。下文對在超網(wǎng)絡(luò)模型演化中實現(xiàn)優(yōu)先連接策略的賭輪法和鏈表法進(jìn)行介紹。

3.1 賭輪法

賭輪法又稱輪盤賭法,是遺傳算法中常用的概念,基本思想是個體被選中的概率與其適應(yīng)度函數(shù)成正比關(guān)系,可表示為:

(2)

賭輪法的過程是假設(shè)群體中全部個體都是適當(dāng)性分?jǐn)?shù),由一張餅圖構(gòu)成,群體中每一個個體為餅圖中指定的小塊,塊的大小與個體的適應(yīng)性分?jǐn)?shù)成比例,適應(yīng)性分?jǐn)?shù)越高,則其在餅圖中對應(yīng)的小塊面積越大。在對個體進(jìn)行選擇時,旋轉(zhuǎn)該輪子直至輪盤停止,看指針停在哪一塊,就選中與之對應(yīng)的個體。

由式(1)、式(2)可知,超網(wǎng)絡(luò)模型演化時的優(yōu)先選擇是可以通過賭輪法實現(xiàn)的。通過實例詳細(xì)說明采用賭輪法實現(xiàn)優(yōu)先連接的過程。假設(shè)一個網(wǎng)絡(luò)中總共有5個節(jié)點,每個節(jié)點的度分別為d1=4,d2=1,d3=2,d4=2,d5=1,則可計算出每個節(jié)點被選擇的概率分別為w1=0.4,w2=0.1,w3=0.2,w4=0.2,w5=0.1。

圖1(a)為上述5個節(jié)點在一個輪盤上的概率分布,圖1(b)為累積概率之和分布。將圖1(a)轉(zhuǎn)化為圖1(b)是相當(dāng)于將5個節(jié)點的累積概率之和放在一個坐標(biāo)軸上。從圖1(a)可以看出,當(dāng)有一個新節(jié)點加入到網(wǎng)絡(luò)中時,它連接到節(jié)點1的概率為0.4,連接到節(jié)點2的概率為0.1,連接到節(jié)點3的概率為0.2,連接到節(jié)點4的概率為0.2,連接到節(jié)點5的概率為0.1。新節(jié)點連接網(wǎng)絡(luò)中的已有節(jié)點是隨機(jī)的,但是概率與已有節(jié)點的度成正比,即度越大,則越可能被連接。例如,如果由系統(tǒng)產(chǎn)生一個0～1之間的隨機(jī)數(shù),比如0.6,則選擇新的節(jié)點與節(jié)點3相連。

圖1 賭輪法示意圖Fig.1 Schematic diagram of the roulette method

賭輪法核心偽代碼如下:

1)利用賭輪法從已有的節(jié)點中隨機(jī)選擇m個節(jié)點與新加入的節(jié)點相連。

for i←1 to m do

b←0

random_data←rand(1,1)

aa←find(pp≥random_data)

jj←aa(1)

b←length(find(exist==jj))

2)已經(jīng)被選擇過的舊節(jié)點不能再被重新選擇。

if b > 0

while b > 0

random_data←rand(1,1)

aa←find(pp≥random_data)

jj←aa(1)

b←length(find(exist==jj))

end while

end if

end for

3.2 鏈表法

鏈表法是將節(jié)點儲存到鏈表中,節(jié)點的度為多少則在鏈表中將該節(jié)點儲存幾次,然后隨機(jī)從鏈表中抽取一個節(jié)點作為舊節(jié)點。為了方便理解,用一個實例來說明鏈表法的實現(xiàn)過程。假設(shè)一個網(wǎng)絡(luò)中總共有5個節(jié)點,每個節(jié)點的度分別為d1=4,d2=1,d3=2,d4=2,d5=1,并將其儲存在鏈表中,如圖2所示。其中,節(jié)點1的度為4,則節(jié)點1在鏈表中儲存4次,但是這4個節(jié)點1的位置不一定是連續(xù)的。采取隨機(jī)選擇策略時,顯然節(jié)點1被選擇的概率遠(yuǎn)大于其他節(jié)點。

圖2 鏈表法示意圖
Fig.2 Schematic diagram of the linked list method

鏈表法核心偽代碼如下:

1)利用鏈表法從已有的節(jié)點中隨機(jī)選擇m個節(jié)點與新加入的節(jié)點相連。

for i←1 to m0 do

list(i)←i;

end for

d←m0;

e←2;

cs←0;

for n←m0+1;n≤N;n←n+n0 do

t←d+cs*(n0+m);

cs←cs + 1;

if n≤N

if n+add_meici>N

n0←N-n+1;

else

n0←n0

end if

for i←1:n0

list(t+i)←n+(i-1)

sf((n+i-1),e)←1

k←1

exist←zeros(1,m)

while (k

B←randint(1,1,[1,t])

p(k)←B(1,1)

if p(k)>0 & p(k)<(t+1)

b←length(find(exist==list(p(k))))

exist(1,k)←list(p(k))

2)控制已經(jīng)被選擇過的舊節(jié)點不能再被重新選擇。

if b > 0

while b > 0

B←randint(1,1,[1,t])

p(k)←B(1,1)

b←length(find(exist==list(p(k))))

end while

exist(1,k)←list(p(k))

end if

list(t+n0+k)←list(p(k))

sf(list(p(k)),e)←1

k←k+1

end if

end while

end for

end for

4 超網(wǎng)絡(luò)仿真實驗

分別采用賭輪法和鏈表法的優(yōu)先連接策略,構(gòu)建均勻超網(wǎng)絡(luò)演化模型和隨機(jī)超網(wǎng)絡(luò)演化模型。G(G0,m,n,N)表示一個超網(wǎng)絡(luò),G0為初始網(wǎng)絡(luò)中的節(jié)點個數(shù),m為選擇的舊節(jié)點個數(shù),n為新增節(jié)點個數(shù),N為最終網(wǎng)絡(luò)中節(jié)點的總數(shù)量,即網(wǎng)絡(luò)規(guī)模。在構(gòu)建均勻超網(wǎng)絡(luò)模型時,舊節(jié)點不可以被重復(fù)選擇,在不可重復(fù)策略中,舊節(jié)點的選擇數(shù)量一定要小于初始節(jié)點數(shù)量。在構(gòu)建隨機(jī)超網(wǎng)絡(luò)模型時,舊節(jié)點可被重復(fù)選擇,在可重復(fù)選擇策略中,舊節(jié)點的選擇數(shù)量可以大于初始節(jié)點,這是因為初始節(jié)點可被多次選擇。為了得到超度分布冪律值的某些規(guī)律,本文將每次重復(fù)實驗50次,以確保斜率和參數(shù)值之間的關(guān)系不會出現(xiàn)波動。

圖3～圖5為采用賭輪法和鏈表法構(gòu)建的均勻超網(wǎng)絡(luò)模型在雙對數(shù)坐標(biāo)系下的超度分布圖。圖3是在G0=5、n=2、N=1 000不變的情況下,改變舊節(jié)點選擇數(shù)量m(m=1,2,3)時的超度分布。圖4是在G0=5、m=2、N=1 000不變的情況下,改變新增節(jié)點個數(shù)n(n=1,3,5)時的超度分布。圖5是在G0=5、m=2、n=1不變的情況下,改變網(wǎng)絡(luò)規(guī)模N(N=500,1 500,3 000)時的超度分布。

圖3 均勻超網(wǎng)絡(luò)中舊節(jié)點選擇數(shù)量的影響Fig.3 Influence of the number of old nodes selected in uniform hypernetwork

圖4 均勻超網(wǎng)絡(luò)中新節(jié)點添加數(shù)量的影響Fig.4 Influence of the number of new nodes added in uniform hypernetwork

圖5 均勻超網(wǎng)絡(luò)中網(wǎng)絡(luò)規(guī)模的影響Fig.5 Influence of the network scale in uniform hypernetwork

從圖3～圖5可以看出,在均勻超網(wǎng)絡(luò)中,采用賭輪法和鏈表法擬合出的直線斜率相差不大,且在雙對數(shù)坐標(biāo)系下呈不斷下降趨勢,數(shù)據(jù)波動較大,少數(shù)點的數(shù)值較高,多數(shù)點數(shù)值都較低,均呈冪律分布,表現(xiàn)出無標(biāo)度特征。其中,在圖3中,當(dāng)改變舊節(jié)點選擇數(shù)量m時,隨著舊節(jié)點選擇數(shù)量m的增加,擬合直線的斜率也隨之增加。在圖4中,當(dāng)改變新節(jié)點添加數(shù)量n時,隨著新節(jié)點添加數(shù)量n的增加,擬合直線的斜率逐漸變小。在圖5中,當(dāng)改變最終網(wǎng)絡(luò)規(guī)模N時,擬合直線的斜率略微波動,影響不大。

圖6～圖8為采用賭輪法和鏈表法構(gòu)建的隨機(jī)超網(wǎng)絡(luò)模型在雙對數(shù)坐標(biāo)系下的超度分布圖。其中,圖6是在G0=5、n=2、N=1 000不變的情況下,當(dāng)改變選擇舊節(jié)點的數(shù)量m(m=1,2,3)時的超度分布。圖7是在G0=5、m=2、N=1 000不變的情況下,改變新節(jié)點添加數(shù)量n(n=1,3,5)時的超度分布。圖8是在G0=5、m=2、n=1不變的情況下,改變最終網(wǎng)絡(luò)規(guī)模N(N=500,1 500,3 000)時的超度分布。從圖6～圖8可以看出,在隨機(jī)超網(wǎng)絡(luò)中,采用賭輪法和鏈表法擬合出的直線斜率相差不大,這是因為構(gòu)建模型時采用優(yōu)先連接策略,導(dǎo)致在雙對數(shù)坐標(biāo)系下數(shù)據(jù)波動較大,少數(shù)點的數(shù)值較高,多數(shù)點的數(shù)值都很低,且呈冪律分布,表現(xiàn)出無標(biāo)度特征。其中,在圖6中,當(dāng)改變選擇舊節(jié)點m的數(shù)量時,隨著舊節(jié)點選擇數(shù)量m的增加,擬合直線的斜率也隨之增加。在圖7中,當(dāng)改變新節(jié)點添加數(shù)量n時,隨著新節(jié)點添加數(shù)量n的增加,擬合直線的斜率反而變小。在圖8中,當(dāng)改變最終網(wǎng)絡(luò)規(guī)模N時,擬合直線的斜率略微波動,影響不大。

圖6 隨機(jī)超網(wǎng)絡(luò)中舊節(jié)點選擇數(shù)量的影響Fig.6 Influence of the number of old nodes selected in random hypernetwork

圖7 隨機(jī)超網(wǎng)絡(luò)中新節(jié)點添加數(shù)量的影響Fig.7 Influence of the number of new nodes added in random hypernetwork

圖8 隨機(jī)超網(wǎng)絡(luò)中網(wǎng)絡(luò)規(guī)模的影響Fig.8 Influence of the network scale in random hypernetwork

通過以上對比發(fā)現(xiàn),利用賭輪法和鏈表法構(gòu)建的均勻超網(wǎng)絡(luò)和隨機(jī)超網(wǎng)絡(luò)的超度在雙對數(shù)坐標(biāo)系下均呈冪律分布,且表現(xiàn)出無標(biāo)度特征。不論是均勻超網(wǎng)絡(luò)還是隨機(jī)超網(wǎng)絡(luò),在相同實驗條件下,賭輪法和鏈表法的實驗結(jié)果基本相同,且相差不大。

在當(dāng)今大數(shù)據(jù)時代,超網(wǎng)絡(luò)規(guī)模越來越大,為了在有限時間內(nèi)得到更多的有效網(wǎng)絡(luò)信息,高效的優(yōu)先連接機(jī)制方法愈發(fā)重要。因此,通過本文實驗分析發(fā)現(xiàn),鏈表法比賭輪法更適合網(wǎng)絡(luò)規(guī)模較大的超網(wǎng)絡(luò)模型構(gòu)建。

表1為均勻超網(wǎng)絡(luò)和隨機(jī)超網(wǎng)絡(luò)采用賭輪法及鏈表法仿真的冪律分布斜率絕對值。從表1可以看出,當(dāng)改變均勻超網(wǎng)絡(luò)和隨機(jī)超網(wǎng)絡(luò)選擇舊節(jié)點個數(shù)時,冪律分布斜率絕對值隨著選擇舊節(jié)點個數(shù)的增加而降低,即冪律分布斜率絕對值與選擇舊節(jié)點個數(shù)成反比關(guān)系;當(dāng)改變均勻超網(wǎng)絡(luò)和隨機(jī)超網(wǎng)絡(luò)新節(jié)點個數(shù)時,冪律分布斜率絕對值隨著新節(jié)點個數(shù)的增加而升高,即冪律分布斜率絕對值與新節(jié)點個數(shù)成正比關(guān)系;當(dāng)改變均勻超網(wǎng)絡(luò)和隨機(jī)超網(wǎng)絡(luò)最終網(wǎng)絡(luò)規(guī)模時,冪律分布斜率絕對值變化不大且無規(guī)律,即冪律分布斜率絕對值與最終網(wǎng)絡(luò)規(guī)模無關(guān)。

表1 冪律分布斜率絕對值結(jié)果Table 1 Results of the absolute value of the slope of the power law distribution

5 運行時間對比

表2為利用賭輪法和鏈表法構(gòu)建均勻超網(wǎng)絡(luò)及隨機(jī)超網(wǎng)絡(luò)的用時統(tǒng)計。從表2可以看出,不論是構(gòu)建均勻超網(wǎng)絡(luò)還是隨機(jī)超網(wǎng)絡(luò),賭輪法優(yōu)先選擇策略用時都遠(yuǎn)多于鏈表法優(yōu)先選擇策略。賭輪法用時最少約為38 s,而鏈表法用時最多約為18 s;當(dāng)超網(wǎng)絡(luò)模型的最終網(wǎng)絡(luò)規(guī)模為3 000時,賭輪法用時約為70 000 s即19 h,而采用鏈表法用時僅約為17 s。究其原因,從理論上分析,賭輪法每一次進(jìn)行節(jié)點選擇都要從頭開始計算累計和,而鏈表法每一次進(jìn)行節(jié)點選擇時只需要將節(jié)點放入鏈表即可,不需要計算累計和,大大縮減了構(gòu)建時間。因此,構(gòu)建超網(wǎng)絡(luò)模型時,采用鏈表法能夠大大縮短實驗時間。

通過表2還可以看出,當(dāng)改變均勻超網(wǎng)絡(luò)和隨機(jī)超網(wǎng)絡(luò)舊節(jié)點個數(shù)時,隨著舊節(jié)點個數(shù)的增加,超網(wǎng)絡(luò)的構(gòu)建時間也隨之增加;當(dāng)改變均勻超網(wǎng)絡(luò)和隨機(jī)超網(wǎng)絡(luò)新節(jié)點個數(shù)時,隨著新節(jié)點個數(shù)的增加,超網(wǎng)絡(luò)的構(gòu)建時間反而縮短;當(dāng)改變均勻超網(wǎng)絡(luò)和隨機(jī)超網(wǎng)絡(luò)最終的網(wǎng)絡(luò)規(guī)模時,隨著最終網(wǎng)絡(luò)規(guī)模的增加,超網(wǎng)絡(luò)的構(gòu)建時間大幅增長。

表2 超網(wǎng)絡(luò)模型構(gòu)建時間對比Table 2 Comparison of construction time of hypernetwork model s

6 結(jié)束語

本文采用賭輪法和鏈表法詳細(xì)闡述了超網(wǎng)絡(luò)模型演化的優(yōu)先選擇過程,利用這2種方法構(gòu)建均勻超網(wǎng)絡(luò)和隨機(jī)超網(wǎng)絡(luò)模型,并對其特性進(jìn)行分析。賭輪法和鏈表法構(gòu)建的超網(wǎng)絡(luò)模型超度分布呈冪律分布,且顯示無標(biāo)度特性,說明賭輪法和鏈表法構(gòu)建超網(wǎng)絡(luò)模型是可行的。實驗結(jié)果表明,合理設(shè)置構(gòu)建超網(wǎng)絡(luò)模型時的新舊節(jié)點個數(shù),可得到任意標(biāo)度指數(shù)的無標(biāo)度超網(wǎng)絡(luò)。通過超網(wǎng)絡(luò)模型構(gòu)建時間對比發(fā)現(xiàn),對于均勻超網(wǎng)絡(luò)與隨機(jī)超網(wǎng)絡(luò),鏈表法構(gòu)建時間均遠(yuǎn)小于賭輪法。為了更適應(yīng)實際應(yīng)用,下一步將采用邏輯回歸模型的方式對超網(wǎng)絡(luò)進(jìn)行連接。