一種基于三角環(huán)的社區(qū)發(fā)現(xiàn)算法

摘 要 在大型復(fù)雜網(wǎng)絡(luò)中自動(dòng)搜尋或發(fā)現(xiàn)社區(qū)具有重要的實(shí)際應(yīng)用價(jià)值。本文把超圖模型以及基于此的聚類算法應(yīng)用到社區(qū)結(jié)構(gòu)發(fā)現(xiàn)領(lǐng)域。對(duì)于簡(jiǎn)單圖的社區(qū)發(fā)現(xiàn)，引入了邊凝聚系數(shù)和三角環(huán)等概念，提出了基于三角環(huán)的社區(qū)結(jié)構(gòu)發(fā)現(xiàn)方法。通過Zachary網(wǎng)絡(luò)的實(shí)例驗(yàn)證和算法的對(duì)比分析，證明了該算法在時(shí)間復(fù)雜度上能提高一個(gè)數(shù)量級(jí)。

關(guān)鍵詞 社區(qū)結(jié)構(gòu) 三角環(huán) 邊凝聚系數(shù) 社會(huì)網(wǎng)絡(luò)

1 引言

在現(xiàn)實(shí)生活中存在著各種各樣的網(wǎng)絡(luò)系統(tǒng)，如人際關(guān)系網(wǎng)、合作網(wǎng)、交通運(yùn)輸網(wǎng)、計(jì)算機(jī)網(wǎng)等。許多現(xiàn)實(shí)系統(tǒng)的網(wǎng)絡(luò)模型是介于完全規(guī)則和完全隨機(jī)之間的，這種網(wǎng)絡(luò)被稱為復(fù)雜網(wǎng)絡(luò)[1]。復(fù)雜網(wǎng)絡(luò)不僅具有小世界、無標(biāo)度特性還具有社區(qū)結(jié)構(gòu)[2]的特性。社區(qū)內(nèi)部的節(jié)點(diǎn)之間的聯(lián)系相對(duì)緊密，而社區(qū)之間的聯(lián)系相對(duì)稀疏[3]。復(fù)雜網(wǎng)絡(luò)中的社區(qū)發(fā)現(xiàn)的研究起源于社會(huì)學(xué)的研究工作。能夠在大型復(fù)雜網(wǎng)絡(luò)中自動(dòng)搜尋或發(fā)現(xiàn)社區(qū)具有重要的實(shí)用價(jià)值，如社會(huì)網(wǎng)絡(luò)中的社區(qū)代表根據(jù)興趣或背景而形成的真實(shí)的社會(huì)團(tuán)體[4]，發(fā)現(xiàn)社會(huì)網(wǎng)絡(luò)中的這些社區(qū)有助于我們更好地理解和應(yīng)用社會(huì)網(wǎng)絡(luò)。目前，社區(qū)發(fā)現(xiàn)的算法很多，其中Kernighan-Lin算法[5]、Laplace圖特征值的譜二分法[6]、GN算法[7]等比較經(jīng)典。其中GN算法是Newman和Girvan在其研究中提出了基于邊介數(shù)的分割方法，盡管該方法計(jì)算量很大，但由于其性能優(yōu)越而成為社區(qū)發(fā)現(xiàn)研究的重要參考模型。

盡管人們對(duì)復(fù)雜網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)問題已進(jìn)行了大量的研究，但是仍然還存在一些目前無法解決的問題，如社區(qū)的概念雖然大量使用，但缺乏嚴(yán)格的數(shù)學(xué)定義；大多數(shù)的發(fā)現(xiàn)算法計(jì)算量很大；很多算法不是針對(duì)異構(gòu)數(shù)據(jù)集。因此，復(fù)雜網(wǎng)絡(luò)中的社區(qū)發(fā)現(xiàn)研究還遠(yuǎn)沒有形成體系，有許多工作有待于進(jìn)一步完善[8]。

本文給出一種新的社區(qū)發(fā)現(xiàn)算法，根據(jù)三角環(huán)來判斷社區(qū)。本文的結(jié)構(gòu)如下：第2節(jié)算法的整體描述；第3節(jié)對(duì)算法進(jìn)行實(shí)例驗(yàn)證并與經(jīng)典算法作對(duì)比；第4節(jié)總結(jié)全文。

