基于論文相似網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的聚類方法比較

，

近幾年，在探索復(fù)雜網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的過程中，研究者除發(fā)現(xiàn)小世界與無標(biāo)度特性外，還發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)還存在一個(gè)基本屬性：社團(tuán)結(jié)構(gòu)(community structure)[1]。復(fù)雜網(wǎng)絡(luò)是由若干個(gè)社團(tuán)組成，社團(tuán)內(nèi)部節(jié)點(diǎn)的連接非常緊密，社團(tuán)之間節(jié)點(diǎn)的連接相對(duì)比較稀疏。結(jié)構(gòu)決定功能，研究網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)有助于分析復(fù)雜網(wǎng)絡(luò)的功能、探索復(fù)雜網(wǎng)絡(luò)的隱藏規(guī)律以及預(yù)測復(fù)雜網(wǎng)絡(luò)的發(fā)展趨勢。

為了能夠精確界定網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)，必須選擇一種優(yōu)秀的聚類方法?，F(xiàn)有的復(fù)雜網(wǎng)絡(luò)聚類方法主要分為兩大類，一類是基于圖論的算法，如Kernighan-Lin法[2]、譜平分法[3]、隨機(jī)游走法(Walktrap algorithm)[4]和標(biāo)簽傳播法(Label propagation algorithm)[5]；另一類是層次聚類方法，層次聚類本身又分為凝聚與分裂算法，其中凝聚算法包括Newman快速算法[6]和最大模塊度算法(BGll algorithm)[7]等，分裂算法中最為經(jīng)典的是Girvan和Newman提出的邊介數(shù)算法(Girvan-Newman algorithm)[8]。此外，近幾年又有許多從其他不同角度提出的劃分網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)的聚類算法，如基于電阻網(wǎng)絡(luò)性質(zhì)的算法、基于信息論的算法等。

在文獻(xiàn)領(lǐng)域，以語義相似性算法構(gòu)造出的論文相似網(wǎng)絡(luò)能夠直接反映文獻(xiàn)內(nèi)容的相似程度[9]。因而以此網(wǎng)絡(luò)為基礎(chǔ)，分析該網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)，可以清晰地描述出學(xué)科結(jié)構(gòu)的動(dòng)態(tài)變化與專業(yè)主題的研究熱點(diǎn)，并為文獻(xiàn)影響力的評(píng)價(jià)提供新的視角。為了找到最適合論文相似網(wǎng)絡(luò)的聚類算法，本文以語義相似算法構(gòu)造論文相似網(wǎng)絡(luò)，并針對(duì)性地選擇了4種代表性聚類方法(基于圖論的隨機(jī)游走算法和標(biāo)簽傳播算法，層次聚類中的最大模塊度法和邊介數(shù)法)對(duì)構(gòu)建出的網(wǎng)絡(luò)進(jìn)行聚類分析，并結(jié)合樣本數(shù)據(jù)的金標(biāo)準(zhǔn)和網(wǎng)絡(luò)社團(tuán)劃分評(píng)價(jià)指標(biāo)D函數(shù)[10]比較4種算法的準(zhǔn)確性和穩(wěn)定性。

1 材料與方法

在OHSUMED試驗(yàn)數(shù)據(jù)集中選擇6個(gè)查詢提問(queries)作為研究主題，收集與其明確相關(guān)(definitely related)的109篇文獻(xiàn)作為樣本數(shù)據(jù)。其中6號(hào)主題19篇，27號(hào)主題36篇，32號(hào)主題14篇，42號(hào)主題13篇，84號(hào)主題22篇，98號(hào)主題5篇。

為了直接反映文獻(xiàn)內(nèi)容的相關(guān)性，采用語義相似性算法[11]構(gòu)造論文相似網(wǎng)絡(luò)，即用文獻(xiàn)的主題詞代表論文，通過計(jì)算主題詞間的相似性得出文獻(xiàn)間的相似程度。利用本地PubMed檢索系統(tǒng)(http://www.bdpubmed.com/)中基于語義相似性的PANS(Paper Network on Similarity)算法直接生成論文相似矩陣(表1)，矩陣中的元素代表相應(yīng)兩篇文獻(xiàn)間內(nèi)容上的相似性。為使聚類結(jié)果更準(zhǔn)確，選擇0.08作為相似度閾值，移除相似度小于等于0.08的邊，得到簡化后的相似矩陣(表2)。在R語言的igraph程序包中，以上述兩個(gè)相似矩陣為鄰接矩陣構(gòu)造論文網(wǎng)絡(luò)，得到原始的論文網(wǎng)絡(luò)(簡稱網(wǎng)絡(luò)1，圖1)和簡化的論文網(wǎng)絡(luò)(簡稱網(wǎng)絡(luò)2，圖2)，并進(jìn)行可視化處理。

網(wǎng)絡(luò)1和網(wǎng)絡(luò)2都是無向加權(quán)圖，每個(gè)節(jié)點(diǎn)代表1篇文獻(xiàn)，邊的權(quán)重代表文獻(xiàn)間的相似度值。其中網(wǎng)絡(luò)1共109個(gè)節(jié)點(diǎn)，5 886條邊；網(wǎng)絡(luò)2含109個(gè)節(jié)點(diǎn)，1621條連接(圖中標(biāo)簽代表金標(biāo)準(zhǔn)的主題號(hào))。利用igraph程序包的復(fù)雜網(wǎng)絡(luò)處理算法功能，分別采用4種聚類算法對(duì)網(wǎng)絡(luò)1和網(wǎng)絡(luò)2進(jìn)行聚類分析，探索論文相似網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)，最后結(jié)合金標(biāo)準(zhǔn)的主題分類和網(wǎng)絡(luò)社團(tuán)劃分評(píng)價(jià)指標(biāo)D函數(shù)[10]比較4種算法的準(zhǔn)確性和穩(wěn)定性。

