科研主題演化中三種典型社區(qū)發(fā)現(xiàn)算法對比研究
——以植物甾醇信號為例①

薛 陜 董 誠 韓紅旗 張均勝 高 雄 王 力

(中國科學(xué)技術(shù)信息研究所 北京100038)

0 引言

科研主題演化是衡量科研主題隨時間推移表現(xiàn)出的動態(tài)性、發(fā)展性和差異性的研究?？蒲兄黝}演化一般包含兩方面含義:其一是科研主題內(nèi)容隨著時間推移而發(fā)生變化,其二是不同科研主題之間復(fù)雜的承繼關(guān)系。其中,主題識別是演化分析的基礎(chǔ)和關(guān)鍵因素。目前主題識別的主流方法可分為基于語言模型的方法[1-2]和基于網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)的方法[3-4]?；诰W(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)的主題識別方法由于速度快、社區(qū)劃分比較準(zhǔn)確,目前已經(jīng)成為科研主題識別的主要方法[5-7]。

社區(qū)(community) 是社會網(wǎng)絡(luò)中的常見現(xiàn)象,由一群高度聚集、聯(lián)系緊密的節(jié)點(diǎn)聚集組成,在各種知識網(wǎng)絡(luò)中普遍存在社區(qū)結(jié)構(gòu)[8-10]。社區(qū)結(jié)構(gòu)研究可以追溯到1977 年Zachary[11]對空手道俱樂部成員關(guān)系網(wǎng)絡(luò)的研究。Girvan 和Newman[12]在對社會網(wǎng)絡(luò)的研究中提出了著名的(Girvan-Newman)GN社區(qū)發(fā)現(xiàn)算法,隨后的研究發(fā)現(xiàn)在物理學(xué)家合作網(wǎng)絡(luò)中同樣存在社區(qū)現(xiàn)象[13]。Boyack 等人[14]在利用7121 種期刊數(shù)據(jù)集繪制科學(xué)景觀鳥瞰圖的研究中也發(fā)現(xiàn)了類似的社區(qū)結(jié)構(gòu)。Lambiotte 等人[15]發(fā)現(xiàn)存在于知識網(wǎng)絡(luò)層面的社區(qū),是一種劃分知識領(lǐng)域和學(xué)科前沿的新視角。

由于構(gòu)成網(wǎng)絡(luò)的數(shù)據(jù)集的不同,網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)往往存在不同特點(diǎn),不同社區(qū)算法對特定網(wǎng)絡(luò)社區(qū)識別效果存在差異[16]。社區(qū)發(fā)現(xiàn)算法對主題識別效果直接影響了主題演化結(jié)果和路徑的判斷。因此,有必要對當(dāng)前主要社區(qū)發(fā)現(xiàn)算法的效果進(jìn)行對比研究,了解其效果以及適用性能。本研究以植物甾醇信號相關(guān)文獻(xiàn)關(guān)鍵詞共現(xiàn)網(wǎng)絡(luò)為實(shí)例,選取3 種典型社區(qū)發(fā)現(xiàn)算法對其主題發(fā)現(xiàn)和演化追蹤效果進(jìn)行了對比,并結(jié)合專家知識對植物甾醇信號主題研究現(xiàn)狀和演化趨勢進(jìn)行了分析解釋。

1 相關(guān)研究

