集合擴(kuò)充的社團(tuán)分解算法

李圓媛，余汪建，何敏華

（1.武漢工程大學(xué)理學(xué)院，湖北 武漢 430074；2.智能機(jī)器人湖北省重點(diǎn)實(shí)驗(yàn)室，湖北 武漢 430074）

0 引 言

二十世紀(jì)末以來，隨著Internet等信息技術(shù)的迅猛發(fā)展，人類社會(huì)已經(jīng)進(jìn)入了網(wǎng)絡(luò)時(shí)代［1］，人們也把目光聚焦到復(fù)雜網(wǎng)絡(luò)的研究上來.近些年來，復(fù)雜網(wǎng)絡(luò)研究滲透到了各個(gè)領(lǐng)域，科學(xué)的理解復(fù)雜網(wǎng)絡(luò)的各種定量與定性的特征是網(wǎng)絡(luò)時(shí)代的一個(gè)非常有挑戰(zhàn)性的科學(xué)研究課題［2］.

許多真實(shí)網(wǎng)絡(luò)研究顯示絕大部分的網(wǎng)絡(luò)存在一個(gè)相同的特征，被稱之為網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu).它是指網(wǎng)絡(luò)中的全部節(jié)點(diǎn)可以被劃分成若干個(gè)群體，每個(gè)群體里面的節(jié)點(diǎn)的連接相對(duì)稠密，而群體之間的節(jié)點(diǎn)的連接相對(duì)稀疏［3］.對(duì)網(wǎng)絡(luò)中社團(tuán)結(jié)構(gòu)的研究是了解整個(gè)網(wǎng)絡(luò)結(jié)構(gòu)和功能的重要途徑［4］.

1 網(wǎng)絡(luò)圖的定義和基本概念

對(duì)網(wǎng)絡(luò)進(jìn)行社團(tuán)分解的操作是基于網(wǎng)絡(luò)圖的表示，在介紹復(fù)雜網(wǎng)絡(luò)的社團(tuán)分解算法前首先介紹網(wǎng)絡(luò)圖的定義和基本概念.網(wǎng)絡(luò)圖G可以用集合（V，Ψ）表示，V（G）＝｛1，2，...，N｝表示網(wǎng)絡(luò)圖G的節(jié)點(diǎn)集合，N表示網(wǎng)絡(luò)圖的節(jié)點(diǎn)總數(shù)，Ψ（G）＝｛（i1，j1），（i2，j2），...，（iE，jE）｝表示邊的集合，用E 表示邊的總數(shù)目，若（i，j）＝（j，i）則該網(wǎng)絡(luò)圖被稱為無向網(wǎng)絡(luò)圖，反之則被稱為有向網(wǎng)絡(luò)圖，在本文中只討論無向無權(quán)網(wǎng)絡(luò)圖.無向無權(quán)網(wǎng)絡(luò)圖的鄰接矩陣A（i，j）是一個(gè)對(duì)稱的0－1矩陣，如果節(jié)點(diǎn)i，j之間有聯(lián)系則ai，j＝1，否則為0.對(duì)于一個(gè)節(jié)點(diǎn)i的度定義為與節(jié)點(diǎn)i相連接的邊的數(shù)目.

2 社團(tuán)分解算法綜述

現(xiàn)在對(duì)于復(fù)雜網(wǎng)絡(luò)的社團(tuán)分解有許多成熟的方法，如基于圖的Laplace矩陣特征向量的譜平分法［5］，GN 算法［3］、NF算法［6］等.一個(gè) 有n 個(gè)節(jié)點(diǎn)的無向圖G的Laplace矩陣是一個(gè)n×n維的對(duì)稱矩陣L，理論上已經(jīng)證明，不為零的特征值所對(duì)應(yīng)的特征向量的各元素中，同一個(gè)社團(tuán)內(nèi)的節(jié)點(diǎn)對(duì)應(yīng)的元素是近似相等的.譜平分法的基本思想就是根據(jù)網(wǎng)絡(luò)的Laplace矩陣的第二小的特征值λ2將網(wǎng)絡(luò)分成兩個(gè)社團(tuán).如果網(wǎng)絡(luò)實(shí)際是由兩個(gè)社團(tuán)構(gòu)成，用譜平分法效果很好，但是如果由多個(gè)以上的社團(tuán)構(gòu)成，則體現(xiàn)不出其優(yōu)點(diǎn).GN算法是Girvan和Newman提出的一種探索網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)的分裂算法.Girvan和Newman提出用邊介數(shù)來標(biāo)記每條邊對(duì)網(wǎng)絡(luò)連通性的影響.GN算法能夠彌補(bǔ)一些傳統(tǒng)算法的缺陷，但是在復(fù)雜網(wǎng)絡(luò)中社團(tuán)的數(shù)目未知的情況下，GN算法無法確定這種分解要在哪一步終止.GN算法雖然準(zhǔn)確度比較高，但是其算法復(fù)雜度比較大，Newman在GN算法的基礎(chǔ)上基于貪婪算法思想提出了一種快速的凝聚算法 （簡(jiǎn)稱NF算法），該算法可以用于處理節(jié)點(diǎn)數(shù)達(dá)到100萬的大型網(wǎng)絡(luò)［7］.