表1 論文相似矩陣(部分)

表2 簡化后的論文相似矩陣(部分)

圖1 原始的論文相似網(wǎng)絡(luò)

圖2 簡化后的論文相似網(wǎng)絡(luò)

2 結(jié)果

按照金標(biāo)準(zhǔn)的主題分類，論文相似網(wǎng)絡(luò)擁有6個(gè)社團(tuán)(圖3)，其中社團(tuán)1(第98號(hào)主題)5個(gè)節(jié)點(diǎn)，社團(tuán)2(第27號(hào)主題)36個(gè)節(jié)點(diǎn)，社團(tuán)3(第6號(hào)主題)19個(gè)節(jié)點(diǎn)，社團(tuán)4(第84號(hào)主題)22個(gè)節(jié)點(diǎn)，社團(tuán)5(第32號(hào)主題)14個(gè)節(jié)點(diǎn)，社團(tuán)6(第42號(hào)主題)13個(gè)節(jié)點(diǎn)。采用4種算法對(duì)網(wǎng)絡(luò)1和網(wǎng)絡(luò)2聚類的結(jié)果如圖4-圖11所示。圖中節(jié)點(diǎn)標(biāo)簽數(shù)字代表金標(biāo)準(zhǔn)的主題號(hào)，標(biāo)簽顏色相同的節(jié)點(diǎn)屬于同一個(gè)社團(tuán)，社團(tuán)內(nèi)連線為黑色，社團(tuán)間連線為紅色。

圖3 社團(tuán)劃分實(shí)際情況

圖4 隨機(jī)游走算法得出的網(wǎng)絡(luò)1的聚類結(jié)果

圖5 隨機(jī)游走算法得出的網(wǎng)絡(luò)2的聚類結(jié)果

圖6 標(biāo)簽傳播算法得出的網(wǎng)絡(luò)1的聚類結(jié)果

圖7 標(biāo)簽傳播算法得出的網(wǎng)絡(luò)2的聚類結(jié)果

圖9 最大模塊度算法得出的網(wǎng)絡(luò)2的聚類結(jié)果

圖10 邊介數(shù)算法得出的網(wǎng)絡(luò)1的聚類結(jié)果

圖11 邊介數(shù)算法得出的網(wǎng)絡(luò)2的聚類結(jié)果

4種算法得出的聚類結(jié)果的具體數(shù)據(jù)如表3和表4所示。

采用隨機(jī)游走算法分析論文相似網(wǎng)絡(luò)，并對(duì)網(wǎng)絡(luò)進(jìn)行聚類分析，如圖4所示，準(zhǔn)確率高達(dá)96.3%，社團(tuán)數(shù)為6，但第6號(hào)主題的一個(gè)節(jié)點(diǎn)與98號(hào)主題的5個(gè)節(jié)點(diǎn)被錯(cuò)誤歸為一類。簡化剪枝后，準(zhǔn)確率為100%，聚類結(jié)果(圖5)與實(shí)際社團(tuán)劃分情況完全相同。

采用標(biāo)簽傳播算法對(duì)網(wǎng)絡(luò)1進(jìn)行聚類分析，如圖6所示，準(zhǔn)確率高達(dá)81.3%。它將27號(hào)主題與98號(hào)主題歸為一類，因此社團(tuán)數(shù)目只有5。但對(duì)網(wǎng)絡(luò)2的聚類結(jié)果跟隨機(jī)游走算法一樣(圖7)，也是與實(shí)際一致。

采用最大模塊度算法對(duì)論文相似網(wǎng)絡(luò)聚類分析時(shí)，網(wǎng)絡(luò)處理前后的結(jié)果是一致的(圖8和圖9)，二者都是將42號(hào)主題與98號(hào)主題聚為一類，從而得到5個(gè)社團(tuán)，但在處理兩個(gè)網(wǎng)絡(luò)時(shí)得到的Q值都是最大的。

