具有雙峰特性的雙層超網絡模型*

盧文 趙海興 孟磊 胡楓?

1) (陜西師范大學計算機科學學院,西安 710119)

2) (青海師范大學計算機學院,西寧 810008)

3) (青海省藏文信息處理與機器翻譯重點實驗室,西寧 810008)

4) (藏文信息處理教育部重點實驗室,西寧 810008)

隨著社會經濟的快速發展,社會成員及群體之間的關系呈現出了更復雜、更多元化的特點.超網絡作為一種描述復雜多元關系的網絡,已在不同領域中得到了廣泛的應用.服從泊松度分布的隨機網絡是研究復雜網絡的開創性模型之一,而在現有的超網絡研究中,基于ER隨機圖的超網絡模型尚屬空白.本文首先在基于超圖的超網絡結構中引入ER隨機圖理論,提出了一種ER隨機超網絡模型,對超網絡中的節點超度分布進行了理論分析,并通過計算機仿真了在不同超邊連接概率條件下的節點超度分布情況,結果表明節點超度分布服從泊松分布,符合隨機網絡特征并且與理論推導相一致.進一步,為更準確有效地描述現實生活中的多層、異質關系,本文構建了節點超度分布具有雙峰特性,層間采用隨機方式連接,層內分別為ER-ER,BA-BA和BA-ER三種不同類型的雙層超網絡模型,理論分析得到了三種雙層超網絡節點超度分布的解析表達式,三種雙層超網絡在仿真實驗中的節點超度分布均具有雙峰特性.

1 引 言

復雜網絡作為描述和分析現實生活中真實網絡的網絡系統,在不同領域中得到了廣泛的應用并取得了豐碩的成果[1-8].隨著社會經濟的快速發展,現實生活中的網絡呈現出了關系更復雜、節點屬性更多元化的特點,而一般的復雜網絡難以全面、準確地刻畫現實網絡的特征.鑒于超網絡具有大數據、復雜性、多維性和多層次等特點,使得描述和分析關系更復雜、節點屬性更多元化的網絡具有一定的實際應用價值[9-12].例如,在航空超網絡和鐵路超網絡之間根據乘客換乘行為依次連接機場和鐵路站點,形成“航空-鐵路”雙層超網絡模型并在此網絡模型的結構基礎之上,利用超圖理論優化交通規劃和乘客換乘行為.如圖1所示,第一層超網絡為航空超網絡,其中超邊A1表示航班,包含的節點a1,a2和a3表示該航班經過的三個機場； 第二層超網絡為鐵路超網絡,其中超邊R1為鐵路運營線路,

包含的節點b1,b2,b3,b4,b5,b6和b7表示該趟列車途經的站點.兩層超網絡之間的超邊C1表示乘客乘坐動車在b4站下車后可以選擇a2或a3機場換乘飛機,超邊C2表示若乘客乘坐動車在b20或b21站下車,如果打算繼續換乘飛機那么就只能選擇a6機場.

近年來,基于超圖的超網絡研究主要分為超網絡的實際應用和模型構建兩個方面.Estrada等[13]對超網絡的子圖中心度和聚集系數進行了系統研究,并采用超網絡描述了馬來西亞熱帶雨林中的食物網絡,通過分析得到了食物競爭關系.Ghoshal等[14]提出并利用隨機三部超圖對社會化標簽網絡中的資源、用戶和標簽三類節點的度分布進行了理論分析,得到了一些重要的結果.Zlati?等[15]在三部隨機超圖的基礎之上,擴展了超度分布、節點相似性和節點間最短路徑等拓撲指標的定義,為進一步研究社會化標簽網絡提供了一個標準工具.Zhang和Liu[16]提出了一種社會化標簽網絡的三部超圖演化模型,研究了該模型的超度、聚集系數和平均路徑長度等拓撲特性,并與實證數據做了對比.Wang等[17]和胡楓等[18]構建了基于超圖理論的無標度超網絡演化模型,理論分析了該超網絡模型的節點超度分布服從冪律分布,并通過仿真實驗驗證了理論分析結果.郭進利等[19,20]將文獻[17]和文獻[18]提出的超網絡模型進行了統一,分析了該統一超網絡的無標度特性演化機理和拓撲特性.Zhou等[21]構建了一種同時考慮新超邊增加和已存在超邊消失的超網絡模型.李甍娜等[22]以唐詩為節點,以韻母為超邊構建了唐詩超網絡,發現該超網絡服從無標度分布且具有較高的聚集性和異配性.胡楓等[23]構建了蛋白復合物超網絡模型,并分析得出了識別關鍵蛋白的方法.與此同時,多層超網絡的發展也極為迅速.方錦清等[24,25]從多角度出發思考和探索了多層超網絡,提出了三層超網絡演化模型,定義了兩種層次交叉度,并用其描述了層間節點的合作競爭關系和超網絡的魯棒性.Boccaletti等[26]詳細描述了多層網絡,并從基本結構入手分析了多層網絡的動態變化過程.蔣文君等[27]就多層網絡級聯失效的預防和級聯失效后的恢復做了整體性討論.楊喜艷等[28]基于馬爾科夫鏈方法建立了雙層謠言傳播網絡模型,并提出了一種能夠有效阻止多層社交網絡謠言傳播的動態控制策略.

