胡燕萍，李金仙，李偉強(qiáng)

(山西大學(xué) 數(shù)學(xué)科學(xué)學(xué)院， 太原 030006)

疾病在復(fù)雜網(wǎng)絡(luò)上的傳播已經(jīng)成為疾病動(dòng)力學(xué)研究的重要組成部分[1]。大量文獻(xiàn)已經(jīng)證實(shí)，網(wǎng)絡(luò)的結(jié)構(gòu)特征對(duì)疾病在其上的傳播有著顯著的影響，比如度分布和聚類系數(shù)等。聚類，作為現(xiàn)實(shí)生活中普遍存在的一種現(xiàn)象，一直受到很大的關(guān)注，但是研究聚類的動(dòng)力學(xué)模型并不多，有關(guān)聚類的結(jié)論大多是基于網(wǎng)絡(luò)模型給出的。目前，生成聚類網(wǎng)絡(luò)的算法已有不少，包括迭代算法[2]、基于群體的算法[3]以及Big-V重連算法[4]等，而引人注目且應(yīng)用較為廣泛的是Big-V重連(BV)算法。BV算法具有適應(yīng)性強(qiáng)、引入聚類更加隨機(jī)等優(yōu)勢(shì)，但也存在計(jì)算成本較高的不足。本文介紹一種新的生成聚類網(wǎng)絡(luò)的算法，這種算法是基于配置模型(configuration model)的推廣[5-6]，稱之為GCM算法。一方面，從某一角度研究了GCM算法的可行性；另一方面，將GCM和BV兩種算法進(jìn)行了對(duì)比，特別是在由它們生成的聚類網(wǎng)絡(luò)的大尺度結(jié)構(gòu)特征方面。

1 聚類介紹以及算法描述

聚類描述的是“朋友的朋友也是朋友”這類現(xiàn)象。聚類現(xiàn)象普遍存在，如在一個(gè)刻畫朋友關(guān)系的網(wǎng)絡(luò)中，一個(gè)人的兩個(gè)朋友之間也極有可能彼此是朋友，即一個(gè)節(jié)點(diǎn)的兩個(gè)鄰居之間也可能存在連邊。

在網(wǎng)絡(luò)中，聚類系數(shù)是描述網(wǎng)絡(luò)中節(jié)點(diǎn)聚集程度的一種度量。根據(jù)刻畫尺度的不同，聚類可以給出兩種不同的定義方式[7]：全局和局部的度量。全局聚類系數(shù)旨在度量整個(gè)網(wǎng)絡(luò)的集聚性，其定義如下：

其中：NΔ表示網(wǎng)絡(luò)中三角形的數(shù)量；N3表示網(wǎng)絡(luò)中總的三元組的數(shù)量。局部聚類系數(shù)刻畫了網(wǎng)絡(luò)中單個(gè)節(jié)點(diǎn)的聚集水平，定義節(jié)點(diǎn)i的聚類為

其中：di表示節(jié)點(diǎn)i的度；Ei表示節(jié)點(diǎn)i的di個(gè)鄰居之間實(shí)際存在的邊數(shù)。

對(duì)于網(wǎng)絡(luò)聚類而言，研究普遍集中于討論聚類的存在給網(wǎng)絡(luò)結(jié)構(gòu)帶來的差異以及對(duì)建立在網(wǎng)絡(luò)上的動(dòng)力學(xué)過程的影響。文獻(xiàn)[8]對(duì)前人研究的成果進(jìn)行了綜述，指出聚類對(duì)傳染性疾病的增長(zhǎng)速率、最終規(guī)模與閾值均有不同程度的影響。除了從宏觀角度上對(duì)網(wǎng)絡(luò)整體聚類水平進(jìn)行研究之外，從微觀角度上，有文獻(xiàn)也指出，即便在具有相等的全局聚類系數(shù)的前提下，網(wǎng)絡(luò)局部聚類分布的差異也有可能影響疾病的動(dòng)力學(xué)[6]。

1.1 GCM算法

隨機(jī)聚類網(wǎng)絡(luò)是基于N個(gè)節(jié)點(diǎn)網(wǎng)絡(luò)中隨機(jī)安排一定數(shù)量的邊與三角形而生成的，其中，隨機(jī)數(shù)的產(chǎn)生與度分布pk和參數(shù)pt有關(guān)。而網(wǎng)絡(luò)的邊則通過下述過程構(gòu)造：