邊介數(shù)算法對(duì)于原始網(wǎng)絡(luò)的聚類效果較差，如圖10所示，模塊度Q僅為0.045，57個(gè)社團(tuán)中僅1個(gè)社團(tuán)的節(jié)點(diǎn)數(shù)超過1，其余社團(tuán)均只含1個(gè)節(jié)點(diǎn)。網(wǎng)絡(luò)剪枝后，GN法得到6個(gè)社團(tuán)(圖11)，準(zhǔn)確率高于90%，僅98號(hào)主題有2個(gè)節(jié)點(diǎn)被錯(cuò)誤歸為42號(hào)主題。

表3 原始論文相似網(wǎng)絡(luò)(網(wǎng)絡(luò)1)的聚類結(jié)果

表4 簡化論文相似網(wǎng)絡(luò)(網(wǎng)絡(luò)2)的聚類結(jié)果

3 討論

由于不同主題文獻(xiàn)之間的相似性大都較低(全部<0.1)，導(dǎo)致同一主題內(nèi)的任意兩篇文獻(xiàn)與其他主題文獻(xiàn)的相似性差異很小。這符合隨機(jī)游走算法的前提，即若兩個(gè)節(jié)點(diǎn)同屬于一個(gè)社團(tuán)，那么分別從兩個(gè)頂點(diǎn)跳躍到整個(gè)網(wǎng)絡(luò)的其他節(jié)點(diǎn)的概率相近：如果頂點(diǎn)i和頂點(diǎn)j屬于同一社團(tuán)，則對(duì)于任一頂點(diǎn)k有Ptik≈Ptjk。

標(biāo)簽傳播算法的兩次聚類結(jié)果差距較大，說明其穩(wěn)定性較差。這是由于它的更新順序是隨機(jī)的[12]、鄰接節(jié)點(diǎn)標(biāo)簽數(shù)量相同時(shí)選擇標(biāo)簽也是隨機(jī)的，算法的魯棒性遭到嚴(yán)重破壞，社區(qū)結(jié)構(gòu)的穩(wěn)定性也就受到嚴(yán)重?fù)p害。

最大模塊度算法則更為穩(wěn)定，具有以下優(yōu)點(diǎn)：計(jì)算速度快，可用于大型網(wǎng)絡(luò); 整個(gè)過程自下而上，不會(huì)遺漏小規(guī)模的社團(tuán)結(jié)構(gòu)；適用于大規(guī)模的加權(quán)網(wǎng)絡(luò)[13]。

邊介數(shù)算法的前提是連接不同社團(tuán)間的邊的介數(shù)值較大，而連接社團(tuán)內(nèi)部邊的介數(shù)值則較小。但由于原始論文相似網(wǎng)絡(luò)中任意兩點(diǎn)之間都存在連接，無法滿足此前提，因此聚類結(jié)果無意義。

4 結(jié)語

在構(gòu)建文獻(xiàn)相似網(wǎng)絡(luò)的基礎(chǔ)上，通過比較4種聚類算法的聚類精度和聚類穩(wěn)定性，我們發(fā)現(xiàn)，隨機(jī)游走算法是一種優(yōu)秀的論文相似網(wǎng)絡(luò)聚類算法，準(zhǔn)確性高、穩(wěn)定性好；標(biāo)簽傳播算法的準(zhǔn)確性次之，但穩(wěn)定性不高；最大模塊度算法穩(wěn)定性好，但聚類精度有待提高；邊介數(shù)算法對(duì)相似網(wǎng)絡(luò)的預(yù)處理要求很高，聚類結(jié)果不穩(wěn)定。另外，我們還發(fā)現(xiàn)，選擇閾值處理相似網(wǎng)絡(luò)后聚類效果顯著提高，說明選擇不同的相似度閾值會(huì)對(duì)聚類結(jié)果產(chǎn)生影響，可見復(fù)雜網(wǎng)絡(luò)的預(yù)處理也是一個(gè)影響其聚類效果的重要因素。

本研究為今后選擇更為準(zhǔn)確和穩(wěn)定的論文相似網(wǎng)絡(luò)聚類算法提供了依據(jù)。在今后的研究中，應(yīng)選擇隨機(jī)游走算法對(duì)文獻(xiàn)相似性網(wǎng)絡(luò)進(jìn)行聚類分析，并且可以嘗試通過閾值的選取來提高文獻(xiàn)相似網(wǎng)絡(luò)的聚類精度。文本聚類分析技術(shù)的進(jìn)一步改進(jìn)，一是有助于揭示學(xué)科結(jié)構(gòu)及其動(dòng)態(tài)變化，在精確計(jì)算論文相似性基礎(chǔ)上，形成準(zhǔn)確的網(wǎng)絡(luò)并精確地聚類分析，隨時(shí)反映不同學(xué)科專業(yè)主題當(dāng)前研究的熱點(diǎn)和結(jié)構(gòu)；二是有助于成簇檢索相關(guān)文獻(xiàn)，可以將基于隨機(jī)游走算法鑲嵌在文獻(xiàn)檢索系統(tǒng)中，將用戶檢索到的文獻(xiàn)集合中相似論文按照類別提供給檢索用戶，提高信息咨詢服務(wù)的準(zhǔn)確度和針對(duì)性。