圖1 “航空-鐵路”雙層超網絡模型Fig.1.Airline-Railway double-layer hyper network.

網絡模型既可以刻畫網絡的結構特征,也可分析網絡的動力學.ER隨機網絡模型是由匈牙利數學家Erd?s和Rényi在[29]20世紀50年代末提出的,是復雜網絡和現實生活中最為常用的一種隨機網絡模型.近年來,ER隨機網絡在不同領域得到了廣泛的研究與應用,Xu[30]在ER隨機網絡模型中研究了經典的量子游走問題,結果表明,量子在游走過程中的返回概率,即在初始節點找到量子的概率正比于ER隨機網絡的邊連接概率,且當ER隨機網絡趨于全連通時,其返回概率會出現激增的現象.Xue[31]在ER隨機網絡中利用大數定律改進了SIR傳播模型.Lima等[32]在有向ER隨機網絡上研究了多數投票模型,通過蒙特卡羅模擬得到了“有序-無序”相變的關鍵參數.Zehmakan[33]將社會網絡抽象為ER隨機網絡,發現了社會成員的觀念在網絡連通性達到某個閾值時會發生改變.李炎等[34]研究了ER隨機網絡中的Achlioptas爆炸滲流模型的相變性質,結果表明,ER隨機網絡中的爆炸滲流相變是一種奇異相變,它既不是標準的不連續相變,又與常規隨機滲流表現出的連續相變處于不同的普適類.在經濟快速發展和“大數據”時代的社會背景下,超網絡已經成為了網絡科學的重要研究方向之一,為更好地應用超網絡,超網絡模型的構建是不能忽略的.目前,超網絡模型的研究成果主要集中在無標度超網絡模型的構建中,對基于ER隨機圖理論的ER隨機超網絡模型研究尚屬空白.本文針對此問題,首先提出了一種ER隨機超網絡模型的構建方法,并分析得出了節點超度分布的解析表達式,仿真實驗結果表明,本文提出的ER隨機超網絡的節點超度分布服從泊松分布,符合隨機網絡特征并與理論推導一致.為描述更為復雜的多層、異質關系的網絡,進一步構建了節點超度分布具有雙峰特性,層間采用隨機方式連接,層內分別為 ER-ER,BA-BA 和 BA-ER 三種不同類型的雙層超網絡模型,理論分析得到了三種雙層超網絡節點超度分布的解析表達式,并通過仿真實驗對其進行了驗證.

2 ER 隨機超網絡

2.1 ER隨機超網絡模型的構建方法

在超圖結構中引入ER隨機圖理論,提出了一種ER隨機超網絡模型,記為H(N,p) ,構建過程如下：

1)初始化： 給定節點數量N和超邊連接概率p,p∈[0,1]；

2)在N個節點中任意選擇r個不相同的節點,r≤N；

3) 生成一個隨機數s,s∈(0,1) ；

4)如果s＜p,將第2步中選擇的r個節點組成一條超邊；