2 算法介紹及分析

2.1 相關(guān)概念的引入

三角環(huán)：網(wǎng)絡(luò)中邊數(shù)為3的閉合回路形成的三角形。如圖1中，節(jié)點(diǎn)3、4、6；節(jié)點(diǎn)4、5、6等可以構(gòu)成三角環(huán)的形式。

點(diǎn)凝聚系數(shù)：對(duì)于某個(gè)點(diǎn)的鄰居節(jié)點(diǎn)之間實(shí)際存在的邊數(shù)與鄰居節(jié)點(diǎn)之間可能存在的最大邊數(shù)之比。一個(gè)網(wǎng)絡(luò)的凝聚系數(shù)就是網(wǎng)絡(luò)中節(jié)點(diǎn)凝聚系數(shù)的平均值。如圖1：節(jié)點(diǎn)1的鄰居節(jié)點(diǎn)分別是2、3、4、5、6，共5個(gè)節(jié)點(diǎn)。它們之間存在的最大邊數(shù)為：5（5-1）/2=10；實(shí)際上這5個(gè)節(jié)點(diǎn)間的有7條邊，那么節(jié)點(diǎn)1的點(diǎn)凝聚系數(shù)為：7/10=0.7。

邊凝聚系數(shù)：借助于節(jié)點(diǎn)的凝聚系數(shù)，來引入邊的凝聚系數(shù)概念。一條邊的邊凝聚系數(shù)定義為包含該邊的三角環(huán)所占的比例：

Cij= （1）

其中，ki，kj分別表示節(jié)點(diǎn)i和節(jié)點(diǎn)j的度數(shù)，zij表示網(wǎng)絡(luò)中實(shí)際包含的三角環(huán)的個(gè)數(shù)。上式中的分母表示包含該邊的最大可能的三角環(huán)的個(gè)數(shù)。圖1中，節(jié)點(diǎn)3和節(jié)點(diǎn)6的度數(shù)分別是5和4，則最多形成min（5-1，3-1）=3個(gè)三角環(huán)；而實(shí)際上包邊E3，6的三角環(huán)有三個(gè)：節(jié)點(diǎn)1、3、6，節(jié)點(diǎn)3、5、6，節(jié)點(diǎn)3、4、6，所以C3，6=4/3。

將整個(gè)網(wǎng)絡(luò)G視為圖，那么一個(gè)社區(qū)V實(shí)際上就是G的子圖。社區(qū)V中的一個(gè)節(jié)點(diǎn)i的度ki來自兩部分，分別是V的內(nèi)部（k（V）=A）和V的外部[（k（V）=A）] 。下面給出社區(qū)緊密程度的兩種級(jí)別[9]：

如果社區(qū)V內(nèi)的任意一個(gè)節(jié)點(diǎn)i的k（V）均大于k（V），即k（V）>k（V），則稱該社區(qū)是強(qiáng)連接社區(qū)。

如果社區(qū)V內(nèi)的所有節(jié)點(diǎn)的k（V）和大于的和k（V），即k（V）>k（V），則稱該社區(qū)為弱連接社區(qū)。

2.2 算法的思想及主要流程

前面提到的GN算法是一種分裂算法。它的基本思想是，通過不斷的從網(wǎng)絡(luò)中移除介數(shù)最大的邊將整個(gè)網(wǎng)絡(luò)分解成不同社區(qū)。在這里，邊的介數(shù)定義為網(wǎng)絡(luò)中經(jīng)過該邊的最短路徑的數(shù)目。這種算法為區(qū)分一個(gè)社區(qū)內(nèi)部邊和連接社區(qū)之間的邊提供了一種有效的度量標(biāo)準(zhǔn)。

