馬飛,姚兵
(西北師范大學數(shù)學與統(tǒng)計學院, 甘肅 蘭州 730070)
雙優(yōu)無標度網(wǎng)絡模型*
馬飛,姚兵
(西北師范大學數(shù)學與統(tǒng)計學院, 甘肅 蘭州 730070)
基于標準的無標度網(wǎng)絡模型,首先擴展了網(wǎng)絡增長的“優(yōu)先連接機制”原則,從更一般的情形出發(fā),設立不同約束條件下的點優(yōu)先連接概率,既而建立了更一般的網(wǎng)絡動力系統(tǒng)所符合的偏微分方程,給出無標度網(wǎng)絡的一個拓撲性質(zhì)。然后,給出了一種更加符合現(xiàn)實的擇優(yōu)概率,接著,建立了一類更一般的網(wǎng)絡演化模型,并討論了它的無標度特性,得到它的冪率指數(shù)γ在1~4之間。
無標度網(wǎng)絡模型;動態(tài)演化;偏微分方程;六度分離
我們生活的世界中充滿了無數(shù)的網(wǎng)絡,如細胞中的新陳代謝網(wǎng)、大腦中的神經(jīng)網(wǎng)、生態(tài)系統(tǒng)中的食物鏈網(wǎng)、社會關系網(wǎng)絡、科研合作網(wǎng)絡、經(jīng)貿(mào)互惠網(wǎng)絡、互聯(lián)網(wǎng)、萬維網(wǎng)以及電力網(wǎng)和交通運輸網(wǎng)等等。這些網(wǎng)絡都能被抽象成網(wǎng)絡模型——圖,起初研究者們運用圖論的方法做研究,但是圖論中研究的圖形大多都是規(guī)則的、單一的,但真實網(wǎng)絡的結(jié)構(gòu)不僅很復雜的,而且構(gòu)成網(wǎng)絡的節(jié)點數(shù)目也是很龐大的,這樣一來,網(wǎng)絡研究對傳統(tǒng)經(jīng)典圖論的發(fā)展提出了新的要求。上世紀50年代,Erd?s等基于經(jīng)典圖論的研究,提出了隨機網(wǎng)絡模型(ER模型)該模型能很好的體現(xiàn)網(wǎng)絡的隨機性,但是節(jié)點的度(與節(jié)點相連接的邊的數(shù)目)之間相差不大,幾乎相等,度分布服從Poisson分布,其圖像是一條鐘型曲線。顯然,真實網(wǎng)絡中節(jié)點的度并不是相等的。為了解釋蘊含在網(wǎng)絡中的規(guī)律,Watts等[1-2]提出了小世界網(wǎng)絡模型,該模型在繼承了隨機網(wǎng)絡模型的隨機性后,出現(xiàn)了新的網(wǎng)絡拓撲性質(zhì):屬于該網(wǎng)絡模型中初始節(jié)點的度相對要大一些,它的度分布呈現(xiàn)出指數(shù)衰減。1999年,基于萬維網(wǎng)拓撲結(jié)構(gòu)的研究,Barabási等[3]發(fā)現(xiàn)鐘型曲線消失了,出現(xiàn)了一條遞減的曲線,為了刻畫這一結(jié)果,他們首次提出了無標度網(wǎng)絡模型(BA-模型),該模型滿足冪率分布式
P(k)≈k-γ
(1)
其中γ叫做無標度指數(shù),它的取值范圍是2<γ<3。在他們首創(chuàng)性的研究工作之后,復雜網(wǎng)絡的研究得到了眾多科研人員的重視,經(jīng)過大量研究后發(fā)現(xiàn):生活中大量的網(wǎng)絡都具有無標度特性(scale-freeproperty),即服從冪率分布(1),但部分真實網(wǎng)絡的冪律指數(shù)γ的取值范圍卻超出了2~3,落在1~4之間[4]。通過計算機仿真模擬后,確實證明了這一點[5-7]。
近年來,國內(nèi)外的研究人員對BA-模型進行了不同層次的推廣和拓展,得到的成果頗多。但在這些研究中,人們認同網(wǎng)絡中存在“先到先得,富者越富,適者更富”現(xiàn)象。針對這種現(xiàn)象,總結(jié)得出具有無標度特性的網(wǎng)絡演化(增長)必須滿足2條性質(zhì):均勻增長和擇優(yōu)連接。特別是擇優(yōu)連接方式對一個演化的網(wǎng)絡是否具有無標度特性起到?jīng)Q定性的作用,已證實運用線性擇優(yōu)連接方式將會得到無標度網(wǎng)絡,非線性的擇優(yōu)連接方式將會影響到網(wǎng)絡的度分布,使其不再服從冪率分布[8]。
在Barabási等[3]提出無標度網(wǎng)絡模型(BA-模型)之后,研究人員不論是采取理論研究手段,還是采用計算機仿真模擬,他們對網(wǎng)絡動態(tài)演化的描述與刻畫都存在著相似之處[4],都是討論隨著時間的延續(xù),網(wǎng)絡中不斷地會有外界新的節(jié)點進入,同時,網(wǎng)絡自身內(nèi)部也發(fā)生著變化(如:網(wǎng)絡中未連邊的節(jié)點之間由于某種聯(lián)系而產(chǎn)生新的連邊),隨著這種演化方式的進行,網(wǎng)絡的規(guī)模會變得越來越龐大,但是這種增長方式不可能無休止地進行下去,在歷經(jīng)一段時間的增長后,網(wǎng)絡的規(guī)模就會趨于穩(wěn)態(tài)或衰退,即網(wǎng)絡中出現(xiàn)節(jié)點“湮滅”和舊邊被“刪除”。對一個最初具有m0個節(jié)點的網(wǎng)絡N(0)而言,假設它的動態(tài)演化是連續(xù)的,t時刻后,對網(wǎng)絡N(t)中一個度為ki(t)的節(jié)點,依據(jù)事件的獨立性給出一個動態(tài)方程[9]:
h*(t)+z*(t)+φ(t)
(2)
方程(2)右端有5個功能函數(shù):加點函數(shù)(優(yōu)先連接函數(shù))f*(t)=f(ap1(t)m,t,ki(t),∏1(ki))的含義是:t時刻有a個“新”節(jié)點進入到網(wǎng)絡N(t-1)中,每個“新”節(jié)點與網(wǎng)絡N(t-1)中已存在的節(jié)點間連接產(chǎn)生p1(tm條新邊(0 設方程(2)的解為ki(t)=θ(t,ti,α1,α2,…,αr),其中參數(shù)αi(i=1,2,…,r)與時間變量t和ti無關。進一步,得 P(ki(t) (t,ti,β1,β2, …,βr)) (3) 方程(3)中的參數(shù)βi(i=1,2,…,r)與時間變量t和ti均無關,上述方程(3)中的記號θ-1(t,ti,β1,β2,…,βr)表示函數(shù)ki(t)的反函數(shù)。解得網(wǎng)絡N(t)中頂點度數(shù)為k的概率 (4) 本文以文獻[6,10-12]中的結(jié)論來解釋由方程(2)所建立的模型,嘗試對復雜網(wǎng)絡進行綜合性的研究。包括演化網(wǎng)絡所符合的動態(tài)微分方程、擇優(yōu)連接方式、如何進行網(wǎng)絡之間比較、如何優(yōu)化網(wǎng)絡等方面,并建立一種冪律指數(shù)γ的取值范圍在1到4之間的無標度網(wǎng)絡模型(雙優(yōu)無標度網(wǎng)絡模型)。 通過對大量現(xiàn)實網(wǎng)絡的研究,人們認識到幾乎所有的網(wǎng)絡都表現(xiàn)出無標度特性,為了更好地模擬無標度網(wǎng)絡,從理論上出發(fā),研究者們建立研究方法,并通過計算機進行仿真模擬。然而經(jīng)驗告訴我們:網(wǎng)絡的動態(tài)演化中包含增長與衰退,許多研究學者都認為網(wǎng)絡以“擇優(yōu)”方式進行增長,以“反擇優(yōu)”方式進行衰退。在Barabási等[3]首次提出線性擇優(yōu)增長模型之后,研究者們依此為基礎,對“擇優(yōu)”方式進行了不斷地改進、完善,相應地建立了不同的網(wǎng)絡模型,從不同的側(cè)重點進行刻畫、模擬現(xiàn)實生活中已存在的網(wǎng)絡,并對網(wǎng)絡的動態(tài)演化特征做出一些相關的預測,同時也為建立新的更加健全的網(wǎng)絡模型提供理論支持。 在本文中,t時刻的網(wǎng)絡模型記為N(t),它的節(jié)點集合和邊集合分別是V(t)和E(t),網(wǎng)絡模型N(t)的節(jié)點個數(shù)是nv(t)=|V(t)|,它的邊數(shù)目是ne(t)=|E(t)|,ni(t)表示N(t)中節(jié)點度數(shù)為ki的節(jié)點數(shù)目。 3.1 陳慶華等模型 陳慶華等模型的演化算法[13]:步驟1、在已存在的節(jié)點中添加l條新邊:隨機選擇一個節(jié)點作為與新邊連接的起始點,點i被選擇作為新邊另一節(jié)點的概率滿足 (5) (6) (7) 由(7)式可得 (8) 3.2 梁洪振等模型 (9) (10) 由(10)式可得 m+2n-2c (11) 和式(11)的結(jié)果是一個常數(shù)。 3.3 賈秀麗等模型 以及φ(t)=0,易得網(wǎng)絡動態(tài)演化滿足下面的方程 (12) (解釋上式每一項的含義,第1項新節(jié)點加入到網(wǎng)絡中引起ki的變化,第2項是隨機刪除節(jié)點引起ki的變化,第3項是網(wǎng)絡擇優(yōu)加邊引起ki的變化(第一部分:節(jié)點i依擇優(yōu)概率∏(ki)被選作所加邊的起始節(jié)點時引起度發(fā)生變化;第二部分:節(jié)點i依擇優(yōu)概率∏(ki)被選作所加邊的另一節(jié)點時引起度發(fā)生變化),第4項是網(wǎng)絡反擇優(yōu)刪除邊引起ki的變化(第一部分:節(jié)點i依反擇優(yōu)概率p-1(ki)被選作所刪邊的起始節(jié)點時引起度發(fā)生變化;第二部分:節(jié)點i依反擇優(yōu)概率p-1(ki)被選作所刪邊的另一節(jié)點時引起度發(fā)生變化))。在t時刻節(jié)點的平均度為 將nv(t)、ne(t)代入方程(12),得到一階近似微分方程 (13) 因此 (14) 所以節(jié)點的度分布: 其中冪率指數(shù) 對(12)式求和,得到 (15) 當t→∞時, m+2r-2n 我們得到一個結(jié)論:在網(wǎng)絡動態(tài)演化的過程中,對相應的動態(tài)方程(2)求和后將等于一個常值M,并且M就等于每一時刻網(wǎng)絡的動態(tài)變化值。 針對現(xiàn)實生活中確實存在冪律指數(shù)γ>3的無標度網(wǎng)絡(例如:SexualContacts網(wǎng)絡的冪律指數(shù)γ=3.4[16],本文建立一類網(wǎng)絡模型,它不僅能很好的說明該類無標度網(wǎng)絡的存在性,而且還可以包含經(jīng)典的BA模型?;跇?gòu)造BA模型的均勻增長、優(yōu)先連接算法,幾乎當前所有的網(wǎng)絡模型都認為新節(jié)點的加入、新邊的產(chǎn)生都完全地遵循優(yōu)先連接,舊節(jié)點的刪除、舊邊的刪除都絕對地遵循反擇優(yōu)刪除。但是絕對的事實并非都完全成立,例如:在科學家合作網(wǎng)絡中,剛出道的年輕研究者往往渴望與著名專家合作,進行科研(只要有機會),但在隨機的情況下有時會與一位同樣年輕的研究者進行合作。這種現(xiàn)象在網(wǎng)絡演化模型中可以解釋為:剛進入網(wǎng)絡的新節(jié)點,在采用優(yōu)先連接概率與已存在于網(wǎng)絡中的舊節(jié)點連邊時,會隨機的與節(jié)點度數(shù)不大(甚至很小)的節(jié)點進行連邊運算,但是連邊的過程中優(yōu)先連接概率起主要的支配作用。同樣的道理,在刪除舊邊的過程中,并不是所有被刪除的邊都采用反擇優(yōu)概率,偶爾也會出現(xiàn)隨機刪邊的現(xiàn)象,但反擇優(yōu)概率在刪邊運算中起決定作用[17-20]。 鑒于此種現(xiàn)象的確存在,本文提出了優(yōu)選優(yōu)先連接概率與優(yōu)選反擇優(yōu)刪除概率。如下: ①優(yōu)選優(yōu)先連接概率 ∏1=α∏11+(1-α)∏12 其中∏11表示優(yōu)先連接概率,∏12表示隨機連接概率,參數(shù)α(1/2≤α≤1)意指“優(yōu)選”,即在概率∏1中,∏11起支配作用。 ②優(yōu)選反擇優(yōu)刪除概率 ∏2=(1-β)∏21+β∏22 其中∏21表示反擇優(yōu)概率,∏22表示隨機刪除概率,參數(shù)β(0≤β≤1/2)意指“優(yōu)選”,即在概率∏2中,∏21起支配作用。 按照上面的優(yōu)選優(yōu)先連接概率與優(yōu)選反擇優(yōu)刪除概率,本文構(gòu)造了如下的雙優(yōu)無標度網(wǎng)絡模型N(t):初始網(wǎng)絡N(0)是具有m0個節(jié)點、n0條邊的簡單連通圖。從t>1時刻起,網(wǎng)絡模型將執(zhí)行以下兩個操作進行演化。 1) 優(yōu)選優(yōu)先連接(1/2≤α≤1):t時刻有a個節(jié)點加入網(wǎng)絡N(t-1)中,每個新節(jié)點分別采用優(yōu)選優(yōu)先連接概率∏1與已存在于網(wǎng)絡模型中的m個不同節(jié)點連邊。度數(shù)為ki的舊節(jié)點獲得與新節(jié)點連邊的概率滿足如下關系: ∏1=α∏11+(1-α)∏12= 2)優(yōu)選反擇優(yōu)刪除(0≤β≤1/2):t時刻有b條邊從網(wǎng)絡N(t-1)中分別采用優(yōu)選反擇優(yōu)概率∏2被刪除。每條被刪除邊的一個節(jié)點隨機選取,選擇另一個節(jié)點時按優(yōu)選反擇優(yōu)概率 ∏2=(1-β)∏21+β∏22= 經(jīng)歷這樣的t次演化后,網(wǎng)絡模型N(t)具有m0+at個節(jié)點和n0+(am-b)t條邊。顯然當參數(shù)a=1,b=0,α=1,β=0時,該網(wǎng)絡模型就退化成BA-模型。 假設ki是連續(xù)實變量,根據(jù)模型的演化機理,在方程(2)中,取加點函數(shù) 刪邊函數(shù) 刪邊函數(shù)z*(t)中的第1項b/{n0+amt-bt}表示節(jié)點i被隨機選中作為起始節(jié)點時引起度的變化,第2項b∏2表示節(jié)點i被采用優(yōu)選反擇優(yōu)刪除概率選中作為另一節(jié)點時引起度的變化,g*(t)=h*(t)=φ(t)=0。則有如下動態(tài)方程: (16) 進一步可得: M(t)ki+R(t) 在初始條件ki(ti)=m下,上述一階微分方程的通解為: (17) 其中h=amα-bβ,l=2(am-b)。網(wǎng)絡中任選一個節(jié)點度數(shù)為ki(t)且不超過k的概率可以被寫成如下: (18) 假設插入“新”節(jié)點到網(wǎng)絡中的時間t服從均勻分布,即P(ti)=1/(m0+t),便可得到節(jié)點的度分布函數(shù) (19) 當t充分大時, 網(wǎng)絡度分布服從冪率分布,且冪率指數(shù) 現(xiàn)對該雙優(yōu)無標度網(wǎng)絡模型的冪律指數(shù)γ=l/h+1進行分析。當α=1/2,β=1/2時,γ=l/h+1=4;當α=1,β=0時,γ=l/h+1<3;當α=2/3,β=1/3時,γ=l/h+1=3。所以冪律指數(shù)γ的范圍為 對(16)式進行求和計算得 (20) 當t充分大時,(20)式的左端趨近于常數(shù) 本文提出了一種新的擇優(yōu)連接規(guī)則,開始嘗試用純數(shù)學方法(動力系統(tǒng)+偏微分方程)來解釋網(wǎng)絡演化的動態(tài)特征,通過對幾類特殊動態(tài)網(wǎng)絡演化模型的理論分析,進一步的說明用偏微分方程去刻畫這一動力系統(tǒng)的必要性和重要性。然后依據(jù)本文中的分析建立了一類新的網(wǎng)絡模型,不僅討論了它的無標度特性,同時也驗證了新發(fā)現(xiàn)——對動態(tài)方程(2)求和后值將是一個常數(shù)。作為今后的研究,提出下面的問題: 問題1 如何優(yōu)化網(wǎng)絡?前期對擇優(yōu)率(增長)的大量研究都局限于線性結(jié)構(gòu),是否生活中的網(wǎng)絡都是線性擇優(yōu)增長的?為此,本文分析了一類簡單的非線性擇優(yōu)增長率 (21) 問題 2 從不同的考察角度和側(cè)重點,研究者們建立的各種模型都是基于方程(2)中概率參數(shù)pi(t)=1(i=1,2,3,4),在這種極為特殊的情形下,問題的討論將變得具體、可操作,但現(xiàn)實生活中網(wǎng)絡的演化是相當復雜的,每一時刻進入網(wǎng)絡的節(jié)點數(shù)目、從網(wǎng)絡中“湮沒”的節(jié)點數(shù)目、網(wǎng)絡中刪除“舊”邊的數(shù)目、網(wǎng)絡中重新連接邊的數(shù)目等都是變化的,所以有必要研究方程(2)中諸概率參數(shù)pi(t)=1(i=1,2,3,4)不是定值的網(wǎng)絡演化情形。 注意根據(jù)六度分離定理,忽略與節(jié)點i距離超過6的節(jié)點的影響系數(shù),那么就可以定義關于節(jié)點i的擇優(yōu)概率為 (22) 選取,式中?i表示與節(jié)點i之間距離為1的節(jié)點構(gòu)成的集合(也稱節(jié)點i的1-鄰居集)。如果網(wǎng)絡中已存節(jié)點間要有新邊產(chǎn)生時,新邊的一個節(jié)點可以隨機選擇,完美的情形下另一個節(jié)點應該是r(1 [1]WATTSDJ,STROGATZSH.Collectivedynamicsofsmall-worldnetworks[J].Nature, 1998, 393:440-442. [2]WATTSDJ.Smallworlds:thedynamicsofnetworksbetweenorderandrandomness[M].Princeton:PrincetonUniversityPress, 1999. [3]BARABSIAL,ALBERTR,JEONGH.Mean-fieldtheoryforscale-freerandomnetworks[J].PhysicaAStatisticalMechanics&ItsApplications, 1999, 272(1/2): 173-187. [4] 劉浩廣, 蔡紹洪, 張玉強. 無標度網(wǎng)絡模型研究進展[J]. 大學物理, 2008, 27(4): 43-47.LIUHG,CAISH,ZHANGYQ.Theresearchonthescale-freenetworksmodel[J].CollegePhysics, 27(4): 43-47. [5]YAOB,LIUX,ZHANGWJ,etal.ApplyingGraphtheorytotheInternetofThings[C]//IEEEInternationalConferenceonHighPerformanceComputingandCommunications, 2013: 2354-2361. [6]YAOB,YAOM,CHENXE,etal.Researchonedge-growingmodelsrelatedwithscale-freesmall-worldnetworks[J].AppliedMechanics&Materials, 2014, 513-517: 2444-2448. [7]YAOB,YANGC,YAOM,etal.Graphsasmodelsofscale-freenetworks[J].AppliedMechanics&Materials, 2012, 380-384: 2720-2723. [8]KRAPIVSKYPL,REDNERS,LEYVRAZF.Connectivityofgrowingrandomnetworks[J].Physics, 2000, 85(21): 4629-4632. [9]MAF,SUJ,YAOB,etal.Scale-freenetworkmodelswithparameters[C].JointInternationalInformationTechnology,MechanicalandElectronicEngineeringConference, 2016, 59: 155-162. [10]SONGC,KORENT,WANGP,etal.Modellingthescalingpropertiesofhumanmobility[J].NaturePhysics, 2010, 6(10): 818-823. [11]YANG,TSEKENISG,BARZELB,etal.Spectrumofcontrollingandobservingcomplexnetworks[J].NaturePhysics, 2015, 11(9): 779-786. [12]DELGENIOCI,GROSST,BASSLERKE.Allscale-freenetworksaresparse[J].PhysicalReviewLetters, 2011, 107(17): 178701-178701. [13]CHENQ,SHID.Themodelingofscale-freenetworks[J].PhysicaAStatisticalMechanics&ItsApplications, 2004, 335: 240-248. [14] 梁宏振, 姚洪興, 張學兵. 一類無標度網(wǎng)絡的特征分析[J]. 復雜系統(tǒng)與復雜性科學, 2005, 2(3): 67-71.LIANGHZ,YAOHX,ZHANGXB.Charactersanalysisforaclassofscale-freenetworks[J].ComplexSystems&ComplexityScience, 2005, 2(3): 67-71. [15] 賈秀麗, 蔡紹洪, 張芙蓉. 一種動態(tài)的無標度網(wǎng)絡模型[J]. 四川師范大學學報(自然科學版), 2009, 32(6): 839-842.JIAXL,CAISH,ZHANGFR.Adynamicscale-freenetworkmodel[J].JournalofSichuanNormalUniversity(NaturalScience), 2009, 32(6): 839-842. [16] 王林, 戴冠中. 復雜網(wǎng)絡的度分布研究[J]. 西北工業(yè)大學學報 (自然科學版), 2006, 24(4):405-409.WANGL,DAIGZ.Ondegreedistributionofcomplexnetwork[J].JournalofNorthwesternPolytechnicalUniversity, 2006, 24(4):405-409. [17]YAOB,MAF,SUJ,etal.Scale-freemultiple-partitemodelstowardsinformationnetworks[C]//Proceedingsof2016IEEEAdvancedInformationManagement,Communicates,ElectronicandAutomationControlConference(IMCEC2016), 2016: 549-554. [18]SUJ,MAF,YAOB,etal.AS-mixednetworkmodelscreatedbytriangle-expandingoperations[C]//JointInternationalInformationTechnology,MechanicalandElectronicEngineeringConference(JIMEC2016), 2016, 59: 260-265. [19] 王曉敏, 趙喜楊, 姚兵. 全邊增長網(wǎng)絡模型的生成樹[J]. 中山大學學報 (自然科學版), 2016,55(1): 48-53.WANGXM,ZHAOXY,YAOB.Spanningtreesoftotallyedge-growingnetworkmodels[J].ActaScientiarumNaturaliumUniversitatisSunyatseni, 2016,55(1): 48-53. [20] 楊俊仙, 閆萍.一類具飽和發(fā)生率的時滯SEIR傳染病模型的分析[J]. 中山大學學報 (自然科學版), 2015, 54(3): 51-55.YANGJX,YANP.AnalysisofadelayedSEIRepidemicmodelwithsaturationincidence[J].ActaScientiarumNaturaliumUniversitatisSunyatseni, 2015, 54(3): 51-55. Double preferential scale-free network models MAFei,YAOBing (College of Mathematics and Statistics,Northwest Normal University,Lanzhou 730070,China) Based on the “classic” scale-free network model, the network growth principle(preferential attachment mechanism) is extended. Starting from a more general situation, some vertex-preferential attachment probability in different constraint conditions are established, and then the partial differential equation satisfied a more general network dynamic system is set up, and also another important topological property of scale-free network is found. Then a much realistic preferential attachment probability is presented. Finally, a more general network model is generated. By discussing its scale-free property, that scale-free parameterγrangesfrom1to4iscaptured. scale-free network model; dynamic evolution; partial differential equation; the six degrees of separation 2016-05-18 基金項目:國家自然科學基金 (61662066,61163054,61363060) 馬飛(1992年生), 男;研究方向:動態(tài)圖論與復雜網(wǎng)絡;E-mail: mafei123987@163.com 姚兵(1956年生);男;研究方向:動態(tài)圖論與復雜網(wǎng)絡; E-mail: yybb918@163. com 10.13471/j.cnki.acta.snus.2017.01.014 O A 0529-6579(2017)01-0085-082 設立反擇優(yōu)連接的標準
3 滿足方程(2)的網(wǎng)絡模型
4 雙優(yōu)無標度網(wǎng)絡模型
5 總結(jié)及問題