超網絡模型構建中優先連接方法研究

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

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

0 概述

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

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

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

上述超網絡演化模型均是基于優先連接構建得到的,這種優先連接機制使得被選擇的舊節點超度大于新節點,且超度分布符合冪律分布。本文通過分析現有超網絡模型演化過程,采用賭輪法和鏈表法對優先選擇進行了詳細描述,利用基于這2種方法構建的均勻超網絡模型和隨機超網絡模型,分析這2種超網絡模型超度冪律分布斜率的規律性質,并且討論了參數的取值對模型構建的影響。

1 超網絡

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

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

2 超網絡模型構建方法

2.1 均勻超網絡演化模型

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

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

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

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

2.2 隨機超網絡演化模型

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

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

上述3種超網絡模型是通過網絡的拓撲結構而構建的,根據不同結構構建的基于超圖結構的超網絡模型,且均勻超網絡模型和隨機超網絡模型都是通過優先連接策略構建得到的。

3 優先連接策略

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

(1)

在超網絡模型構建方法中,通過改變超網絡模型演化過程中節點的增加與選擇,構建出不同的超網絡演化模型。近年來,對超網絡模型演化過程中節點的增加方式研究較多,而對如何實現在演化過程中的優先連接沒有具體說明。下文對在超網絡模型演化中實現優先連接策略的賭輪法和鏈表法進行介紹。

3.1 賭輪法

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

(2)

賭輪法的過程是假設群體中全部個體都是適當性分數,由一張餅圖構成,群體中每一個個體為餅圖中指定的小塊,塊的大小與個體的適應性分數成比例,適應性分數越高,則其在餅圖中對應的小塊面積越大。在對個體進行選擇時,旋轉該輪子直至輪盤停止,看指針停在哪一塊,就選中與之對應的個體。

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

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

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

賭輪法核心偽代碼如下:

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

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)已經被選擇過的舊節點不能再被重新選擇。

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 鏈表法

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

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

鏈表法核心偽代碼如下:

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

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)控制已經被選擇過的舊節點不能再被重新選擇。

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 超網絡仿真實驗

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

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

圖3 均勻超網絡中舊節點選擇數量的影響Fig.3 Influence of the number of old nodes selected in uniform hypernetwork

圖4 均勻超網絡中新節點添加數量的影響Fig.4 Influence of the number of new nodes added in uniform hypernetwork

圖5 均勻超網絡中網絡規模的影響Fig.5 Influence of the network scale in uniform hypernetwork

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

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

圖6 隨機超網絡中舊節點選擇數量的影響Fig.6 Influence of the number of old nodes selected in random hypernetwork

圖7 隨機超網絡中新節點添加數量的影響Fig.7 Influence of the number of new nodes added in random hypernetwork

圖8 隨機超網絡中網絡規模的影響Fig.8 Influence of the network scale in random hypernetwork

通過以上對比發現,利用賭輪法和鏈表法構建的均勻超網絡和隨機超網絡的超度在雙對數坐標系下均呈冪律分布,且表現出無標度特征。不論是均勻超網絡還是隨機超網絡,在相同實驗條件下,賭輪法和鏈表法的實驗結果基本相同,且相差不大。

在當今大數據時代,超網絡規模越來越大,為了在有限時間內得到更多的有效網絡信息,高效的優先連接機制方法愈發重要。因此,通過本文實驗分析發現,鏈表法比賭輪法更適合網絡規模較大的超網絡模型構建。

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

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

5 運行時間對比

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

通過表2還可以看出,當改變均勻超網絡和隨機超網絡舊節點個數時,隨著舊節點個數的增加,超網絡的構建時間也隨之增加;當改變均勻超網絡和隨機超網絡新節點個數時,隨著新節點個數的增加,超網絡的構建時間反而縮短;當改變均勻超網絡和隨機超網絡最終的網絡規模時,隨著最終網絡規模的增加,超網絡的構建時間大幅增長。

表2 超網絡模型構建時間對比Table 2 Comparison of construction time of hypernetwork model s

6 結束語

本文采用賭輪法和鏈表法詳細闡述了超網絡模型演化的優先選擇過程,利用這2種方法構建均勻超網絡和隨機超網絡模型,并對其特性進行分析。賭輪法和鏈表法構建的超網絡模型超度分布呈冪律分布,且顯示無標度特性,說明賭輪法和鏈表法構建超網絡模型是可行的。實驗結果表明,合理設置構建超網絡模型時的新舊節點個數,可得到任意標度指數的無標度超網絡。通過超網絡模型構建時間對比發現,對于均勻超網絡與隨機超網絡,鏈表法構建時間均遠小于賭輪法。為了更適應實際應用,下一步將采用邏輯回歸模型的方式對超網絡進行連接。