基于引文網(wǎng)絡(luò)的無(wú)標(biāo)度網(wǎng)絡(luò)模型探究

韓錦華

（陜西師范大學(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］。

1 模型A

我們將網(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)組成。

1.1 累積度分布

根據(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)最大度。

1.2 年齡分布

我們定義年齡分布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ò)特征不符合。

1.3 聚類(lèi)系數(shù)

一般的，假設(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］。

2 模型B

只須將模型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相似。

3 延伸網(wǎng)絡(luò)模型

只將模型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.