網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的聚類方法與計(jì)算機(jī)科學(xué)中的圖形分割(graph partition) 和社會學(xué)中的分級聚類(hierarchical clustering)[17-18]有著密切聯(lián)系。復(fù)雜網(wǎng)絡(luò)社區(qū)識別方法按照聚類算法的不同可以分為以下幾類:基于譜平均法的聚類算法、基于分裂的聚類算法、基于凝聚的聚類算法以及基于重疊社區(qū)的聚類算法。計(jì)算復(fù)雜度以及準(zhǔn)確性是分析復(fù)雜網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)面臨的主要問題。如表1 所示,譜平均法難以適用于社區(qū)結(jié)構(gòu)復(fù)雜的網(wǎng)絡(luò)結(jié)構(gòu),而以GN 算法[12]為代表的分裂算法由于運(yùn)算復(fù)雜不適用于大型網(wǎng)絡(luò),因此本文不再選用這兩種算法進(jìn)行研究。目前已有的研究發(fā)現(xiàn)基于凝聚的方法[19]和基于重疊社區(qū)[9]的方法在處理復(fù)雜網(wǎng)絡(luò)社區(qū)劃分中具有較好的效果[20]。因此本文選取基于凝聚的聚類算法中具有代表性的Newman MM 算法[13,19]、Blondel算法[21]以及基于重疊社區(qū)發(fā)現(xiàn)的Ball Overlapping算法[22]作為研究對象。以植物油菜素甾醇研究領(lǐng)域的關(guān)鍵詞共現(xiàn)網(wǎng)絡(luò)為例,對這幾種社區(qū)發(fā)現(xiàn)算法的社區(qū)劃分速度、準(zhǔn)確性以及在演化分析過程中的適用性進(jìn)行了對比,揭示了它們在主題演化研究中的優(yōu)點(diǎn)與不足。

表1 常用社區(qū)發(fā)現(xiàn)算法的分類與優(yōu)缺點(diǎn)對比

2 實(shí)驗(yàn)方法設(shè)計(jì)

2.1 實(shí)驗(yàn)數(shù)據(jù)

以2010 年為分界點(diǎn),2010 年之前每年關(guān)于植物甾醇信號的研究不到50 篇,2010 年之后每年文獻(xiàn)的數(shù)量迅速增長,到2017 年到達(dá)頂峰,有141 篇文獻(xiàn)。因此將文獻(xiàn)檢索時間限定為2010 -2017 年,以檢索式“Brassinosteroids”[MeSH Terms] or“Brassinosteroids”[AllFields] or“Brassinosteroid”[All Fields]從Pubmed 數(shù)據(jù)庫檢索,獲得關(guān)于植物油菜素甾醇研究文獻(xiàn)962 篇。

2.2 關(guān)鍵詞共現(xiàn)網(wǎng)絡(luò)的構(gòu)建

對收集到的962 篇文獻(xiàn)進(jìn)行處理,按年份為尺度對文獻(xiàn)進(jìn)行分割。以關(guān)鍵詞為節(jié)點(diǎn),關(guān)鍵詞的共現(xiàn)關(guān)系為邊,構(gòu)建了每年的關(guān)鍵詞共現(xiàn)網(wǎng)絡(luò),各關(guān)鍵詞網(wǎng)絡(luò)指標(biāo)見表2。

表2 2010 -2017 年植物甾醇激素領(lǐng)域關(guān)鍵詞共現(xiàn)網(wǎng)絡(luò)部分指標(biāo)

2.3 科研主題演化的計(jì)算和可視化展現(xiàn)

經(jīng)過調(diào)研,選擇文獻(xiàn)[25]提出的相似度計(jì)算公式作為不同時間窗口的主題相似度的測度。該公式基于節(jié)點(diǎn)重合度計(jì)算兩個社區(qū)的相似度,能夠較好地反映兩個主題之間的相似性。給定社區(qū)Mx和社區(qū)My,各自對應(yīng)的詞匯集合為Cx、Cy,它們的相似度按式(1)定義為

其中,W(v) 表示節(jié)點(diǎn)的頻次,min(x,y) 為x和y中較小的值。如果前后兩個連續(xù)時間段中的社區(qū)相似度超過設(shè)定的閾值,則認(rèn)為兩個社區(qū)存在演化關(guān)系。社區(qū)M(T+1)j的前驅(qū)定義見式(2)。

其中,δ是可調(diào)節(jié)的閾值,根據(jù)經(jīng)驗(yàn)取值為0.3。為了判斷社區(qū)的演化形式,本研究參考了文獻(xiàn)[9,26]所提出的方法,將網(wǎng)絡(luò)社區(qū)的演化過程定義為6 種形式,分別是產(chǎn)生、消亡、分裂、融合、擴(kuò)張和收縮。主題演化的可視化則采用可視化軟件NEViewer 以河流圖形式展現(xiàn)。

2.4 基于專家知識的社區(qū)發(fā)現(xiàn)算法效果的比較