3 集合擴(kuò)充的社團(tuán)分解算法

3.1 算法原理

對(duì)復(fù)雜網(wǎng)絡(luò)進(jìn)行社團(tuán)分解的本質(zhì)就是要找出某些節(jié)點(diǎn)聯(lián)系是緊密的，對(duì)于每一個(gè)點(diǎn)來說，它必可以劃分到一個(gè)聯(lián)系最緊密的點(diǎn)集中，在這里需要做的就是判斷每個(gè)點(diǎn)是否和某個(gè)社團(tuán)聯(lián)系緊密，如果是，那么該點(diǎn)就可以劃分到這個(gè)社團(tuán)中.

假設(shè)有了一個(gè)節(jié)點(diǎn)的集合S＝（V，G），V表示該集合中的所有節(jié)點(diǎn)，G表示該集合中節(jié)點(diǎn)間的邊.現(xiàn)在對(duì)于一個(gè)新的節(jié)點(diǎn)vn，為了判斷vn是否可以加入集合S，先定義一個(gè)參數(shù)：PQ＝oe／ie，式中的oe表示一個(gè)節(jié)點(diǎn)在S內(nèi)而另一個(gè)節(jié)點(diǎn)不在S中的邊的總數(shù)，ie表示S中的邊的總數(shù).該式的物理意義就是社團(tuán)同外部聯(lián)系的邊的數(shù)目與社團(tuán)內(nèi)部邊的數(shù)目的比值.在此先計(jì)算PQ（S），再計(jì)算出加入點(diǎn)vn之后的PQ（Sn），如果PQ（Sn）＜ PQ（S），那么就認(rèn)為vn和集合S＝（V，G）的聯(lián)系是比較緊密的，就把節(jié)點(diǎn)vn加入到集合S＝（V，G）中來.

3.2 算法流程

參照算法原理，給出該算法如下運(yùn)行流程：

步驟一：在已知的節(jié)點(diǎn)集中選取一個(gè)度最大的節(jié)點(diǎn)，找到與該點(diǎn)有關(guān)聯(lián)的所有節(jié)點(diǎn)，選取其中一個(gè)度最小的點(diǎn)，和第一個(gè)節(jié)點(diǎn)構(gòu)成一個(gè)集合.

步驟二：對(duì)于步驟一中得到的集合，找到與該集合相關(guān)的所有節(jié)點(diǎn)，分別計(jì)算這些節(jié)點(diǎn)加入該集合后的PQ值并和之前集合的PQ值進(jìn)行比較，判斷能否加入該集合，如果可以加入，則加入該集合.

步驟三：重復(fù)步驟二，將這個(gè)兩點(diǎn)的集合不斷的擴(kuò)充，直到整個(gè)網(wǎng)絡(luò)中剩余的點(diǎn)都不符合加入該集合的條件為止，這樣就得到了劃分出來的一個(gè)社團(tuán).

步驟四：從網(wǎng)絡(luò)圖中去掉已經(jīng)找出的社團(tuán)，重復(fù)步驟一、步驟二、步驟三直到網(wǎng)絡(luò)中的節(jié)點(diǎn)完全劃分.

3.3 算法分析

這個(gè)算法的優(yōu)點(diǎn)是不需要考慮整個(gè)網(wǎng)絡(luò)的結(jié)構(gòu)，劃分的思維比較清晰，同時(shí)可以根據(jù)不同的需求對(duì)網(wǎng)絡(luò)進(jìn)行不同的劃分.在某些網(wǎng)絡(luò)中，并不需要對(duì)整個(gè)網(wǎng)絡(luò)進(jìn)行社團(tuán)結(jié)構(gòu)劃分，只是需要找出其中的部分社團(tuán)，在這種情況下，運(yùn)用筆者提出的算法具有運(yùn)算簡(jiǎn)便、運(yùn)算量小的特點(diǎn).而GN算法和NF算法在運(yùn)算的時(shí)候都需要考慮整個(gè)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，運(yùn)算量很大.同時(shí)本文的算法可以通過調(diào)整起始規(guī)則或者起始集合來得到不同的社團(tuán)結(jié)構(gòu)劃分.同譜平分算法相比，筆者提出的算法可以將整個(gè)復(fù)雜網(wǎng)絡(luò)分成任意個(gè)社團(tuán)結(jié)構(gòu)，而譜平分法僅能將網(wǎng)絡(luò)分成兩個(gè)社團(tuán).

3.4 算法測(cè)試

