基于論文相似網(wǎng)絡拓撲結構的聚類方法比較

，

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

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

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

1 材料與方法

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

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

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

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

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

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

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

2 結果

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

圖3 社團劃分實際情況

圖4 隨機游走算法得出的網(wǎng)絡1的聚類結果

圖5 隨機游走算法得出的網(wǎng)絡2的聚類結果

圖6 標簽傳播算法得出的網(wǎng)絡1的聚類結果

圖7 標簽傳播算法得出的網(wǎng)絡2的聚類結果

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

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

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

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

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

采用標簽傳播算法對網(wǎng)絡1進行聚類分析，如圖6所示，準確率高達81.3%。它將27號主題與98號主題歸為一類，因此社團數(shù)目只有5。但對網(wǎng)絡2的聚類結果跟隨機游走算法一樣(圖7)，也是與實際一致。

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

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

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

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

3 討論

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

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

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

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

4 結語

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

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