5)重復2)—4)步,直至所有的r個不相同的節點都被選擇一次.

在以上的構建過程中,由于每次選擇r個節點形成一條超邊,因此本模型構建的超網絡為r均勻超網絡.最終生成的超邊數量

2.2 ER隨機超網絡節點超度分布理論分析

在本文提出的ER隨機超網絡中,一個節點與其他r-1 個節點組成一條超邊的概率為pk(1-p)F-k,其中則網絡中一個給定節點超度為k的概率分布為：

網絡節點的平均超度為

所以,當ER隨機超網絡的節點數N較大并且超邊連接概率p較小時,節點超度為k的二項分布近似為泊松分布：

其中,〈λ〉=p×F.

2.3 仿真實驗

圖2 為N=500 ,r=3 時,在超邊連接概率p=0.004,p=0.006 ,p=0.008 和p=0.01 四種不同條件下取100次平均值的節點超度分布情況.

圖2 500 個節點的隨機 3 均勻超網絡在不同連接概率 p 值時的節點超度分布 (a) p =0.004 ； (b) p =0.006 ； (c) p =0.008 ；(d)p=0.01Fig.2.The hyper degree distribution of 3-uniform random hyper networks under different p： (a) p =0.004 ； (b) p =0.006 ；(c) p =0.008 ； (d) p =0.01 .

從圖2(a)—圖2(d)可以看出,本文提出的ER隨機超網絡模型的節點超度分布在四種不同超邊連接概率條件下均服從泊松分布并與理論分析結果一致,符合隨機網絡特征.

3 雙層超網絡模型

超網絡在描述復雜多元關系的系統時有著較強的優勢,而隨著一些實際研究工作的展開,我們發現單層超網絡在描述多層異質關系時會略顯不足.例如在交通網絡中,如何準確地描述航空超網絡和鐵路超網絡之間的關系等.針對此類問題,本文構建了節點超度分布具有雙峰特性的雙層超網絡模型,層間采用隨機方式連接,層內分別為ERER,BA-BA和BA-ER三種不同類型的雙層超網絡模型(簡記為EE,BB和BE,其中E代表本文提出的ER隨機超網絡； B代表BA 無標度超網絡).本文以雙層3均勻超網絡為例,分析三種不同類型的雙層超網絡模型.

3.1 EE雙層3均勻超網絡

EE雙層3均勻超網絡包含兩層ER隨機3均勻超網絡,層與層之間采用隨機連接方式.

3.1.1 構建方法

EE雙層3均勻超網絡模型的構建過程如下：

1) 采用本文提出的ER隨機超網絡模型H(N,p)構建第一層和第二層超網絡H1(N1,p1) 和H2(N2,p2) ；

2) 層間連接： 采用隨機方式連接層間,即第一層中的任意一個節點與第二層中的任意兩個不相同節點以概率p12組合生成一條超邊,直至層間形成條超邊為止.

3.1.2 理論分析

根據以上構建方法中的第2步可知,EE雙層超網絡的節點平均超度〈k〉由第一層超網絡的節點平均超度〈k1〉和第二層超網絡的節點平均超度〈k2〉決定.其中,EE雙層超網絡中第一層網絡中的任意一個節點與層內其他任意兩個節點形成超邊的數量為與第二層超網絡中的任意兩個節點形成超邊的數量為同理,第二層超網絡中任意一個節點在層內形成的超邊數量為第二層超網絡中任意兩個節點與第一層超網絡中任意一個節點形成超邊的數量為N2(N2-1)p12,故第一層和第二層超網絡節點平均超度的計算表達式為：

式中,N1和N2分別為第一層和第二層超網絡的節點數,p1和p2分別為第一層和第二層超網絡的層內超邊連接概率,p12為層間超邊連接概率.由(4)式和(5)式可得

EE雙層超網絡的節點超度分布由第一層超網絡的節點超度分布p1st(k) 和第二層超網絡的節點超度分布p2nd(k) 組成.第一層超網絡中任意一個節點與其他兩個節點組成一條超邊的概率為p1i(1-p1)F1-i,其中與第二層超網絡中的任意兩個節點組成一條超邊的概率為(1-p12)Q1-(k-i),其中由此可以得出第一層超網絡中節點超度為k的概率分布為