GN算法雖然能彌補(bǔ)一些傳統(tǒng)算法的不足，但是一般要指定社區(qū)的個(gè)數(shù)，否則，該算法不知道要將網(wǎng)絡(luò)分解到什么程度停止。另外，該算法的時(shí)間復(fù)雜度較高，為O（n3）。算法效率較低的一個(gè)重要原因是邊介數(shù)的計(jì)算開銷大。針對(duì)上述情況，這里提出一種基于三角環(huán)的社區(qū)發(fā)現(xiàn)方法（Triangle Ring Community Detecting簡(jiǎn)稱TRCD算法）?？紤]無向無權(quán)重的形式，用鄰接矩陣Ai，j表示節(jié)點(diǎn)間的關(guān)系，有邊相連則值為1，無邊相連則為0。

上述兩個(gè)社區(qū)的級(jí)別可以作為判斷子圖是否為一個(gè)社區(qū)的標(biāo)準(zhǔn)，只有滿足上述兩個(gè)定義的子圖才能作為一個(gè)社區(qū)。首先從整個(gè)網(wǎng)絡(luò)開始，不斷的刪除邊，直到不存在滿足上述定義的社區(qū)為止。本文中的方法和前面的GN算法類似，都是分裂式算法。該方法不是根據(jù)邊介數(shù)來選擇要?jiǎng)h除的邊，而是根據(jù)邊凝聚系數(shù)這個(gè)新的指標(biāo)。

根據(jù)上述基本思想得到算法的具體步驟如下：

Step1：根據(jù)公式（1）所示，計(jì)算整個(gè)網(wǎng)絡(luò)中的每一條邊的凝聚系數(shù)Cij；

Step2：刪除凝聚系數(shù)最小的邊Eij；

Step3：重新計(jì)算以i和j為頂點(diǎn)的所有邊的凝聚系數(shù)，而其它的邊不需要重新計(jì)算；

Step4：返回Step2，直到網(wǎng)絡(luò)中不存在符合上述定義的社區(qū)。

2.3 算法分析

對(duì)于一個(gè)含有n個(gè)節(jié)點(diǎn)m條邊的網(wǎng)絡(luò)，整個(gè)算法運(yùn)行的時(shí)間為O（m4/n2）。顯然該算法的時(shí)間復(fù)雜度要低于GN的時(shí)間復(fù)雜度。因?yàn)樗紤]的是局部信息，去邊以后無須所有的邊重新計(jì)算，所以降低了時(shí)間復(fù)雜度。該算法依賴于網(wǎng)絡(luò)中的三角環(huán)，如果網(wǎng)絡(luò)中三角環(huán)的數(shù)量很少，該方法將失去意義。大量的實(shí)例研究表明，社會(huì)網(wǎng)絡(luò)中三角環(huán)的數(shù)量比較大，而非社會(huì)網(wǎng)絡(luò)中，三角環(huán)的數(shù)量則相對(duì)較少。所以這種方法更適合于社會(huì)網(wǎng)絡(luò)。

3 實(shí)例驗(yàn)證

3.1 在Zachary網(wǎng)絡(luò)上的實(shí)驗(yàn)

圖2所示是某大學(xué)空手道俱樂部中34個(gè)成員之間的社會(huì)關(guān)系網(wǎng)絡(luò)，曾是人類學(xué)家懷恩扎卡利（Wayne Zachary）在20世紀(jì)70年代研究的對(duì)象。Zachary網(wǎng)絡(luò)在復(fù)雜網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)分析中已經(jīng)成為一個(gè)經(jīng)典問題，成為了衡量社區(qū)結(jié)構(gòu)劃分算法準(zhǔn)確性的標(biāo)準(zhǔn)[10]。在調(diào)查研究過程中，該俱樂部的主管與校長(zhǎng)因是否抬高俱樂部收費(fèi)的問題產(chǎn)生了爭(zhēng)執(zhí)。結(jié)果，這個(gè)俱樂部分裂成了兩個(gè)分別以校長(zhǎng)和主管為核心的小俱樂部。下面以Zachary網(wǎng)絡(luò)為例檢驗(yàn)TRCD算法在實(shí)際網(wǎng)絡(luò)中的應(yīng)用。

按照文中算法的流程，得到最終的結(jié)果如下圖3所示，為了與圖2方便比較，圖3中沒有將邊去掉。其中圓形節(jié)點(diǎn)代表由節(jié)點(diǎn)27得到社區(qū)A，方形節(jié)點(diǎn)代表另一個(gè)社區(qū)B。A和B社區(qū)就代表著以校長(zhǎng)和主管為核心的小俱樂部，這個(gè)結(jié)果同實(shí)際存在的社區(qū)是一致的。