由于在復(fù)雜網(wǎng)絡(luò)的社區(qū)分割中不存在有效的精確解法(該問題是一個NP 難題)[27-29],因此很難定義一個量化指標(biāo)并從準(zhǔn)確性的角度評價不同算法的優(yōu)劣。為了比較社區(qū)發(fā)現(xiàn)算法的聚類識別性能,以確定效果最好的主題識別算法,本研究邀請領(lǐng)域?qū)＜覍κ占奈墨I(xiàn)集進(jìn)行了主題標(biāo)引,結(jié)合專家標(biāo)引的結(jié)果對Newman MM 算法和Blondel 算法的社區(qū)劃分以及主題演化分析效果進(jìn)行了對比。

3 結(jié)果及分析

3.1 三種典型社區(qū)發(fā)現(xiàn)算法社區(qū)劃分效果的比較

目前基于復(fù)雜網(wǎng)絡(luò)理論的主題聚類算法有很多,經(jīng)過調(diào)研,選取其中使用較多、有代表性的3 種算法:Newman MM 算法、Ball Overlapping 算法和Blondel 算法,對文獻(xiàn)關(guān)鍵詞所組成的共詞網(wǎng)絡(luò)進(jìn)行了社區(qū)劃分,并對這3 種算法的社區(qū)劃分性能進(jìn)行了比較。從運(yùn)算速度上看,Blondel 算法最快,僅用21 s;Ball Overlapping 算法次之,用時139 s;Newman MM 算法最慢,用時977 s,約是Blondel 算法的46倍,Ball 算法的7 倍。社區(qū)具體內(nèi)容如表3 所示,在社區(qū)識別結(jié)果上,因?yàn)锽all Overlapping 算法是支持重疊社區(qū)識別的,因此產(chǎn)生了很多重復(fù)的社區(qū)關(guān)鍵詞。以識別到的10 個社區(qū)為例,其中有8 個社區(qū)的關(guān)鍵詞都是重復(fù)的,表明該算法對該數(shù)據(jù)集的支持性不好。Blondel 算法和Newman MM 算法在社區(qū)識別效果上比較接近,Blondel 算法發(fā)現(xiàn)了12 個社區(qū),Newman MM 算法發(fā)現(xiàn)了10 個社區(qū)。這2 種算法發(fā)現(xiàn)的社區(qū)的代表性關(guān)鍵詞也具有較好的解釋性,如Mutation(突變體)、Plants、Genetically modified(轉(zhuǎn)基因植物)、Signal Transduction(信號傳導(dǎo))等都是植物甾醇激素領(lǐng)域研究的熱點(diǎn)主題,而且基本沒有產(chǎn)生重復(fù)的關(guān)鍵詞。因此之后的研究中可著重針對這2 種算法作對比。

表3 3 種社區(qū)發(fā)現(xiàn)算法的社區(qū)內(nèi)容

續(xù)表3

3.2 科研主題演化的計(jì)算和可視化

由于2010 -2017 年間的文獻(xiàn)總共有926 篇,如果這些文獻(xiàn)都由專家進(jìn)行主題標(biāo)注的話,專家的工作量會很大。因此本文只選取了2010 -2014 年的文獻(xiàn)集為例。采用2.3 節(jié)所述方法,對這5 年的植物甾醇激素領(lǐng)域相關(guān)文獻(xiàn)的主題進(jìn)行了識別和演化追蹤,并通過可視化軟件NEViewer 將主題的演化結(jié)果進(jìn)行可視化展現(xiàn)。圖1 展示了采用Blondel 算法繪制的主題演化河流圖,圖2 展示了采用Newman MM 算法繪制的主題演化河流圖。

如圖1 和圖2 所示,在河流圖中將偵測到具有演化關(guān)系的主題用相同顏色的條帶表示,而條帶的粗細(xì)則代表組成該主題關(guān)鍵詞的多少。對比2 種算法繪制的河流圖可以發(fā)現(xiàn),通過Blondel 算法劃分的社區(qū)偵測到的主題演化狀態(tài)更為豐富,社區(qū)的6 種演化狀態(tài)(產(chǎn)生、消亡、分裂、融合、擴(kuò)張和收縮)都有發(fā)現(xiàn)。而基于Newman MM 算法劃分的社區(qū)演化狀態(tài)比較單一,沒有發(fā)現(xiàn)融合狀態(tài)的社區(qū),這與專家判斷的實(shí)際情況不符。