1) 對(duì)于每個(gè)節(jié)點(diǎn)v，隨機(jī)安排服從于度分布pk的邊數(shù)δv和服從于參數(shù)為(δv-1)δv/2與pt的二項(xiàng)分布的三角形數(shù)ρv，其中pt(pi∈[0,1])為一給定常數(shù)。

2) 對(duì)于每個(gè)節(jié)點(diǎn)v，構(gòu)造一個(gè)由“半邊(half-edge)”組成的集合Xv，元素為節(jié)點(diǎn)v的δv個(gè)副本(copies)，也構(gòu)造一個(gè)由“角(corner)”組成的集合Yv，元素為節(jié)點(diǎn)v的ρv個(gè)副本。令X=Xv1∪Xv2∪…∪XvN，Y=Yv1∪Yv2∪…∪YvN。

3) 判斷||Y||<3是否成立，如果成立，則直接跳到步驟5)。否則的話，從集合Y中隨機(jī)選取3個(gè)元素v1、v2與v3后，執(zhí)行如下步驟：

① 對(duì)上述3個(gè)節(jié)點(diǎn)中的任意兩個(gè)，判斷它們之間是否已存在連邊。如果沒有，則在它們之間構(gòu)造一條邊。

② 對(duì)上述3個(gè)節(jié)點(diǎn)，依次進(jìn)行如下過程，以節(jié)點(diǎn)v1為例闡述：判斷節(jié)點(diǎn)v1剩余的半邊數(shù)是否小于2并且節(jié)點(diǎn)v1剩余的角數(shù)是否為0；如果條件成立，首先在剩余的半邊與另一條隨機(jī)選擇的半邊之間構(gòu)造一條邊，然后對(duì)于由節(jié)點(diǎn)v1的所有鄰居所構(gòu)成的全部可能鄰居組合，只要組合中的任一鄰居仍有多余的半邊與角，便在它們之間構(gòu)造一條邊，直到所有組合都被嘗試過或者節(jié)點(diǎn)v1的角不再剩余；最后令Yv1=?。

③ 在整個(gè)過程中，一個(gè)包含節(jié)點(diǎn)v的新三角形一旦形成，則從集合Yv中刪除v的一個(gè)副本；同樣，一條包含節(jié)點(diǎn)v的新邊一旦形成，則從集合Xv中刪除v的一個(gè)副本。

4) 重復(fù)步驟3)。

5) 在從集合X中隨機(jī)選擇的兩個(gè)元素之間構(gòu)造新邊，直到||X||<1。其中||·||表示一個(gè)集合元素的個(gè)數(shù)。

注意到GCM算法允許兩個(gè)節(jié)點(diǎn)之間存在重邊，也允許自環(huán)的情形出現(xiàn)，然而相較于大型的稀疏隨機(jī)網(wǎng)絡(luò)而言，出現(xiàn)重邊與自環(huán)的情形是非常稀少的，因此可以忽略不計(jì)。此外，不難發(fā)現(xiàn)，如果令pt=0，GCM算法完全“退化”成配置模型。

1.2 BV算法

BV算法[4]是通過兩個(gè)步驟來生成聚類網(wǎng)絡(luò)的：第1步，生成一個(gè)隨機(jī)圖；第2步，通過斷邊重連的方式，在圖中引入聚類。

斷邊重連也被稱為邊的交換。一個(gè)斷邊重連的過程由兩步組成：一是斷開兩條不相鄰的邊，二是重新連接斷開的邊，見圖1。在BV算法中，斷邊重連是基于5個(gè)節(jié)點(diǎn)構(gòu)成的形狀類似于“大V(big-V)”的網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行的，見圖2。這種基于“大V”的斷邊重連，一方面增加了網(wǎng)絡(luò)的聚類，另一方面未改變每個(gè)參與節(jié)點(diǎn)的度。

圖1 斷邊重連示意圖

圖2 “大V”斷邊重連示意圖

2 網(wǎng)絡(luò)的大尺度結(jié)構(gòu)

為了研究?jī)深惥垲惥W(wǎng)絡(luò)生成算法的差異，關(guān)注兩類算法生成的聚類網(wǎng)絡(luò)的結(jié)構(gòu)特征，特別是大尺度結(jié)構(gòu)特征[9]，對(duì)兩種算法選取相同的初始度序列，分別生成100個(gè)網(wǎng)絡(luò)，并使得聚類值分別為C=0.2與C=0.35。在這里采用如下一系列度量來刻畫網(wǎng)絡(luò)的大尺度結(jié)構(gòu)：

