劉晨晨,許 英

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

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

1 相關(guān)工作

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

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

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

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

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

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

(1)

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

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

2.1 譜算法聚類

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

(2)

2.2 向量劃分

(3)

(4)

這樣,模塊度可改寫成

(5)

(6)

2.3 算法描述

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

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

Step4更新群向量.

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

3 實(shí)證研究

為了檢驗(yàn)SVD-MS算法的有效性,在3個(gè)真實(shí)世界的網(wǎng)絡(luò)中進(jìn)行算法評(píng)估,并與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算法下的社團(tuán)劃分Fig. 2 Community Detection of Southern Women Network Through SVD-MS Algorithm

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

SVD-MS算法將Southern women網(wǎng)絡(luò)分成了3個(gè)規(guī)模大小不一的社團(tuán).社團(tuán)檢測(cè)結(jié)果的拓?fù)浣Y(jié)構(gòu)如圖2所示.圖2中白色、淺灰色和深灰色表示社團(tuán),方形表示婦女,圓形表示活動(dòng).經(jīng)計(jì)算,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算法能較精準(zhǔn)地識(shí)別Southern women網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu).

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

圖3 Disease-Gene網(wǎng)絡(luò)在SVD-MS算法下的社團(tuán)劃分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個(gè)遺傳疾病和19個(gè)致病基因,共有49條連邊.

SVD-MS算法將Disease-gene網(wǎng)絡(luò)分成了3個(gè)規(guī)模大小不一的社團(tuán).社團(tuán)檢測(cè)結(jié)果的拓?fù)浣Y(jié)構(gòu)如圖3所示.圖3中白色、淺灰色和深灰色表示社團(tuán),方形表示疾病,圓形表示致病基因.經(jīng)計(jì)算,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算法能較精準(zhǔn)地識(shí)別Disease-gene網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu).

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

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

SVD-MS算法將America revolution網(wǎng)絡(luò)分成了5個(gè)規(guī)模大小不一的社團(tuán)(表1).表1中1～136為成員,137～141為組織.經(jīng)計(jì)算,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算法能較精準(zhǔn)地識(shí)別America revolution網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu).

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

4 結(jié)語

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