同理,第二層超網絡中節點超度為k的概率分布為

3.1.3 仿真實驗

在EE雙層超網絡節點超度分布仿真實驗中,N1和N2取值為 500,層內連接概率p1和p2為 0.006,層間連接概率p12分別為0.001和0.01,為了結果的合理有效,實驗結果取了100次的平均值.

表1為EE雙層超網絡節點超度分布實驗的統計信息,其中N代表雙層網絡的總節點數,M為層間的超邊數量.實驗結果表明,EE雙層超網絡的節點超度分布在不同層間超邊連接概率條件下均具有雙峰特性,如圖3(a)和圖3(b)所示.

表1 EE 雙層 3 均勻超網絡實驗統計Table 1.Experimental statistics of EE hyper network.

圖3 雙層3均勻EE超網絡在不同層間超邊連接概率時的節點超度分布 (a) p 12=0.001 ； (b)p12=0.01Fig.3.The EE hyper degree distribution of double-layer 3-uniform hyper network under different p 12 ： (a) p 12=0.001 ；(b) p 12=0.01 .

3.2 BB雙層3均勻超網絡

BB雙層3均勻超網絡包含兩層3均勻無標度超網絡,層與層之間采用隨機連接方式.在構建3均勻無標度超網絡時,采用文獻[17]提出的均勻無標度超網絡模型構建方法,記為H(m0,m) .該超網絡模型的節點超度分布服從冪律分布,符合無標度網絡特征.H(m0,m) 模型的構建過程如下：

1) 初始化： 給定初始m0個節點{v1,v2,v3,···,vm0}與一條包含這些節點的超邊E0={v1,v2,v3,···,vm0}；

2) 超邊增長： 每個時間步t添加m個節點{vt1,vt2,vt3,···,vtm}與一個已存在的節點vi組合成一條新的超邊Et={vt1,vt2,vt3,···,vtm,vi}.這個已存在節點的選取方式為“超度優先連接”,即節點vi被選中的概率正比于這個節點的超度,定義為：

式中,分子dH(vi) 為節點vi的超度,分母表示當前網絡中所有節點超度之和.在該均勻無標度超網絡中,一個給定節點超度為k的概率分布為[18]

式中,m為每次添加新節點的個數,當m=2 時,該超網絡為3均勻無標度超網絡.

3.2.1 構建方法

BB雙層3均勻超網絡模型的構建過程如下：

1) 采用H(m0,m) 模型構建第一層和第二層3均勻無標度超網絡H1(m10,m1) 和H2(m20,m2) ；

2) 層間連接： 采用隨機方式連接層間,即第一層中的任意一個節點與第二層中的任意兩個不相同節點以概率p12組合生成一條超邊,直至形成條超邊為止.

3.2.2 理論分析

由于第一層與第二層超網絡均為3均勻無標度超網絡,每次增加2個新節點與1個已存在節點組合生成一條超邊,所以在層間連接之前,各層超網絡的節點平均超度約為 3 /2 .由此可得,第一層超網絡的節點平均超度〈k1〉和第二層超網絡的節點平均超度〈k2〉分別為：

其中,N2為第二層超網絡的節點數,則BB超網絡的節點平均超度.

在具有N個節點的3均勻無標度超網絡中,超度為1的節點數M(1) 的上下界為N/2+1≤M(1)≤N-1,超度為 2 的節點數M(2) 的上界為M(2)≤N/2.所以,BB 雙層超網絡的第一層超網絡中節點超度為k的概率分布為

同理,第二層超網絡中節點超度為k的概率分布為

3.2.3 仿真實驗

在BB雙層超網絡節點超度分布的仿真實驗中,第一層與第二層超網絡的節點數N1=m10+m1和N2=m20+m2取值為500,其中各層初始節點m10和m20均為 3,層間連接概率p12分別為 0.001和0.01,為了結果的合理有效,實驗結果取了100次的平均值.

表2為BB超網絡節點超度分布實驗的統計信息.與EE雙層超網絡的結果相同,BB雙層超網絡的節點超度分布在不同層間超邊連接概率條件下均具有雙峰特性,如圖4(a)和圖4(b)所示.

