兩類算法生成的聚類網絡的大尺度結構特征的比較

胡燕萍，李金仙，李偉強

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

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

1 聚類介紹以及算法描述

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

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

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

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

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

1.1 GCM算法

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

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

2) 對于每個節(jié)點v，構造一個由“半邊(half-edge)”組成的集合Xv，元素為節(jié)點v的δv個副本(copies)，也構造一個由“角(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é)點中的任意兩個，判斷它們之間是否已存在連邊。如果沒有，則在它們之間構造一條邊。

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

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

4) 重復步驟3)。

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

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

1.2 BV算法

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

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

圖1 斷邊重連示意圖

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

2 網絡的大尺度結構

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

2.1 路徑長度

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

常使用下式來刻畫網絡的平均路徑長度：

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

2.2 同配混合

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

2.3 連通片規(guī)模

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

3 結果

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

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

圖3 在不同pt值下，GCM算法生成的100個網絡的聚類系數的箱圖

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

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

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

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

表1 幾類網絡結構特征的統(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

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

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

4 結束語

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