韓錦華
(陜西師范大學(xué)物理學(xué)與信息技術(shù)學(xué)院,陜西西安 710119)
信息交換網(wǎng)、社會(huì)網(wǎng)絡(luò)、生物網(wǎng)絡(luò)都是一些可用復(fù)雜網(wǎng)絡(luò)描述的事例。傳統(tǒng)研究復(fù)雜網(wǎng)絡(luò)是用隨機(jī)圖來(lái)研究的。近年來(lái),隨著計(jì)算機(jī)能力的提高,使我們能夠研究包含成千上萬(wàn)節(jié)點(diǎn)的復(fù)雜網(wǎng)絡(luò),與此同時(shí),很多新概念、新測(cè)量方法如小世界網(wǎng)絡(luò)、度分布、聚類(lèi)系數(shù)等被提出來(lái)[1]。
隨機(jī)圖研究復(fù)雜網(wǎng)絡(luò)的節(jié)點(diǎn)度分布是一個(gè)泊松分布?,F(xiàn)在對(duì)復(fù)雜網(wǎng)絡(luò)的研究結(jié)果是不同的:Redner研究了被科學(xué)信息研究所所收錄的783339篇文章及在1975至1994年間發(fā)表在PRD上的24296篇文章的被引用次數(shù)的分布,發(fā)現(xiàn)它們服從指數(shù)為3的冪律分布,為無(wú)標(biāo)度網(wǎng)絡(luò)。事實(shí)上,很多實(shí)際復(fù)雜網(wǎng)絡(luò)的節(jié)點(diǎn)度分布是冪律分布[1]。
研究無(wú)標(biāo)度網(wǎng)絡(luò)模型最早和最多的是BA無(wú)標(biāo)度網(wǎng)絡(luò)模型,但它不能用來(lái)解釋現(xiàn)實(shí)中很多無(wú)標(biāo)度網(wǎng)絡(luò)的某些特性。比如上述事例中,并不是所有已發(fā)表過(guò)的文章都會(huì)被新發(fā)表的文章所引用,對(duì)于年代距今久遠(yuǎn)的文章,內(nèi)容可能已經(jīng)過(guò)時(shí),不被引用,而年代距今很近的文章被引用的可能性較前者大一些。一篇文章被引用的概率將隨著它已發(fā)表的時(shí)間的增長(zhǎng)而降低,但根據(jù)BA無(wú)標(biāo)度網(wǎng)絡(luò)模型中的優(yōu)先連接原則,一篇文章被引用的概率與它已發(fā)表的時(shí)間成正相關(guān)性,與實(shí)際情況相矛盾。再如,如果將BA無(wú)標(biāo)度網(wǎng)絡(luò)模型中最老的一些節(jié)點(diǎn)去掉,則它不再是無(wú)標(biāo)度網(wǎng)絡(luò),但科學(xué)研究表明有些實(shí)際無(wú)標(biāo)度網(wǎng)絡(luò)如果去掉所有節(jié)點(diǎn)中最老的一部分,依然是無(wú)標(biāo)度網(wǎng)絡(luò)。為了解決這一矛盾,我們需要構(gòu)建新的網(wǎng)絡(luò)模型[2]。
我們將網(wǎng)絡(luò)中節(jié)點(diǎn)比作被引用文章,而連線(xiàn)比作發(fā)表文章與被引文章的聯(lián)系,節(jié)點(diǎn)的度表示文章被引的次數(shù),從而構(gòu)成引文網(wǎng)絡(luò)。能夠被引用的文章稱(chēng)為活躍節(jié)點(diǎn),一篇文章直到不被引用時(shí),則變?yōu)椴换钴S節(jié)點(diǎn)。當(dāng)其不被引用時(shí),則永遠(yuǎn)不被引用,即永遠(yuǎn)失活。如果一篇文章被引次數(shù)越多,則越不容易被遺忘,相反則越容易被遺忘。我們用ki表示節(jié)點(diǎn)的度,P表示節(jié)點(diǎn)失活的概率,則有P正比于1/(a+ki),其中a為偏置常數(shù)[2]。
設(shè)初始網(wǎng)絡(luò)由m個(gè)活躍、完全連接的節(jié)點(diǎn)組成。
根據(jù)文獻(xiàn)[2][3][4],我們首先導(dǎo)出在某一時(shí)刻t時(shí)活躍節(jié)點(diǎn)的度分布p(k),對(duì)于k>0,我們有
假設(shè)歸一化因子r-1的浮動(dòng)變化足夠小,r可以看成是一個(gè)常數(shù)。靜止情況下P(t+1)(k)=P(t)(k)
將k看成連續(xù)的,我們可將(2)寫(xiě)成
得到
b為歸一化常數(shù)。整個(gè)網(wǎng)絡(luò)中,相比所有點(diǎn)而言,m個(gè)活躍點(diǎn)數(shù)量是很小的,所以整個(gè)網(wǎng)絡(luò)度分布N(k)可以近似只考慮失活點(diǎn)的度分布,我們有
取m=10,a=10,p1=0.99,運(yùn)用Fortran90語(yǔ)言編程,模擬50000次時(shí)間步,獨(dú)立重復(fù)10次,取平均得到累積度分布。如圖A(a)所示,它是冪律分布,與很多實(shí)際復(fù)雜網(wǎng)絡(luò)特征相符合。斜率為1.95即為指數(shù),與方程(4)相似,略低于數(shù)值分析結(jié)果(r-1)p1=1.98。其中橫坐標(biāo)表示網(wǎng)絡(luò)節(jié)點(diǎn)的度,縱坐標(biāo)表示大于對(duì)應(yīng)其橫坐標(biāo)節(jié)點(diǎn)度的節(jié)點(diǎn)數(shù)占網(wǎng)絡(luò)總節(jié)點(diǎn)數(shù)的比例。
上面我們考慮了包含網(wǎng)絡(luò)中所有節(jié)點(diǎn),但是在很多情況下,經(jīng)驗(yàn)數(shù)據(jù)只包含網(wǎng)絡(luò)中最近連接的新點(diǎn)及連線(xiàn)。比如在引文網(wǎng)絡(luò)研究中所用文章距現(xiàn)在不能超過(guò)某一特定年份,這種網(wǎng)絡(luò)稱(chēng)為截?cái)嗑W(wǎng)絡(luò)。如圖A(b)所示,其忽略了最老的一半節(jié)點(diǎn)及它們所有的連線(xiàn)??梢钥吹阶兓淮螅c很多實(shí)際復(fù)雜網(wǎng)絡(luò)特征相符合。而B(niǎo)A無(wú)標(biāo)度網(wǎng)絡(luò)中截?cái)嗲芭c截?cái)嗪蟮睦鄯e度分布變化比較大,與很多實(shí)際復(fù)雜網(wǎng)絡(luò)特征不符。運(yùn)用Fortran90語(yǔ)言編程,取初始節(jié)點(diǎn)數(shù)為10,模擬50000次時(shí)間步,獨(dú)立重復(fù)10次,求平均后得到的BA無(wú)標(biāo)度網(wǎng)絡(luò)模型截?cái)嗲凹敖財(cái)嗪罄鄯e度分布如圖A(c)所示。
為了系統(tǒng)的觀察截?cái)鄮?lái)的影響,我們考慮在不同截?cái)喙?jié)點(diǎn)數(shù)時(shí)網(wǎng)絡(luò)節(jié)點(diǎn)的最大度。獨(dú)立重復(fù)10次,取平均得到結(jié)果如圖A(d)所示。其中橫坐標(biāo)表示截?cái)嗥淝耙话牍?jié)點(diǎn)及所有連線(xiàn),縱坐標(biāo)表示截?cái)嗪蟠藭r(shí)網(wǎng)絡(luò)中存在的節(jié)點(diǎn)中的節(jié)點(diǎn)最大度。
我們定義年齡分布h(τ)為在t時(shí)刻一條新邊連接到年齡為τ的節(jié)點(diǎn)概率。因?yàn)橹挥谢钴S的節(jié)點(diǎn)才能夠得到連線(xiàn),對(duì)于這些節(jié)點(diǎn),它們的年齡與它們的度有相同值,所以年齡為τ的節(jié)點(diǎn)獲得一條新邊的概率與這個(gè)節(jié)點(diǎn)有τ條邊時(shí)能夠活躍的概率相同(4)式,則h(τ)正比于(a+τ)-r+1。取上述相同的初始值及模擬方法得到結(jié)果如圖A(e)所示。可以看到隨著節(jié)點(diǎn)相對(duì)年齡的增大而連接概率有降低的趨勢(shì),與實(shí)際引文網(wǎng)絡(luò)特征相符合。
而取初始網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)為10個(gè)點(diǎn),模擬50000次時(shí)間步,獨(dú)立重復(fù)10次,求平均得到的BA無(wú)標(biāo)度網(wǎng)絡(luò)結(jié)果如圖A(f)所示,與實(shí)際引文網(wǎng)絡(luò)特征不符合。
一般的,假設(shè)網(wǎng)絡(luò)中的一個(gè)節(jié)點(diǎn)i有ki條邊將它和其他節(jié)點(diǎn)相連,這ki個(gè)節(jié)點(diǎn)就稱(chēng)為節(jié)點(diǎn)i的鄰居。顯然在這ki個(gè)節(jié)點(diǎn)之間最多可能有ki(ki-1)/2條邊,而這ki個(gè)節(jié)點(diǎn)之間實(shí)際存在的邊數(shù)Ei和總的可能邊數(shù)ki(ki-1)/2之比就定義為節(jié)點(diǎn)i的聚類(lèi)系數(shù)Ci[5]14即:
這里取與上述相同的初始值,模擬10000次時(shí)間步,獨(dú)立重復(fù)10次,求平均得到結(jié)果如圖A(g)所示。圖中橫坐標(biāo)表示網(wǎng)絡(luò)總共包含的節(jié)點(diǎn)數(shù),縱坐標(biāo)表示相應(yīng)網(wǎng)絡(luò)的聚類(lèi)系數(shù)。而B(niǎo)A無(wú)標(biāo)度網(wǎng)絡(luò)模型中,隨著網(wǎng)絡(luò)包含節(jié)點(diǎn)數(shù)量的增加,其聚類(lèi)系數(shù)迅速下降如圖A(h)所示。
我們可以看到,隨著網(wǎng)絡(luò)包含節(jié)點(diǎn)數(shù)量的增加,其聚類(lèi)系數(shù)趨向于0.82,此網(wǎng)絡(luò)具有高聚類(lèi)系數(shù)的特點(diǎn),與實(shí)際網(wǎng)絡(luò)如演員網(wǎng)絡(luò)(C=0.79)及科學(xué)合作網(wǎng)(C=0.76)相似[1]。
只須將模型A第(2)步驟改為:將其隨機(jī)與網(wǎng)絡(luò)中已存在的活躍點(diǎn)中的m個(gè)活躍點(diǎn)相連接,每一個(gè)活躍節(jié)點(diǎn)只能被連接一次。模擬方法與模型A的方法完全相同。圖B(a)為網(wǎng)絡(luò)截?cái)嗲芭c截?cái)嗪蟮睦鄯e度分布,圖B(b)為截?cái)喙?jié)點(diǎn)數(shù)與節(jié)點(diǎn)最大度關(guān)系圖,圖B(c)為節(jié)點(diǎn)相對(duì)年齡與連接概率關(guān)系圖,圖B(d)為網(wǎng)絡(luò)大小與相應(yīng)的聚類(lèi)系數(shù)關(guān)系圖。
可以看到,圖B(a),圖B(b),圖B(c)模擬結(jié)果與模型A相似,與實(shí)際引文網(wǎng)絡(luò)特征相符合。圖B(d)與電子郵件網(wǎng)(C=0.16)[5]10相似。
只將模型A第(2)步驟改為以?xún)?yōu)先連接原則與m個(gè)活躍點(diǎn)連接,每一個(gè)活躍節(jié)點(diǎn)只能被連接一次,模擬結(jié)果與圖A(c),圖B(c)結(jié)果近似相同,而網(wǎng)絡(luò)的大小與相應(yīng)的聚類(lèi)系數(shù)與上述模型有所不同。而只將模型A第(2)步驟改為將其與網(wǎng)絡(luò)中已存在的活躍點(diǎn)中的最老(近)的m個(gè)活躍點(diǎn)相連接,模擬結(jié)果與模型A、B有很大差異。
綜上所述,我們提出了兩種基于節(jié)點(diǎn)失活的網(wǎng)絡(luò)增長(zhǎng)模型。通過(guò)數(shù)值計(jì)算分析和編程模擬,得到了網(wǎng)絡(luò)節(jié)點(diǎn)截?cái)嗲袄鄯e度冪律分布和隨著截?cái)喙?jié)點(diǎn)數(shù)的增加而節(jié)點(diǎn)最大度下降關(guān)系。實(shí)際網(wǎng)絡(luò)節(jié)點(diǎn)被截?cái)嗪?,累積度分布依然保持冪律分布的特征,隨著節(jié)點(diǎn)年齡的增大而連接概率降低的特征,而這些特征用傳統(tǒng)BA無(wú)標(biāo)度網(wǎng)絡(luò)模型無(wú)法解釋。發(fā)現(xiàn)隨著網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)的增大,其聚類(lèi)系數(shù)保持比較大的數(shù)值,而B(niǎo)A無(wú)標(biāo)度網(wǎng)絡(luò)模型的特征恰恰相反。這些模型對(duì)于我們研究實(shí)際存在的復(fù)雜網(wǎng)絡(luò)的拓?fù)湫再|(zhì)及系統(tǒng)結(jié)構(gòu)是有幫助的。
[1]ALBERT R,BARABA'SI A-L.Statistical mechanics of complex networks[J].Rev.Mod.Phys,2002,74,47.
[2]KLEMM K,EGUILUZ V M.Highly clustered scale-free networks[J].Phys.Rev.E,2002,65,036123.
[3]WU Zhi-xi,XU Xin-jian,WANG YING-Hai.Generating structured networks based on a weight-dependent deactivationmechanism[J].Phys.Rev.E,2005,71,066124.
[4]TIAN Liang,ZHU Chen-ping,SHI Da-ning,GU Zhi-ming.Universal scaling behavior of clustering coefficient induced by deactivation mechanism[J].Phys.Rev.E,2006,74,046103.
[5]汪小帆,等.復(fù)雜網(wǎng)絡(luò)理論及其應(yīng)用[M].北京:清華大學(xué)出版社,2005.