2.1 路徑長(zhǎng)度

在現(xiàn)實(shí)網(wǎng)絡(luò)中，很大部分節(jié)點(diǎn)彼此并不相連，但絕大部分節(jié)點(diǎn)之間經(jīng)過很少幾步就可以到達(dá)，這種現(xiàn)象也被稱為小世界現(xiàn)象。不難想象，小世界網(wǎng)絡(luò)對(duì)疾病的傳播有著明顯的影響。設(shè)想，在一個(gè)路徑普遍較短的簡(jiǎn)單網(wǎng)絡(luò)上，疾病從一個(gè)節(jié)點(diǎn)傳到另一個(gè)節(jié)點(diǎn)只需要通過更少的邊，進(jìn)而在某些假設(shè)下，這就意味著疾病可以在較短的時(shí)間內(nèi)爆發(fā)到一定的數(shù)量。

常使用下式來刻畫網(wǎng)絡(luò)的平均路徑長(zhǎng)度：

其中：dij表示網(wǎng)絡(luò)中節(jié)點(diǎn)i與j的最短距離；N表示網(wǎng)絡(luò)的總節(jié)點(diǎn)數(shù)。在實(shí)際使用中，常常僅在網(wǎng)絡(luò)的最大連通片中考慮此均值，也就是說，上述求和只對(duì)最大連通片中的節(jié)點(diǎn)進(jìn)行，N也僅表示最大連通片中節(jié)點(diǎn)的數(shù)量。

2.2 同配混合

同配混合是描述網(wǎng)絡(luò)相關(guān)性的一種特征量，即網(wǎng)絡(luò)中的節(jié)點(diǎn)偏向于與其類似的節(jié)點(diǎn)相連的傾向性。這種傾向性普遍存在，比如，在刻畫朋友關(guān)系的網(wǎng)絡(luò)中，人們偏向于和與他們有共同語言、相同愛好的人交朋友，這就是一種傾向性，此時(shí)，這個(gè)網(wǎng)絡(luò)被視為是同配混合的。在網(wǎng)絡(luò)中，常常關(guān)注一種傾向性——度的同配性，可以采用如下形式度量：

2.3 連通片規(guī)模

連通片是指網(wǎng)絡(luò)中一些節(jié)點(diǎn)的集合，使得集合中的任意兩節(jié)點(diǎn)至少有1條路徑相連，其中最大的那個(gè)就是巨連通片(GCC)。本文采用邊滲流的思想來研究?jī)深愃惴ㄉ傻木W(wǎng)絡(luò)結(jié)構(gòu)，具體而言，即通過隨機(jī)刪除網(wǎng)絡(luò)中一定比例p的邊來觀察巨連通片規(guī)模的變化，結(jié)果對(duì)研究與控制網(wǎng)絡(luò)上疾病的傳播有著非常重要的啟示[10-11]。

3 結(jié)果

為了對(duì)比兩類算法生成的網(wǎng)絡(luò)在大尺度結(jié)構(gòu)特征上的差異，統(tǒng)一采用度分布-泊松分布來生成網(wǎng)絡(luò)，其中：平均度n=5；網(wǎng)絡(luò)總節(jié)點(diǎn)數(shù)N=104。

首先驗(yàn)證GCM算法的可行性。圖3給出的是分別取定pt=0.22與pt=0.6的情形下，由GCM算法生成的網(wǎng)絡(luò)的聚類系數(shù)的取值情況。從圖3可以看出：就生成的網(wǎng)絡(luò)的聚類而言，GCM算法具有良好的穩(wěn)定性，從而在一定程度上證實(shí)了該算法的可行性。

圖3 在不同pt值下，GCM算法生成的100個(gè)網(wǎng)絡(luò)的聚類系數(shù)的箱圖

值得注意的是，圖4表明，相較于BV算法，GCM算法以一種更同質(zhì)的方式引入聚類。既然事先把網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的局部聚類值預(yù)設(shè)為pt，那么這個(gè)結(jié)果是可以預(yù)見的。同時(shí)也注意到，在引入較高水平聚類的情形下，兩種算法均會(huì)使得網(wǎng)絡(luò)聚類分布更加異質(zhì)。此外，仍需指出的是，GCM算法并不能實(shí)現(xiàn)對(duì)網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的局部聚類進(jìn)行預(yù)期控制，一種常見的結(jié)果就是出現(xiàn)局部聚類嚴(yán)重偏離pt的節(jié)點(diǎn)，如圖4中用符號(hào)“+”所表示的節(jié)點(diǎn)，不過也正如圖4所示，這種狀況很少發(fā)生。