為了測(cè)試程序的正確性和算法的可行性，構(gòu)造了一個(gè)社團(tuán)結(jié)構(gòu)很清晰的網(wǎng)絡(luò)圖，如圖1所示.從圖中可以很清楚的看到該網(wǎng)絡(luò)可以劃分為四個(gè)比較合理的社團(tuán).將四個(gè)社團(tuán)以節(jié)點(diǎn)集合的形式表現(xiàn)出來為（11，12，24，27，29，16，28，22），（6，8，18，19），（9，21，17，7，3，23，25），（1，4，15，2，5，30，20，13，14，26，10）.先將該網(wǎng)絡(luò)的鄰接矩陣進(jìn)行存儲(chǔ)，然后應(yīng)用筆者提出的算法，得到如表1所示的結(jié)果.從該表中看到，算法也將網(wǎng)絡(luò)分成了四個(gè)社團(tuán)，并且結(jié)果與預(yù)期的一致，那么說明文中提出的算法在此社團(tuán)結(jié)構(gòu)比較清晰的網(wǎng)絡(luò)中是可以實(shí)現(xiàn)的.

圖1 社團(tuán)結(jié)構(gòu)清晰的網(wǎng)絡(luò)圖Fig.1 Aschematic representation of a network with community structure

表1 圖1的測(cè)試結(jié)果Table 1 The test results of figure 1

為了進(jìn)一步測(cè)試算法的可行性，使用了著名的Wayne Zachary觀察的美國(guó)大學(xué)空手道俱樂部成員間的人際關(guān)系網(wǎng)絡(luò)的例子［8］，如圖2所示，該例子具有很強(qiáng)的實(shí)際意義，把該例子應(yīng)用到筆者提出的算法程序測(cè)試中來，將該網(wǎng)絡(luò)的鄰接矩陣進(jìn)行運(yùn)算后得到如表2所示的結(jié)果.從表2中看到該算法將網(wǎng)絡(luò)分成了兩個(gè)社團(tuán)，第一個(gè)社團(tuán)和圖2中圓形表示的社團(tuán)基本符合，第二個(gè)社團(tuán)和圖2中方形表示的社團(tuán)基本符合.除了節(jié)點(diǎn)3的劃分和GN算法的劃分有區(qū)別外，其余的結(jié)果和使用GN算法的結(jié)果一致.從直觀上來說，也不能確定節(jié)點(diǎn)3到底分在哪一個(gè)社團(tuán)比較合適，這說明筆者提出的算法在結(jié)構(gòu)不是很清晰的實(shí)際網(wǎng)絡(luò)中進(jìn)行社團(tuán)劃分還是具有一定意義的.

圖2 空手道俱樂部網(wǎng)絡(luò)圖Fig.2 The friendship network from Zachary＇s karate club

表2 圖2的測(cè)試結(jié)果Table 2 The test results of figure 2

4 結(jié) 語

復(fù)雜網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)分解是一個(gè)富有挑戰(zhàn)性和應(yīng)用前景性的研究領(lǐng)域.本文提出了通過集合擴(kuò)充的方式劃分復(fù)雜網(wǎng)絡(luò)中社團(tuán)結(jié)構(gòu)的算法.并對(duì)提出的算法進(jìn)行了詳細(xì)的介紹，給出了算法的理論基礎(chǔ)和算法流程，并對(duì)算法進(jìn)行了實(shí)例測(cè)試.從測(cè)試結(jié)果可以看出，本文提出的基于集合擴(kuò)充的社團(tuán)分解算法具有不錯(cuò)的效率，本文中僅僅討論了復(fù)雜網(wǎng)絡(luò)社團(tuán)分解算法在無向無權(quán)圖中的運(yùn)行，而現(xiàn)實(shí)生活中很多實(shí)際網(wǎng)絡(luò)都是有向的有權(quán)的.因此如何定義和劃分有向網(wǎng)中的社團(tuán)結(jié)構(gòu)，有向網(wǎng)中的環(huán)型結(jié)構(gòu)與集團(tuán)結(jié)構(gòu)的關(guān)系，以及如何探索有向網(wǎng)中的層次問題都是一些值得我們關(guān)注的問題.

［1］汪小帆，李翔，陳關(guān)榮.復(fù)雜網(wǎng)絡(luò)理論及其應(yīng)用［M］.北京：清華大學(xué)出版社，2006.

［2］Barabasi A L，F(xiàn)rangos J.Linked：The New Science of Networks［M］.Massachusetts：Perseus Books Group，2002.

［3］Girvan M，Newman M E J.Community structure in social and biological networks［J］.Proceedings of the National Academy of Sciences of the United States of America，2001，99（12）：7821－7826.

［4］李曉佳，張鵬，狄增如，等.復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)［J］.復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)，2008，5（3）：20－42.LI Xiao－jia，ZHANG Peng，DI Zeng－ru，et al.Community Structure in Complex Networks［J］.Complex Systems and Complexity Science，2008，5（3）：19－42.（in Chinese）

［5］Pothen A，Simon H D，Liou K P.Partitioning sparse matrices with eigenvectors of graphs［J］.SIAM Journal on Matrix Analysis and Applications，1990，11（3）：430－452.

［6］Newman M E J.Fast algorithm for detecting community structure in networks［J］.Physical Review E，2004，69（6）： 066133－ 066137.

［8］Zachary W W.An information flow model for conflict and fission in small groups［J］.Journal of Anthropological Research，1977，33（4）：452－473.