韓錦華

（陜西師范大學(xué)物理學(xué)與信息技術(shù)學(xué)院，陜西西安 710119）

信息交換網(wǎng)、社會網(wǎng)絡(luò)、生物網(wǎng)絡(luò)都是一些可用復(fù)雜網(wǎng)絡(luò)描述的事例。傳統(tǒng)研究復(fù)雜網(wǎng)絡(luò)是用隨機(jī)圖來研究的。近年來，隨著計算機(jī)能力的提高，使我們能夠研究包含成千上萬節(jié)點的復(fù)雜網(wǎng)絡(luò)，與此同時，很多新概念、新測量方法如小世界網(wǎng)絡(luò)、度分布、聚類系數(shù)等被提出來［1］。

隨機(jī)圖研究復(fù)雜網(wǎng)絡(luò)的節(jié)點度分布是一個泊松分布?，F(xiàn)在對復(fù)雜網(wǎng)絡(luò)的研究結(jié)果是不同的：Redner研究了被科學(xué)信息研究所所收錄的783339篇文章及在1975至1994年間發(fā)表在PRD上的24296篇文章的被引用次數(shù)的分布，發(fā)現(xiàn)它們服從指數(shù)為3的冪律分布，為無標(biāo)度網(wǎng)絡(luò)。事實上，很多實際復(fù)雜網(wǎng)絡(luò)的節(jié)點度分布是冪律分布［1］。

研究無標(biāo)度網(wǎng)絡(luò)模型最早和最多的是BA無標(biāo)度網(wǎng)絡(luò)模型，但它不能用來解釋現(xiàn)實中很多無標(biāo)度網(wǎng)絡(luò)的某些特性。比如上述事例中，并不是所有已發(fā)表過的文章都會被新發(fā)表的文章所引用，對于年代距今久遠(yuǎn)的文章，內(nèi)容可能已經(jīng)過時，不被引用，而年代距今很近的文章被引用的可能性較前者大一些。一篇文章被引用的概率將隨著它已發(fā)表的時間的增長而降低，但根據(jù)BA無標(biāo)度網(wǎng)絡(luò)模型中的優(yōu)先連接原則，一篇文章被引用的概率與它已發(fā)表的時間成正相關(guān)性，與實際情況相矛盾。再如，如果將BA無標(biāo)度網(wǎng)絡(luò)模型中最老的一些節(jié)點去掉，則它不再是無標(biāo)度網(wǎng)絡(luò)，但科學(xué)研究表明有些實際無標(biāo)度網(wǎng)絡(luò)如果去掉所有節(jié)點中最老的一部分，依然是無標(biāo)度網(wǎng)絡(luò)。為了解決這一矛盾，我們需要構(gòu)建新的網(wǎng)絡(luò)模型［2］。

1 模型A

我們將網(wǎng)絡(luò)中節(jié)點比作被引用文章，而連線比作發(fā)表文章與被引文章的聯(lián)系，節(jié)點的度表示文章被引的次數(shù)，從而構(gòu)成引文網(wǎng)絡(luò)。能夠被引用的文章稱為活躍節(jié)點，一篇文章直到不被引用時，則變?yōu)椴换钴S節(jié)點。當(dāng)其不被引用時，則永遠(yuǎn)不被引用，即永遠(yuǎn)失活。如果一篇文章被引次數(shù)越多，則越不容易被遺忘，相反則越容易被遺忘。我們用ki表示節(jié)點的度，P表示節(jié)點失活的概率，則有P正比于1／（a+ki），其中a為偏置常數(shù)［2］。

設(shè)初始網(wǎng)絡(luò)由m個活躍、完全連接的節(jié)點組成。

1.1 累積度分布

根據(jù)文獻(xiàn)［2］［3］［4］，我們首先導(dǎo)出在某一時刻t時活躍節(jié)點的度分布p（k），對于k＞0，我們有

假設(shè)歸一化因子r-1的浮動變化足夠小，r可以看成是一個常數(shù)。靜止情況下P（t+1）（k）＝P（t）（k）

將k看成連續(xù)的，我們可將（2）寫成

得到

b為歸一化常數(shù)。整個網(wǎng)絡(luò)中，相比所有點而言，m個活躍點數(shù)量是很小的，所以整個網(wǎng)絡(luò)度分布N（k）可以近似只考慮失活點的度分布，我們有

取m＝10，a＝10，p1＝0.99，運用Fortran90語言編程，模擬50000次時間步，獨立重復(fù)10次，取平均得到累積度分布。如圖A（a）所示，它是冪律分布，與很多實際復(fù)雜網(wǎng)絡(luò)特征相符合。斜率為1.95即為指數(shù)，與方程（4）相似，略低于數(shù)值分析結(jié)果（r-1）p1＝1.98。其中橫坐標(biāo)表示網(wǎng)絡(luò)節(jié)點的度，縱坐標(biāo)表示大于對應(yīng)其橫坐標(biāo)節(jié)點度的節(jié)點數(shù)占網(wǎng)絡(luò)總節(jié)點數(shù)的比例。

上面我們考慮了包含網(wǎng)絡(luò)中所有節(jié)點，但是在很多情況下，經(jīng)驗數(shù)據(jù)只包含網(wǎng)絡(luò)中最近連接的新點及連線。比如在引文網(wǎng)絡(luò)研究中所用文章距現(xiàn)在不能超過某一特定年份，這種網(wǎng)絡(luò)稱為截斷網(wǎng)絡(luò)。如圖A（b）所示，其忽略了最老的一半節(jié)點及它們所有的連線?？梢钥吹阶兓淮?，與很多實際復(fù)雜網(wǎng)絡(luò)特征相符合。而BA無標(biāo)度網(wǎng)絡(luò)中截斷前與截斷后的累積度分布變化比較大，與很多實際復(fù)雜網(wǎng)絡(luò)特征不符。運用Fortran90語言編程，取初始節(jié)點數(shù)為10，模擬50000次時間步，獨立重復(fù)10次，求平均后得到的BA無標(biāo)度網(wǎng)絡(luò)模型截斷前及截斷后累積度分布如圖A（c）所示。