圖4 不同pt值下局部聚類的分布(GCM與BV算法分別生成的100個(gè)網(wǎng)絡(luò)的局部聚類的箱圖)

在網(wǎng)絡(luò)平均最短距離方面，在相等的聚類水平下，兩類算法并沒有表現(xiàn)出明顯的差異。不過也注意到，平均最短距離會(huì)隨著聚類水平的升高而增大，見表1。對(duì)此，一種可能的解釋是：當(dāng)網(wǎng)絡(luò)存在較高水平聚類時(shí)，網(wǎng)絡(luò)節(jié)點(diǎn)趨向于聚集成一些小的叢，使得在給定網(wǎng)絡(luò)的度分布、網(wǎng)絡(luò)的總邊數(shù)為定值的前提下，更多的邊存在于節(jié)點(diǎn)叢內(nèi)，于是處于節(jié)點(diǎn)叢內(nèi)外的節(jié)點(diǎn)間的路徑長(zhǎng)度會(huì)增大，最終平均距離隨之增大。

在網(wǎng)絡(luò)的度的同配性方面，兩者卻表現(xiàn)出了較大的差異，見表1。關(guān)于這一點(diǎn)，給出如下可能的解釋：網(wǎng)絡(luò)中的任一節(jié)點(diǎn)v出現(xiàn)在集合Y中的次數(shù)是近似正比于(dv-1)dv的，使得兩個(gè)度較大的節(jié)點(diǎn)更傾向于連接在一起，因此網(wǎng)絡(luò)會(huì)呈現(xiàn)出較大的度的同配性。此外，值得注意的是，聚類水平的升高并未引起網(wǎng)絡(luò)的度的同配性發(fā)生較大的改變。另外，從表1中還可以看出，BV算法在引入較低水平聚類時(shí)并未導(dǎo)致網(wǎng)絡(luò)呈現(xiàn)出較大的度的同配性，這是BV算法很重要的一個(gè)優(yōu)勢(shì)。

表1 幾類網(wǎng)絡(luò)結(jié)構(gòu)特征的統(tǒng)計(jì)量

AlgorithmlC=0.2C=0.35rC=0.2C=0.35GCM6.731 27.503 90.212 10.234 7BV6.608 57.614 03.582 1e-5-8.742 8e-5

最后，在網(wǎng)絡(luò)的恢復(fù)力方面，兩類算法呈現(xiàn)出不同的現(xiàn)象。具體地說，隨著聚類水平的升高，由BV算法生成的網(wǎng)絡(luò)的巨連通片對(duì)邊的移除更加敏感，特別是當(dāng)邊的移除比例達(dá)到一定數(shù)值時(shí)；相對(duì)而言，GCM算法則并不明顯。不過，對(duì)兩類算法而言，滲流閾值依舊存在，而且在不同聚類水平下，閾值并未表現(xiàn)出明顯的不同，見圖5。

圖5 不同概率下p巨連通片的規(guī)模(結(jié)果是500次值的平均，其中對(duì)100個(gè)網(wǎng)絡(luò)中的每一個(gè)重復(fù)5次隨機(jī)刪邊過程)

4 結(jié)束語

通過對(duì)兩類生成聚類網(wǎng)絡(luò)算法的對(duì)比不難看出，在引入較低水平聚類時(shí)，兩類算法生成的聚類網(wǎng)絡(luò)表現(xiàn)出諸多相似之處，因此認(rèn)為GCM算法可以在一定程度上替代BV算法。當(dāng)然，GCM算法自身也存在著許多不足之處，比如很重要的一點(diǎn)(從圖3中也不難看出)，GCM算法只能引入較低水平的聚類，而BV算法就靈活得多。此外，文獻(xiàn)[12]已經(jīng)表明，不同算法生成的聚類網(wǎng)絡(luò)在網(wǎng)絡(luò)結(jié)構(gòu)上具有很大差異，這就意味著，如果要研究疾病在聚類網(wǎng)絡(luò)上的傳播就必須考慮不同網(wǎng)絡(luò)結(jié)構(gòu)所可能帶來的影響，不過目前的進(jìn)展還不能給出一個(gè)令人滿意的回答。