3.3 BE雙層3均勻超網絡

BE雙層3均勻超網絡由第一層3均勻無標度超網絡和第二層ER隨機3均勻超網絡組成,層與層之間采用隨機連接方式.

表2 BB 雙層 3 均勻超網絡實驗統計Table 2.Experimental statistics of BB hyper network.

3.3.1 構建方法

BE雙層3均勻超網絡模型的構建過程如下：

1)采用H(m0,m) 模型構建第一層超網絡H1(m10,m1)；

2)采用H(N,p) 模型構建第二層超網絡H2(N2,p2)；

3) 層間連接： 采用隨機方式連接層間,即第一層中的任意一個節點與第二層中的任意兩個不相同節點以概率p12組合生成一條超邊,直至形成條超邊為止.

3.3.2 理論分析

BE雙層超網絡的節點平均超度〈k〉由第一層無標度超網絡的節點平均超度〈k1〉和第二層ER隨機超網絡的節點平均超度〈k2〉決定,分別為：

其中,N2為第二層超網絡的節點數,p2為第二層超網絡的層內超邊連接概率,p12為層間超邊連接概率,則〈k〉=(〈k1〉×N1+〈k2〉×N2)/(N1+N2) .

BE雙層超網絡的節點超度分布與EE雙層超網絡和BB雙層超網絡類似,由第一層無標度超網絡的節點超度分布和第二層ER隨機超網絡的節點超度分布組成.第一層超網絡中節點超度為k的概率分布為

第二層超網絡中節點超度為k的概率分布為

3.3.3 仿真實驗

在BE雙層超網絡的節點超度分布實驗中,第一層與第二層超網絡的節點數N1=m10+m1和N2取值為500,其中第一層超網絡的初始節點m10為3,第二層超網絡的超邊連接概率p2為0.006,層間連接概率p12分別為0.001和0.01,為了結果的合理有效,實驗結果取了100次的平均值.

表3為BE超網絡節點超度分布實驗的統計信息.BE雙層超網絡的節點超度分布與以上兩種類型的雙層超網絡情況相同,在不同的層間超邊連接概率的條件下,節點超度分布均具有雙峰特性,如圖5(a)和圖5(b)所示.

圖4 雙層 3 均勻 BB 超網絡節點超度分布 (a)p12=0.001； (b)p12=0.01Fig.4.The BB hyper degree distribution of double-layer 3-uniform hyper network under different p 12 ： (a) p 12=0.001 ；(b) p 12=0.01 .

圖5 雙層3均勻BE超網絡模型節點超度分布 (a)p12=0.001； (b)p12=0.01Fig.5.The BE hyper degree distribution of double-layer 3-uniform hyper network under different p 12 ： (a) p 12=0.001 ；(b) p 12=0.01 .

表3 BE 雙層 3 均勻超網絡實驗統計Table 3.Experimental statistics of BE hyper network.

4 結 論

本文基于經典的ER隨機模型構建了基于超圖的ER隨機超網絡模型,通過理論分析得到了該模型的節點超度分布其中泊松分布的期望值λ與超邊連接概率p有關,計算機仿真實驗結果與理論分析一致.與普通的ER隨機網絡相比,本文提出的ER隨機超網絡模型對于描述和分析關系更復雜、節點屬性更多元化的隨機社會網絡具有一定的實際應用價值.同時,在ER隨機超網絡模型的基礎之上,構建了 ER-ER,BABA和BA-ER三種不同類型的雙層超網絡模型.理論分析發現,三種雙層超網絡的節點平均超度與層間超邊連接概率密切相關,隨著層間超邊連接概率的增大網絡節點的平均超度也隨之增大； 仿真實驗結果表明,三種模型的節點超度分布在不同的層間超邊連接概率條件下均具有雙峰特性.

本文提出的ER隨機超網絡模型和雙層超網絡模型對今后進一步研究此類超網絡的熵、超網絡動力學、超網絡表示學習、超網絡鏈路預測和交通超網絡優化等提供了理論基礎,對研究多層超網絡的演化具有一定的借鑒意義.