劉晨晨,許 英

(新疆財經(jīng)大學統(tǒng)計與數(shù)據(jù)科學學院,新疆 烏魯木齊 830012)

二分網(wǎng)絡(luò)是復(fù)雜網(wǎng)絡(luò)中的一種重要類型,它可以將用戶-產(chǎn)品購買關(guān)系[1]、科學家-論文合作關(guān)系[2]、蛋白質(zhì)-配體作用關(guān)系[3]等相關(guān)關(guān)系直觀地表示出來.社團檢測在挖掘二分網(wǎng)絡(luò)的結(jié)構(gòu)、預(yù)測對象的行為特征、提取網(wǎng)絡(luò)的有用信息等方面有廣泛應(yīng)用[4].目前,二分網(wǎng)絡(luò)社團檢測方法主要有2種:一是將二分網(wǎng)絡(luò)映射為單分網(wǎng)絡(luò),再采用單分網(wǎng)絡(luò)社團檢測算法進行社團劃分.但這個映射過程會丟失原始網(wǎng)絡(luò)信息,致使社團劃分結(jié)果不理想[5].二是直接在二分網(wǎng)絡(luò)上實現(xiàn)社團劃分,如通過尋找二分網(wǎng)絡(luò)的最大模塊度[6]、標簽傳播[7]、節(jié)點間的親密度[8]、邊密度傳播[4]等方法實現(xiàn).為了保留二分網(wǎng)絡(luò)的原始信息并進一步提高社團檢測的模塊度,筆者擬設(shè)計一種融合奇異值分解的譜聚類(Singular Value Decomposition of Multiway Spectral,SVD-MS)算法,即將單分網(wǎng)絡(luò)社團檢測方法[9]擴展到二分網(wǎng)絡(luò),通過奇異值分解方法解決二分網(wǎng)絡(luò)鄰接矩陣的非對稱問題,再采用啟發(fā)式算法快速求解向量劃分問題,從而實現(xiàn)二分網(wǎng)絡(luò)的社團檢測.

1 相關(guān)工作

1.1 二分網(wǎng)絡(luò)

二分網(wǎng)絡(luò)由2種不同類型的節(jié)點組成,直接連邊只存在于不同類型的節(jié)點之間,同一類型的節(jié)點之間不存在直接連邊.用G=(U,V,E)表示一個二分網(wǎng)絡(luò),U和V為不同類型節(jié)點的集合,E為節(jié)點之間連邊的集合.在集合U(或集合V)內(nèi)沒有連邊,在集合E內(nèi),ui∈U,vj∈V.一個等效且更直觀的定義是給二分網(wǎng)絡(luò)的節(jié)點分配2種顏色中的一種,如深灰色或淺灰色,且相同顏色的節(jié)點之間沒有直接連邊.

用p表示深灰色節(jié)點的數(shù)量,q表示淺灰色節(jié)點的數(shù)量,n=p+q.在不失一般性的情況下,假設(shè)節(jié)點被索引,深灰色節(jié)點標記為1,2,…,p,淺灰色節(jié)點標記為p+1,p+2,…,n.那么,鄰接矩陣

1.2 Barber的二分網(wǎng)絡(luò)模塊度

模塊度QB是衡量社團檢測質(zhì)量的標準.一個好的劃分(即大多數(shù)的邊位于社團內(nèi),很少的邊位于不同社團之間)會得到一個高的分數(shù),而一個糟糕的劃分會得到一個低的分數(shù).模塊度是在社團結(jié)構(gòu)不變的情況下,同一社團內(nèi)節(jié)點間實際連邊比例與隨機2點間連邊比例期望值的差值.在零模型中,節(jié)點i和j之間存在邊的概率為P,

那么模塊度矩陣是非對角形式的矩陣,即

(1)

其中:gi為節(jié)點i分配到的社團;hj為節(jié)點j分配到的社團;δij為Kronecker-delta函數(shù).

2 二分網(wǎng)絡(luò)的SVD-MS社團檢測算法

2.1 譜算法聚類

現(xiàn)在考慮將n個節(jié)點的網(wǎng)絡(luò)劃分為k個社團的問題.一個好的劃分應(yīng)具有高模塊度,現(xiàn)通過尋找最大的模塊度來實現(xiàn)好的劃分.注意到(1)式中的delta函數(shù)可以寫成

(2)

2.2 向量劃分

(3)

(4)

這樣,模塊度可改寫成

(5)

(6)

2.3 算法描述

基于向量劃分思想并結(jié)合二分網(wǎng)絡(luò)的拓撲結(jié)構(gòu),構(gòu)建以下SVD-MS算法:

圖1 描述向量分區(qū)啟發(fā)式操作的工作原理Fig. 1 Working Principle of Vector Partitioning Heuristic Operation

Step4更新群向量.

Step5從step 2開始重復(fù),直至群向量停止改變(或者達到最大迭代次數(shù)時停止).

3 實證研究

為了檢驗SVD-MS算法的有效性,在3個真實世界的網(wǎng)絡(luò)中進行算法評估,并與LPBRIM算法[7]、Asymlntimacy算法[10]、BiAttractor算法[11]、SVD-BRIM算法[12]、BRIM算法[6]、SCA算法[13]和BiNeTClus算法[14]作比較.