圖1 植物甾醇激素領(lǐng)域的主題演化河流圖(Blondel 算法)

圖2 植物甾醇激素領(lǐng)域的主題演化河流圖(Newman MM 算法)

3.3 基于專家知識的社區(qū)發(fā)現(xiàn)算法準(zhǔn)確性的比較

為了評價這2 種社區(qū)發(fā)現(xiàn)算法的演化分析結(jié)果的優(yōu)劣,邀請了中科院植物所的專家,利用專家的知識對Newman MM 算法和Blondel 算法的社區(qū)劃分效果進(jìn)行對比。以Animals 這個主題為實(shí)例說明專家的判斷結(jié)果。Animals 主題在2010 年的數(shù)據(jù)集中,Newman MM 算法和Blondel 算法都發(fā)現(xiàn)了此主題。不同的是,Blondel 算法在2011 年偵測到主題Animals 的后繼主題狀態(tài)為擴(kuò)張,而Newman MM 分區(qū)算法沒有偵測到主題Animals 的后繼主題。將Blondel算法偵測到的主題Animals的演化網(wǎng)絡(luò)從整體網(wǎng)絡(luò)中單獨(dú)提取出來,以河流圖形式進(jìn)行可視化展現(xiàn),結(jié)果見圖3。

如圖3 所示,2010 年組成Animals 主題的關(guān)鍵詞數(shù)量只有29 個。2011 年該主題發(fā)生擴(kuò)張,關(guān)鍵詞數(shù)量增加到31 個。2012 年該主題進(jìn)一步擴(kuò)張,關(guān)鍵詞增加到71 個,并且中心度最高的關(guān)鍵詞由Animals 演化為Humans。2013 年該主題發(fā)生分裂產(chǎn)生了2 個新生主題:Stereoisomerism(立體異構(gòu))和Acetylation(乙?；?。

圖3 主題Animals 的演化河流圖(Blondel 算法)

為了驗(yàn)證Blondel 算法獲得的Animals 主題演化路徑的準(zhǔn)確性,需要借助專家知識對2011 -2014年的文獻(xiàn)主題進(jìn)行標(biāo)注和分析,如果發(fā)現(xiàn)有Animals相關(guān)研究組成的主題則說明Blondel 算法較為準(zhǔn)確。如果沒有發(fā)現(xiàn)Animals 相關(guān)研究組成的主題,則說明Newman MM 算法較為準(zhǔn)確。因此中科院植物所的領(lǐng)域?qū)＜沂苎麑ξ墨I(xiàn)集進(jìn)行了主題標(biāo)注,標(biāo)注結(jié)果如表4 所示。

由表4 可知,從2010 年開始到2013 年,與動物有關(guān)的Brassinosteroids 研究文獻(xiàn)一直存在并呈上升趨勢,2010 年4 篇,2011 年6 篇,2012 年7 篇,2013年9 篇。主題內(nèi)容上可以分為Brassinosteroids 對動物細(xì)胞的毒理研究、植物甾醇與動物甾醇的功能比較、Brassinosteroids 的化學(xué)修飾。

表4 專家對Animals 主題文獻(xiàn)知的主題標(biāo)注結(jié)果

2010 年主題Animals 的研究內(nèi)容主要為Brassinosteroids 對動物細(xì)胞的毒理研究,其中有3 篇的研究對象為實(shí)驗(yàn)動物(小鼠、大鼠及牛),但也有1 篇關(guān)于人類胸腺腫瘤細(xì)胞的研究。2011 年研究該主題的文獻(xiàn)擴(kuò)大為6 篇,但研究還是以實(shí)驗(yàn)動物為主。到了2012 年研究該主題的文獻(xiàn)擴(kuò)大為7 篇,其中有6 篇是關(guān)于動物細(xì)胞的研究,當(dāng)年關(guān)于人類細(xì)胞的研究共有5 篇文獻(xiàn),而關(guān)于小鼠的研究下降為1 篇。2013 年該主題進(jìn)一步發(fā)生分裂產(chǎn)生了Brassinosteroids 的化學(xué)修飾這個研究主題,包括乙酰化修飾1篇,立體異構(gòu)體3 篇。這與Blondel 算法獲得的Animals 主題演化路徑基本是一致的。

