兩類算法生成的聚類網(wǎng)絡的大尺度結(jié)構(gòu)特征的比較

胡燕萍，李金仙，李偉強

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

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

1 聚類介紹以及算法描述

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

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

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

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

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

1.1 GCM算法

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

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

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

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

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

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

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

4) 重復步驟3)。

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

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

1.2 BV算法

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

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

圖1 斷邊重連示意圖

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

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

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

2.1 路徑長度

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

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

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

2.2 同配混合

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

2.3 連通片規(guī)模

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

3 結(jié)果

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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