3.1 Southern Women網(wǎng)絡(luò)

圖2 Southern Women網(wǎng)絡(luò)在SVD-MS算法下的社團劃分Fig. 2 Community Detection of Southern Women Network Through SVD-MS Algorithm

Southern women數(shù)據(jù)集[15]是二分網(wǎng)絡(luò)社團檢測算法最常用的數(shù)據(jù)集之一.該網(wǎng)絡(luò)中有18名婦女和14個活動,用婦女是否參加過活動的關(guān)系構(gòu)建連邊,共有93條連邊.

SVD-MS算法將Southern women網(wǎng)絡(luò)分成了3個規(guī)模大小不一的社團.社團檢測結(jié)果的拓撲結(jié)構(gòu)如圖2所示.圖2中白色、淺灰色和深灰色表示社團,方形表示婦女,圓形表示活動.經(jīng)計算,SVD-MS,LPBRIM,Asymlntimacy,BiAttractor,SVD-BRIM,BRIM,SCA,BiNeTClus算法的模塊度分別為0.345,0.313,0.333,0.345,0.321,0.345,0.333,0.313.由此可知,SVD-MS算法的模塊度與BRIM和SVD-BRIM算法的相同,略高于其他5種算法,說明SVD-MS算法能較精準地識別Southern women網(wǎng)絡(luò)中的社團結(jié)構(gòu).

3.2 Disease-Gene網(wǎng)絡(luò)

圖3 Disease-Gene網(wǎng)絡(luò)在SVD-MS算法下的社團劃分Fig. 3 Community Detection of Disease-Gene Network Through SVD-MS Algorithm

Kwang-II等[16]通過探討致病基因與遺傳疾病的關(guān)系構(gòu)建了Disease-gene二分網(wǎng)絡(luò).該網(wǎng)絡(luò)中有19個遺傳疾病和19個致病基因,共有49條連邊.

SVD-MS算法將Disease-gene網(wǎng)絡(luò)分成了3個規(guī)模大小不一的社團.社團檢測結(jié)果的拓撲結(jié)構(gòu)如圖3所示.圖3中白色、淺灰色和深灰色表示社團,方形表示疾病,圓形表示致病基因.經(jīng)計算,SVD-MS,LPBRIM,Asymlntimacy,BiAttractor,SVD-BRIM,BRIM,SCA,BiNeTClus算法的模塊度分別為0.514,0.348,0.348,0.348,0.415,0.415,0.379,0.415.由此可知,SVD-MS算法的模塊度高于其他7種算法,說明SVD-MS算法能較精準地識別Disease-gene網(wǎng)絡(luò)中的社團結(jié)構(gòu).

3.3 American Revolution網(wǎng)絡(luò)

American revolution數(shù)據(jù)集[17]包含5個組織和136個成員的信息.成員與組織之間的關(guān)系構(gòu)建成二分網(wǎng)絡(luò),該網(wǎng)絡(luò)共有160條連邊.

SVD-MS算法將America revolution網(wǎng)絡(luò)分成了5個規(guī)模大小不一的社團(表1).表1中1～136為成員,137～141為組織.經(jīng)計算,SVD-MS,LPBRIM,Asymlntimacy,BiAttractor,SVD-BRIM,BRIM,SCA,BiNeTClus算法的模塊度分別為0.602,0.591,0.48,0.601,0.595,0.602,0.601,0.591.由此可知,SVD-MS算法的模塊度與BRIM算法的相同,比Asymlntimacy算法的高23.3%,略高于其他5種算法,說明SVD-MS算法能較精準地識別America revolution網(wǎng)絡(luò)中的社團結(jié)構(gòu).

表1 America Revolution網(wǎng)絡(luò)在SVD-MS算法下的社團劃分結(jié)果Table 1 Community Detection Results of the American Revolution Network Through SVD-MS Algorithm

4 結(jié)語

從保留二分網(wǎng)絡(luò)的原始信息和提高社團檢測的模塊度的角度出發(fā),設(shè)計了一種基于譜聚類的社團檢測算法(SVD-MS).該算法用線性代數(shù)原理作為社團檢測的基礎(chǔ),易于形式化分析.在真實世界的網(wǎng)絡(luò)中將SVD-MS與L-P,Asymlntimacy,BiAttractor,SVD-BRIM,BRIM,SCA,BiNeTClus等7種算法進行對比實驗,結(jié)果表明,在保留二分網(wǎng)絡(luò)原始信息的情況下,相比其他算法,SVD-MS算法更能有效地對二分網(wǎng)絡(luò)實現(xiàn)社團劃分.由于SVD-MS算法需要事先給定二分網(wǎng)絡(luò)社團的數(shù)量,然后通過尋求最大模塊度來找到社團劃分的最優(yōu)結(jié)果,而社團數(shù)量很難確定,目前只能進行多次重復(fù)實驗才能找到最優(yōu)結(jié)果,因此筆者下一步將著重探索確定社團數(shù)量的方法.