由以上結(jié)果可知,從2010 年開始到2013 年,Animals 這個主題是存在的,并且其研究內(nèi)容發(fā)生了從以實(shí)驗(yàn)動物為主到以人類細(xì)胞研究為主的轉(zhuǎn)變。結(jié)合專家知識繪制了該主題的演化模式圖,證明Blondel 算法得到的Animals 主題演化路徑是比較準(zhǔn)確的。如圖4 所示。

圖4 專家解讀繪制的Animals 主題演化圖

4 結(jié)論

本研究對Blondel 算法、Newman MM 算法和Ball Overlapping 3 種典型的社區(qū)發(fā)現(xiàn)算法的社區(qū)劃分效果和準(zhǔn)確性進(jìn)行了對比研究。在植物甾醇領(lǐng)域的實(shí)驗(yàn)研究總結(jié)如下。

(1)3 種社區(qū)發(fā)現(xiàn)算法的主題識別效果比較表明:在運(yùn)算速度上Blondel 算法最快,Ball Overlapping 算法次之,Newman MM 算法最慢。而在社區(qū)識別效果上Blondel 算法和Newman MM 算法比較接近,識別到的社區(qū)其代表性關(guān)鍵詞也具有較好的解釋性。

(2)基于河流圖的植物甾醇激素領(lǐng)域的主題演化可視化結(jié)果表明:采用同樣的社區(qū)演化追蹤方法,通過Blondel 算法劃分的社區(qū)偵測到的主題演化狀態(tài)更為豐富,而基于Newman MM 算法劃分的社區(qū)演化狀態(tài)比較單一。

(3)以Animals 主題作為實(shí)例,比較Newman 和Blondel 2 個算法發(fā)現(xiàn)主題的準(zhǔn)確性可以看到:此主題在2010 年的數(shù)據(jù)集中Newman MM 算法和Blondel 算法都有發(fā)現(xiàn)。不同的是,Blondel 算法在2011年偵測到Animals 后繼主題狀態(tài)為擴(kuò)張,并且到2013 年為止都有后續(xù)主題的發(fā)現(xiàn);而Newman MM分區(qū)算法則沒有偵測到Animals 的后繼主題。以上為算法生成的演化路徑。

(4)該領(lǐng)域?qū)＜医忉尩难莼窂斤@示,從2010年開始到2013 年,Animals 這個主題是一直存在的。并且研究對象經(jīng)歷了以實(shí)驗(yàn)動物為主到以人類細(xì)胞為主的轉(zhuǎn)變。這證明Blondel 算法得到的主題Animals 演化路徑是比較準(zhǔn)確的。

根據(jù)植物甾醇領(lǐng)域文獻(xiàn)的實(shí)驗(yàn)結(jié)果可以得知,3種算法中Blondel 算法獲得的主題和演化追蹤最為準(zhǔn)確,它不僅可以很好地實(shí)現(xiàn)關(guān)鍵詞共現(xiàn)網(wǎng)絡(luò)的社區(qū)劃分,而且能更好地發(fā)現(xiàn)科研主題的演化。

基于復(fù)雜網(wǎng)絡(luò)理論的社區(qū)發(fā)現(xiàn)和演化算法為研究科研主題演化追蹤提供了一種新的思路。該方法得到的主題演化數(shù)據(jù)具有較好的解釋性,但同時存在一些不足之處。其一是這種方法比較依賴于關(guān)鍵詞數(shù)據(jù),一般只適用于結(jié)構(gòu)性比較強(qiáng)的文獻(xiàn)數(shù)據(jù);其二是有些文獻(xiàn)關(guān)鍵詞的選擇存在隨意性[30],不一定能很好地反映文獻(xiàn)的內(nèi)在特征,忽略了對文獻(xiàn)內(nèi)容的分析因而具有一定局限性。未來的工作可以嘗試在該方法中融入基于文獻(xiàn)內(nèi)部特征提取的方法,以實(shí)現(xiàn)對非結(jié)構(gòu)化數(shù)據(jù)主題演化的研究。