劉晨晨,許 英
(**財(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)檢測在挖掘二分網(wǎng)絡(luò)的結(jié)構(gòu)、預(yù)測對象的行為特征、提取網(wǎng)絡(luò)的有用信息等方面有廣泛應(yīng)用[4].目前,二分網(wǎng)絡(luò)社團(tuán)檢測方法主要有2種:一是將二分網(wǎng)絡(luò)映射為單分網(wǎng)絡(luò),再采用單分網(wǎng)絡(luò)社團(tuán)檢測算法進(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)檢測的模塊度,筆者擬設(shè)計(jì)一種融合奇異值分解的譜聚類(Singular Value Decomposition of Multiway Spectral,SVD-MS)算法,即將單分網(wǎng)絡(luò)社團(tuán)檢測方法[9]擴(kuò)展到二分網(wǎng)絡(luò),通過奇異值分解方法解決二分網(wǎng)絡(luò)鄰接矩陣的非對稱問題,再采用啟發(fā)式算法快速求解向量劃分問題,從而實(shí)現(xiàn)二分網(wǎng)絡(luò)的社團(tuá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)檢測質(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,
那么模塊度矩陣是非對角形式的矩陣,即
(1)
其中:gi為節(jié)點(diǎn)i分配到的社團(tuán);hj為節(jié)點(diǎn)j分配到的社團(tuán);δij為Kronecker-delta函數(shù).
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í)停止).
為了檢驗(yàn)SVD-MS算法的有效性,在3個(gè)真實(shí)世界的網(wǎng)絡(luò)中進(jìn)行算法評估,并與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)檢測算法最常用的數(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)檢測結(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)檢測結(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
從保留二分網(wǎng)絡(luò)的原始信息和提高社團(tuán)檢測的模塊度的角度出發(fā),設(shè)計(jì)了一種基于譜聚類的社團(tuán)檢測算法(SVD-MS).該算法用線性代數(shù)原理作為社團(tuán)檢測的基礎(chǔ),易于形式化分析.在真實(shí)世界的網(wǎng)絡(luò)中將SVD-MS與L-P,Asymlntimacy,BiAttractor,SVD-BRIM,BRIM,SCA,BiNeTClus等7種算法進(jìn)行對比實(shí)驗(yàn),結(jié)果表明,在保留二分網(wǎng)絡(luò)原始信息的情況下,相比其他算法,SVD-MS算法更能有效地對二分網(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ù)量的方法.
猜你喜歡 深灰色社團(tuán)向量 世上的雨星星·散文詩(2023年20期)2023-08-13繽紛社團(tuán)閱讀(中年級）(2022年9期)2022-10-08向量的分解新高考·高一數(shù)學(xué)(2022年3期)2022-04-28德國制造睿士(2021年10期)2021-10-22聚焦“向量與三角”創(chuàng)新題中學(xué)生數(shù)理化(高中版.高考數(shù)學(xué))(2021年1期)2021-03-19哪個(gè)圖形面積大發(fā)明與創(chuàng)新·小學(xué)生(2019年12期)2019-12-05哪個(gè)圖形面積大發(fā)明與創(chuàng)新(2019年47期)2019-11-21最棒的健美操社團(tuán)軍事文摘(2017年16期)2018-01-19K-BOT拼插社團(tuán)中學(xué)生(2016年13期)2016-12-01向量垂直在解析幾何中的應(yīng)用高中生學(xué)習(xí)·高三版(2016年9期)2016-05-14