3.2 與經(jīng)典算法的比較

從算法準(zhǔn)確性和算法的復(fù)雜度兩方面將文中的算法與三種經(jīng)典的算法作對(duì)比。

GN算法是一種分裂方法，其基本思想是不斷地從網(wǎng)絡(luò)中移除介數(shù)最大的邊。譜二分法是利用網(wǎng)絡(luò)結(jié)構(gòu)的Laplace矩陣中不為0的特征值所對(duì)應(yīng)的特征向量和同一個(gè)社區(qū)內(nèi)的節(jié)點(diǎn)對(duì)應(yīng)的元素近似值的原理對(duì)網(wǎng)絡(luò)社區(qū)進(jìn)行劃分。這兩種算法應(yīng)用到Zachary網(wǎng)絡(luò)中所得到的社區(qū)結(jié)構(gòu)如圖4所示。

其中圖4中所有的圓形節(jié)點(diǎn)是在同一社區(qū)，其余節(jié)點(diǎn)屬于另一個(gè)社區(qū)。K-L算法是一種試探優(yōu)化法，它是一種利用貪婪算法將復(fù)雜網(wǎng)絡(luò)劃分為兩個(gè)社區(qū)的二分法。若將K-L算法應(yīng)用到Zachary網(wǎng)絡(luò)，得到的結(jié)果和文中算法一致，如上圖3。

圖3和圖4的區(qū)別是：節(jié)點(diǎn)3被劃分到兩個(gè)不同的社區(qū)。而真實(shí)的社區(qū)結(jié)構(gòu)如圖5所示，所以說，GN算法和譜二分法的結(jié)果使得節(jié)點(diǎn)3被錯(cuò)誤劃分。并且譜二分法僅適用于由兩個(gè)社區(qū)組成的大網(wǎng)絡(luò)結(jié)構(gòu)，而GN算法對(duì)網(wǎng)絡(luò)社區(qū)進(jìn)行劃分時(shí)必須事先知道網(wǎng)絡(luò)中存在的社區(qū)個(gè)數(shù)。雖然K-L算法得到的社區(qū)跟實(shí)際結(jié)果一致，但是必須提前知道兩個(gè)社區(qū)的大小分別是16和18，因此K-L算法很難適用于實(shí)際網(wǎng)絡(luò)。這也說明了經(jīng)典算法存在一些不足。對(duì)TRCD算法而言，在進(jìn)行社區(qū)劃分之前不需要指定社區(qū)個(gè)數(shù)，這是一種自然劃分，能夠得到網(wǎng)絡(luò)中實(shí)際存在的社區(qū)結(jié)構(gòu)，而且算法的準(zhǔn)確性較高，所以該算法能克服其他算法的一些不足。

對(duì)于一個(gè)含有n個(gè)節(jié)點(diǎn)m條邊的網(wǎng)絡(luò)，TRCD算法的時(shí)間復(fù)雜度為O（m），空間復(fù)雜度是O（m4/n2）。將該算法與經(jīng)典的三種算法的復(fù)雜度作了對(duì)比，如表1。

經(jīng)過對(duì)比分析，我們發(fā)現(xiàn)TRCD算法的思想易于理解，步驟簡(jiǎn)潔；算法的準(zhǔn)確性較高；在復(fù)雜度方面，該算法也有一定的提高。

4 總結(jié)

文中的TRCD算法，是在研究了近年來常見的一些方法的基礎(chǔ)上提出了根據(jù)邊的凝聚系數(shù)來求得下一步將要去掉的邊，因?yàn)榭紤]的是局部信息，去邊以后不需要重新計(jì)算所有的邊，所以與GN算法相比降低了時(shí)間復(fù)雜度。通過與經(jīng)典算法的比較，可以發(fā)現(xiàn)TRCD算法在算法的準(zhǔn)確性和算法復(fù)雜度方面都有一定的優(yōu)越性。特別地，該算法比較適合三角關(guān)系較多的網(wǎng)絡(luò)。