為了系統(tǒng)的觀察截斷帶來的影響，我們考慮在不同截斷節(jié)點數(shù)時網(wǎng)絡(luò)節(jié)點的最大度。獨立重復(fù)10次，取平均得到結(jié)果如圖A（d）所示。其中橫坐標(biāo)表示截斷其前一半節(jié)點及所有連線，縱坐標(biāo)表示截斷后此時網(wǎng)絡(luò)中存在的節(jié)點中的節(jié)點最大度。

1.2 年齡分布

我們定義年齡分布h（τ）為在t時刻一條新邊連接到年齡為τ的節(jié)點概率。因為只有活躍的節(jié)點才能夠得到連線，對于這些節(jié)點，它們的年齡與它們的度有相同值，所以年齡為τ的節(jié)點獲得一條新邊的概率與這個節(jié)點有τ條邊時能夠活躍的概率相同（4）式，則h（τ）正比于（a+τ）-r+1。取上述相同的初始值及模擬方法得到結(jié)果如圖A（e）所示?？梢钥吹诫S著節(jié)點相對年齡的增大而連接概率有降低的趨勢，與實際引文網(wǎng)絡(luò)特征相符合。

而取初始網(wǎng)絡(luò)節(jié)點數(shù)為10個點，模擬50000次時間步，獨立重復(fù)10次，求平均得到的BA無標(biāo)度網(wǎng)絡(luò)結(jié)果如圖A（f）所示，與實際引文網(wǎng)絡(luò)特征不符合。

1.3 聚類系數(shù)

一般的，假設(shè)網(wǎng)絡(luò)中的一個節(jié)點i有ki條邊將它和其他節(jié)點相連，這ki個節(jié)點就稱為節(jié)點i的鄰居。顯然在這ki個節(jié)點之間最多可能有ki（ki-1）／2條邊，而這ki個節(jié)點之間實際存在的邊數(shù)Ei和總的可能邊數(shù)ki（ki-1）／2之比就定義為節(jié)點i的聚類系數(shù)Ci［5］14即：

這里取與上述相同的初始值，模擬10000次時間步，獨立重復(fù)10次，求平均得到結(jié)果如圖A（g）所示。圖中橫坐標(biāo)表示網(wǎng)絡(luò)總共包含的節(jié)點數(shù)，縱坐標(biāo)表示相應(yīng)網(wǎng)絡(luò)的聚類系數(shù)。而BA無標(biāo)度網(wǎng)絡(luò)模型中，隨著網(wǎng)絡(luò)包含節(jié)點數(shù)量的增加，其聚類系數(shù)迅速下降如圖A（h）所示。

我們可以看到，隨著網(wǎng)絡(luò)包含節(jié)點數(shù)量的增加，其聚類系數(shù)趨向于0.82，此網(wǎng)絡(luò)具有高聚類系數(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ò)中已存在的活躍點中的m個活躍點相連接，每一個活躍節(jié)點只能被連接一次。模擬方法與模型A的方法完全相同。圖B（a）為網(wǎng)絡(luò)截斷前與截斷后的累積度分布，圖B（b）為截斷節(jié)點數(shù)與節(jié)點最大度關(guān)系圖，圖B（c）為節(jié)點相對年齡與連接概率關(guān)系圖，圖B（d）為網(wǎng)絡(luò)大小與相應(yīng)的聚類系數(shù)關(guān)系圖。

可以看到，圖B（a），圖B（b），圖B（c）模擬結(jié)果與模型A相似，與實際引文網(wǎng)絡(luò)特征相符合。圖B（d）與電子郵件網(wǎng)（C＝0.16）［5］10相似。

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

只將模型A第（2）步驟改為以優(yōu)先連接原則與m個活躍點連接，每一個活躍節(jié)點只能被連接一次，模擬結(jié)果與圖A（c），圖B（c）結(jié)果近似相同，而網(wǎng)絡(luò)的大小與相應(yīng)的聚類系數(shù)與上述模型有所不同。而只將模型A第（2）步驟改為將其與網(wǎng)絡(luò)中已存在的活躍點中的最老（近）的m個活躍點相連接，模擬結(jié)果與模型A、B有很大差異。

綜上所述，我們提出了兩種基于節(jié)點失活的網(wǎng)絡(luò)增長模型。通過數(shù)值計算分析和編程模擬，得到了網(wǎng)絡(luò)節(jié)點截斷前累積度冪律分布和隨著截斷節(jié)點數(shù)的增加而節(jié)點最大度下降關(guān)系。實際網(wǎng)絡(luò)節(jié)點被截斷后，累積度分布依然保持冪律分布的特征，隨著節(jié)點年齡的增大而連接概率降低的特征，而這些特征用傳統(tǒng)BA無標(biāo)度網(wǎng)絡(luò)模型無法解釋。發(fā)現(xiàn)隨著網(wǎng)絡(luò)節(jié)點數(shù)的增大，其聚類系數(shù)保持比較大的數(shù)值，而BA無標(biāo)度網(wǎng)絡(luò)模型的特征恰恰相反。這些模型對于我們研究實際存在的復(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.