范純龍，王潔瓊，范東皖，丁國(guó)輝

(沈陽(yáng)航空航天大學(xué) a.遼寧省大規(guī)模分布式系統(tǒng)實(shí)驗(yàn)室，b.計(jì)算機(jī)學(xué)院，沈陽(yáng) 110136)

近幾年，復(fù)雜網(wǎng)絡(luò)中的節(jié)點(diǎn)預(yù)測(cè)問(wèn)題受到學(xué)者們的關(guān)注，其研究類型大致可以分為兩類，一類是對(duì)網(wǎng)絡(luò)中源頭節(jié)點(diǎn)的定位或追溯，另一類是對(duì)網(wǎng)絡(luò)中隱藏節(jié)點(diǎn)的發(fā)現(xiàn)。例如，在傳染病網(wǎng)絡(luò)中追蹤和定位攜帶病毒的原始載體節(jié)點(diǎn)(源頭節(jié)點(diǎn))，或者在黑暗組織網(wǎng)絡(luò)中發(fā)現(xiàn)和定位隱藏起來(lái)的領(lǐng)導(dǎo)人節(jié)點(diǎn)(隱藏節(jié)點(diǎn))等。然而這兩類節(jié)點(diǎn)預(yù)測(cè)都存在一定的局限性，其一是網(wǎng)絡(luò)應(yīng)用場(chǎng)景的局限，都只在具有某些特征的網(wǎng)絡(luò)中進(jìn)行研究，正如例子中的傳染病網(wǎng)絡(luò)和黑暗組織網(wǎng)絡(luò)；其二是現(xiàn)有節(jié)點(diǎn)預(yù)測(cè)研究大多只考慮節(jié)點(diǎn)間相似性，網(wǎng)絡(luò)的結(jié)構(gòu)以及網(wǎng)絡(luò)傳播代價(jià)度量等，從而忽略了節(jié)點(diǎn)間關(guān)系除了相似性之外同時(shí)存在著互斥性，相似性用來(lái)描述節(jié)點(diǎn)間相互吸引的程度，而新提出的節(jié)點(diǎn)間互斥性則是描述節(jié)點(diǎn)之間互相排斥的程度，可以更全面地描述節(jié)點(diǎn)之間的相互影響關(guān)系，該互斥性概念的具體理論及公式定義將在后面給出詳細(xì)的說(shuō)明；其三是現(xiàn)有節(jié)點(diǎn)預(yù)測(cè)研究都是在單頂點(diǎn)網(wǎng)絡(luò)中進(jìn)行，沒(méi)有涉及關(guān)于二分網(wǎng)絡(luò)中的節(jié)點(diǎn)預(yù)測(cè)研究，特別是對(duì)于未來(lái)網(wǎng)絡(luò)中可能出現(xiàn)的新生節(jié)點(diǎn)的預(yù)測(cè)研究更是罕見(jiàn)。因此，針對(duì)目前的節(jié)點(diǎn)預(yù)測(cè)領(lǐng)域，有必要研究在二分網(wǎng)絡(luò)中的新生節(jié)點(diǎn)的預(yù)測(cè)問(wèn)題，幫助擴(kuò)展節(jié)點(diǎn)預(yù)測(cè)研究的應(yīng)用范圍，為各種二分網(wǎng)絡(luò)節(jié)點(diǎn)預(yù)測(cè)提供更廣泛的研究思路。

以網(wǎng)絡(luò)中節(jié)點(diǎn)類型的數(shù)量為劃分依據(jù)，復(fù)雜網(wǎng)絡(luò)可以被分類為單頂點(diǎn)網(wǎng)絡(luò)和二分網(wǎng)絡(luò)等形式。二分網(wǎng)絡(luò)由兩種類型的節(jié)點(diǎn)以及這兩種類型節(jié)點(diǎn)之間的連邊組成，同種類型的節(jié)點(diǎn)之間不存在連邊。在現(xiàn)實(shí)世界中，有很多網(wǎng)絡(luò)都表現(xiàn)出自然的二分結(jié)構(gòu)，自然界和社會(huì)中的一系列合作網(wǎng)絡(luò)，都可以表現(xiàn)成由合作主體和合作事務(wù)而構(gòu)成的二分網(wǎng)絡(luò)，比如作者-論文合作網(wǎng)[1-2]、演員-事件合作網(wǎng)[3]、miRNA與疾病關(guān)系網(wǎng)絡(luò)[4]、觀眾與歌曲網(wǎng)絡(luò)[5]以及在P2P系統(tǒng)中計(jì)算機(jī)終端數(shù)據(jù)網(wǎng)絡(luò)[6]等。二分網(wǎng)絡(luò)具有普遍性，已經(jīng)成為復(fù)雜網(wǎng)絡(luò)研究的重要對(duì)象。近年來(lái)，二分網(wǎng)絡(luò)的研究方法被應(yīng)用到了眾多領(lǐng)域中，學(xué)者們也開(kāi)始關(guān)注網(wǎng)絡(luò)的二分性，并嘗試在二分網(wǎng)絡(luò)中應(yīng)用鏈路預(yù)測(cè)解決一些問(wèn)題，比如個(gè)性化推薦[7]，合著關(guān)系的研究[8]等，從而揭示出來(lái)了一些更深層的網(wǎng)絡(luò)特性。追根溯源，本文研究的節(jié)點(diǎn)預(yù)測(cè)與鏈路預(yù)測(cè)是極為相似的問(wèn)題，鏈路預(yù)測(cè)是預(yù)測(cè)網(wǎng)絡(luò)中節(jié)點(diǎn)間存在鏈接的可能性，而節(jié)點(diǎn)預(yù)測(cè)問(wèn)題雖然是預(yù)測(cè)網(wǎng)絡(luò)中未來(lái)有可能產(chǎn)生的節(jié)點(diǎn)，也可以看作是對(duì)網(wǎng)絡(luò)中現(xiàn)有節(jié)點(diǎn)與未來(lái)可能產(chǎn)生的節(jié)點(diǎn)之間存在鏈接的可能性預(yù)測(cè)。從這個(gè)方面來(lái)看，節(jié)點(diǎn)預(yù)測(cè)問(wèn)題在某種程度上也可以轉(zhuǎn)化為鏈路預(yù)測(cè)問(wèn)題。而且，利用二分網(wǎng)絡(luò)有利于研究主體和客體之間的結(jié)構(gòu)特征以及演化的過(guò)程，可以幫助我們探索知識(shí)創(chuàng)造活動(dòng)的規(guī)律，這也是本文嘗試在二分網(wǎng)絡(luò)上研究節(jié)點(diǎn)預(yù)測(cè)問(wèn)題的原因之一。

本文在二分網(wǎng)絡(luò)上對(duì)網(wǎng)絡(luò)中較活躍一側(cè)未來(lái)可能會(huì)出現(xiàn)的節(jié)點(diǎn)進(jìn)行預(yù)測(cè)，歸根結(jié)底，這里對(duì)未來(lái)可能生成節(jié)點(diǎn)的預(yù)測(cè)也可以認(rèn)為是預(yù)測(cè)網(wǎng)絡(luò)中存在的一種潛在節(jié)點(diǎn)，與現(xiàn)有的關(guān)于源頭節(jié)點(diǎn)和隱藏節(jié)點(diǎn)的預(yù)測(cè)工作異曲同工。不同之處在于，本文為現(xiàn)有的節(jié)點(diǎn)預(yù)測(cè)算法提供了新的研究思路。首先，我們發(fā)現(xiàn)網(wǎng)絡(luò)中的節(jié)點(diǎn)之間除了可以利用相似性指標(biāo)來(lái)表示兩節(jié)點(diǎn)間的親密關(guān)系，還有一種影響關(guān)系存在于節(jié)點(diǎn)之間，那就是后文將提出的節(jié)點(diǎn)間互相排斥的關(guān)系，我們稱之為互斥性。在相似性存在的基礎(chǔ)上，互斥性的提出幫助我們從另一個(gè)方向描述實(shí)際存在于網(wǎng)絡(luò)中的節(jié)點(diǎn)間關(guān)系，而且明確對(duì)該節(jié)點(diǎn)間性質(zhì)進(jìn)行了定義，該定義的提出不僅能夠幫助我們更全面地了解網(wǎng)絡(luò)中節(jié)點(diǎn)的特性，也為學(xué)者們以后更深入全面地研究復(fù)雜網(wǎng)絡(luò)提供了全新的靈感和方向。

本文以論文-關(guān)鍵詞二分網(wǎng)絡(luò)為研究對(duì)象，主要研究網(wǎng)絡(luò)中未來(lái)可能出現(xiàn)的新生論文節(jié)點(diǎn)預(yù)測(cè)問(wèn)題，不僅擴(kuò)展了現(xiàn)有節(jié)點(diǎn)預(yù)測(cè)的應(yīng)用場(chǎng)景，也為各種二分網(wǎng)絡(luò)上進(jìn)行節(jié)點(diǎn)預(yù)測(cè)研究提供了新思路。本文研究也可以稱為新生知識(shí)點(diǎn)的發(fā)現(xiàn)，我們可以利用現(xiàn)有的知識(shí)網(wǎng)絡(luò)結(jié)構(gòu)等信息預(yù)測(cè)將來(lái)可能會(huì)出現(xiàn)的新生知識(shí)點(diǎn)或者新的研究方向，不僅能夠?yàn)閷W(xué)者們的研究提供參考和引導(dǎo)，更有可能推動(dòng)領(lǐng)域研究的發(fā)展，對(duì)學(xué)術(shù)界具有重大的意義。

1 相關(guān)研究

1.1 鏈路預(yù)測(cè)簡(jiǎn)介

網(wǎng)絡(luò)可以自然地描述各種自然和社會(huì)結(jié)構(gòu)。在這樣的網(wǎng)絡(luò)中，頂點(diǎn)表示實(shí)體，鏈接表示實(shí)體之間的通信或關(guān)系。鏈路預(yù)測(cè)是網(wǎng)絡(luò)分析研究中的一個(gè)重要領(lǐng)域。網(wǎng)絡(luò)中的鏈路預(yù)測(cè)是指通過(guò)已知的網(wǎng)絡(luò)節(jié)點(diǎn)以及網(wǎng)絡(luò)的結(jié)構(gòu)等信息，預(yù)測(cè)網(wǎng)絡(luò)中尚未產(chǎn)生連邊的兩個(gè)節(jié)點(diǎn)之間產(chǎn)生鏈接的可能性。這種預(yù)測(cè)既包含了對(duì)未知鏈接的預(yù)測(cè)，也包含了對(duì)未來(lái)鏈接的預(yù)測(cè)[9]。本文研究的節(jié)點(diǎn)預(yù)測(cè)與鏈路預(yù)測(cè)有著緊密的聯(lián)系，鏈路預(yù)測(cè)是對(duì)網(wǎng)絡(luò)中可能存在的邊的預(yù)測(cè)，而節(jié)點(diǎn)預(yù)測(cè)主要是通過(guò)已知的網(wǎng)絡(luò)信息來(lái)預(yù)測(cè)未來(lái)將會(huì)出現(xiàn)的新生節(jié)點(diǎn)，而新生節(jié)點(diǎn)必然會(huì)與現(xiàn)有網(wǎng)絡(luò)中某些節(jié)點(diǎn)存在連邊的關(guān)系。因此，節(jié)點(diǎn)預(yù)測(cè)在某種程度上也可以轉(zhuǎn)化為鏈路預(yù)測(cè)問(wèn)題，即預(yù)測(cè)新生節(jié)點(diǎn)與現(xiàn)有節(jié)點(diǎn)之間存在鏈接的可能性。

1.2 節(jié)點(diǎn)預(yù)測(cè)相關(guān)研究

目前，學(xué)者們對(duì)于節(jié)點(diǎn)預(yù)測(cè)的相關(guān)研究主要分為兩類：一類是對(duì)網(wǎng)絡(luò)中“源頭節(jié)點(diǎn)”的預(yù)測(cè)，另一類是對(duì)“隱藏節(jié)點(diǎn)”的預(yù)測(cè)。由于許多真實(shí)網(wǎng)絡(luò)擁有巨大的規(guī)模，例如因特網(wǎng)或人類社交圖，觀察網(wǎng)絡(luò)中所有節(jié)點(diǎn)的狀態(tài)通常是不可行的。也就是說(shuō)，利用觀察者收集的稀疏的測(cè)量值來(lái)估計(jì)源節(jié)點(diǎn)的位置是根本不可能的。PINTO等人[10]在受限觀察者的異步模型下研究“源頭節(jié)點(diǎn)”的定位問(wèn)題，提出了一種對(duì)任意樹(shù)進(jìn)行最優(yōu)定位的策略，實(shí)現(xiàn)了正確定位的最大概率，并提出了一個(gè)估計(jì)器。LOUNI等人[11]提出了基于上述源頭節(jié)點(diǎn)定位工作的兩階段算法，該算法是一種最大似然源定位算法，特別適用于大型社交網(wǎng)絡(luò)，只需比其他單級(jí)算法少3%的傳感器節(jié)點(diǎn)，便可以獲得相同的檢測(cè)精度。ZHANG等人[12]同樣比較了上述源頭節(jié)點(diǎn)定位工作中提出的源頭定位估計(jì)器的采樣策略，認(rèn)為識(shí)別高效觀察者對(duì)于高精度定位源節(jié)點(diǎn)至關(guān)重要，而且策略的定位精度隨著網(wǎng)絡(luò)連通性的增加而降低。SHEN等人[13]同樣研究了異步模型下“源頭節(jié)點(diǎn)”的定位問(wèn)題，從數(shù)據(jù)中發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)和動(dòng)態(tài)的能力是理解和控制復(fù)雜系統(tǒng)中集體動(dòng)態(tài)的基礎(chǔ)。

對(duì)當(dāng)前已有的節(jié)點(diǎn)預(yù)測(cè)研究進(jìn)行分析，我們發(fā)現(xiàn)現(xiàn)有的源頭節(jié)點(diǎn)和隱藏節(jié)點(diǎn)的定位問(wèn)題，歸根結(jié)底都是對(duì)網(wǎng)絡(luò)中不能或者很難直接觀察到，但是實(shí)際存在的或者潛在的節(jié)點(diǎn)進(jìn)行預(yù)測(cè)。本文預(yù)測(cè)將來(lái)網(wǎng)絡(luò)中可能會(huì)出現(xiàn)的節(jié)點(diǎn)，在某種程度上也可以理解為預(yù)測(cè)網(wǎng)絡(luò)中的潛在節(jié)點(diǎn)。然而，現(xiàn)有節(jié)點(diǎn)預(yù)測(cè)算法存在一些不足之處，比如，現(xiàn)有算法大多關(guān)注節(jié)點(diǎn)間的相似性以及網(wǎng)絡(luò)的傳播代價(jià)度量，從而忽略了節(jié)點(diǎn)間存在彼此排斥的現(xiàn)象，不利于更全面地描述節(jié)點(diǎn)間的關(guān)系。

另外，這兩類節(jié)點(diǎn)預(yù)測(cè)研究的應(yīng)用場(chǎng)景只適用于具有某些結(jié)構(gòu)特征的網(wǎng)絡(luò)。源頭節(jié)點(diǎn)的預(yù)測(cè)[14-16]主要應(yīng)用在流行病網(wǎng)絡(luò)中，用來(lái)追蹤和定位病毒的原始載體；隱藏節(jié)點(diǎn)的預(yù)測(cè)主要應(yīng)用在恐怖組織網(wǎng)絡(luò)中，預(yù)測(cè)領(lǐng)導(dǎo)者的存在和位置，或者也可以預(yù)測(cè)流行病網(wǎng)絡(luò)中的病毒源。更重要的是，已有的關(guān)于節(jié)點(diǎn)預(yù)測(cè)工作絕大部分都在單頂點(diǎn)網(wǎng)絡(luò)中進(jìn)行，而本文主要是在采集的論文-關(guān)鍵詞二分網(wǎng)絡(luò)數(shù)據(jù)集上預(yù)測(cè)未來(lái)可能發(fā)表的論文，不僅擴(kuò)展了節(jié)點(diǎn)預(yù)測(cè)的應(yīng)用場(chǎng)景，也為各種二分網(wǎng)絡(luò)上進(jìn)行節(jié)點(diǎn)預(yù)測(cè)提供了更廣泛的研究思路。

1.3 二分網(wǎng)絡(luò)相關(guān)介紹

二分網(wǎng)絡(luò)由兩類節(jié)點(diǎn)以及兩類節(jié)點(diǎn)之間的連邊組成，同類節(jié)點(diǎn)之間不存在連邊。二分網(wǎng)絡(luò)可以用一個(gè)無(wú)向簡(jiǎn)單二部圖G=(U,V,E)來(lái)表示，這里，U和V分別是G的兩部分頂點(diǎn)的集合，E為G中邊的集合。對(duì)于任意邊(u,v)∈E，必有u∈U且v∈V，即只有不同部分之間的頂點(diǎn)才能鏈接，而在同一部分的頂點(diǎn)之間不存在鏈接[17-18]。如圖1(a)所示是一個(gè)二分網(wǎng)絡(luò)，在該網(wǎng)絡(luò)中，小寫字母頂點(diǎn)為同一類型的頂點(diǎn)，大寫字母頂點(diǎn)為另一類型的頂點(diǎn)，同類型的頂點(diǎn)之間沒(méi)有相連的邊。

圖1 二分網(wǎng)絡(luò)加權(quán)投影

在實(shí)際生活中，我們?nèi)菀装l(fā)現(xiàn)許多呈現(xiàn)出二分性的網(wǎng)絡(luò)具有“動(dòng)態(tài)”的特征，網(wǎng)絡(luò)結(jié)構(gòu)隨著時(shí)間的變化并不是一成不變的。例如，隨著時(shí)間推移合著網(wǎng)絡(luò)中出現(xiàn)新的合著關(guān)系，即合著網(wǎng)絡(luò)中的節(jié)點(diǎn)之間產(chǎn)生新的連邊。二分網(wǎng)絡(luò)的“動(dòng)態(tài)性”不僅僅體現(xiàn)在邊的變化上，隨時(shí)間推移其節(jié)點(diǎn)的數(shù)量也會(huì)變化，如合著網(wǎng)絡(luò)中新科學(xué)家的出現(xiàn)，并且普遍存在單側(cè)較“穩(wěn)定”的特點(diǎn)，另一側(cè)隨時(shí)間變化則較明顯。

二分網(wǎng)絡(luò)的研究通常有兩種思路：第一種是直接基于原始的二分網(wǎng)絡(luò)進(jìn)行分析；第二種是把二分網(wǎng)絡(luò)投影到單頂點(diǎn)網(wǎng)絡(luò)，然后再進(jìn)行網(wǎng)絡(luò)分析。其中，投影方式可以分為無(wú)權(quán)投影和加權(quán)投影兩類[19]。最簡(jiǎn)單的投影方法涉及將二分網(wǎng)絡(luò)投影到未加權(quán)的網(wǎng)絡(luò)上，而不考慮網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)或與相對(duì)集合元素共享鏈接的頻率。如圖1(b)和1(c)分別為圖1(a)所示二分網(wǎng)絡(luò)在兩種不同類型節(jié)點(diǎn)所在側(cè)的無(wú)權(quán)投影網(wǎng)絡(luò)。本文采用最簡(jiǎn)單的一種加權(quán)投影方式，意味著邊緣直接按共同關(guān)聯(lián)的重復(fù)次數(shù)加權(quán)，也就是將權(quán)重定義為兩個(gè)同類節(jié)點(diǎn)共同鏈接另一類節(jié)點(diǎn)的個(gè)數(shù)。目前，在二分網(wǎng)絡(luò)上進(jìn)行的預(yù)測(cè)算法研究[20-22]都集中在鏈路預(yù)測(cè)，即預(yù)測(cè)新的“合作”關(guān)系，新邊的產(chǎn)生。本文嘗試在二分網(wǎng)絡(luò)中研究節(jié)點(diǎn)預(yù)測(cè)的問(wèn)題，假設(shè)較穩(wěn)定一側(cè)的節(jié)點(diǎn)個(gè)數(shù)在一定時(shí)間范圍內(nèi)是不變的，然后根據(jù)二分網(wǎng)絡(luò)的現(xiàn)有信息來(lái)預(yù)測(cè)未來(lái)“非穩(wěn)定”一側(cè)會(huì)出現(xiàn)的節(jié)點(diǎn)，在“非穩(wěn)定”一側(cè)的二分網(wǎng)絡(luò)投影上進(jìn)行節(jié)點(diǎn)的預(yù)測(cè)研究。

2 二分網(wǎng)絡(luò)節(jié)點(diǎn)預(yù)測(cè)算法

2.1 基于加權(quán)網(wǎng)絡(luò)的最大值隨機(jī)游走算法

在本文關(guān)鍵詞節(jié)點(diǎn)一側(cè)的加權(quán)投影網(wǎng)絡(luò)上，我們讓信息的每一次傳播根據(jù)每個(gè)節(jié)點(diǎn)與相鄰節(jié)點(diǎn)連邊的權(quán)值比例進(jìn)行分配?；诠?jié)點(diǎn)信息在二分網(wǎng)絡(luò)加權(quán)投影中以隨機(jī)游走方式傳播，存在著如下基于局部隨機(jī)游走的鏈路預(yù)測(cè)框架。在二分網(wǎng)絡(luò)中，A表示二分網(wǎng)絡(luò)加權(quán)投影的鄰接矩陣，存在節(jié)點(diǎn)i和j有連邊且權(quán)重為w，則元素aij=w，若節(jié)點(diǎn)i、j無(wú)連邊，則aij=0。假設(shè)目標(biāo)節(jié)點(diǎn)i的初始信息量為1，其余節(jié)點(diǎn)信息量為0，每次迭代信息都以隨機(jī)游走的方式傳播，則t+1次迭代后某一節(jié)點(diǎn)擁有的信息量為：

(1)

其中，N表示網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)量，kj表示節(jié)點(diǎn)j的度數(shù)。我們將兩個(gè)節(jié)點(diǎn)i和j分別作為源節(jié)點(diǎn)，令其初始信息資源量都為1，在經(jīng)過(guò)t步擴(kuò)散之后，將兩個(gè)節(jié)點(diǎn)間傳播的信息資源量，即兩個(gè)節(jié)點(diǎn)從對(duì)方得到的信息資源量之和作為兩個(gè)節(jié)點(diǎn)之間的相似性，也就是說(shuō)，節(jié)點(diǎn)i和j的相似度由節(jié)點(diǎn)間基于局部隨機(jī)游走的雙向信息傳播過(guò)程疊加得到?；诰植侩S機(jī)游走的相似性指標(biāo)LRW可表示為：

(2)

本文對(duì)在雙向傳播過(guò)程中所傳播的信息量進(jìn)行取最大值計(jì)算，利用其最大值來(lái)“統(tǒng)一化”被傳播的信息量，這種方法能夠降低由于取平均值導(dǎo)致的節(jié)點(diǎn)間相似度的偏移，可以在在保證避免偏移的前提下得到其相似強(qiáng)度。因此，基于加權(quán)網(wǎng)絡(luò)的最大值隨機(jī)游走指標(biāo)MLRW(maximum local random walk)可表示如下：

(3)

為方便理解，基于一個(gè)簡(jiǎn)單的例子對(duì)MLRW指標(biāo)進(jìn)行較詳細(xì)的計(jì)算和說(shuō)明。圖2是分別以節(jié)點(diǎn)A和節(jié)點(diǎn)E為源節(jié)點(diǎn)的兩步加權(quán)的局部隨機(jī)游走過(guò)程，A和E分別為源節(jié)點(diǎn)，源節(jié)點(diǎn)起始信息量為1，其它節(jié)點(diǎn)起始信息量為0。當(dāng)節(jié)點(diǎn)A為源節(jié)點(diǎn)時(shí)，節(jié)點(diǎn)E得到的信息量為SA→E=11/36；當(dāng)節(jié)點(diǎn)E為源節(jié)點(diǎn)時(shí)，節(jié)點(diǎn)A得到的信息量為：SE→A=11/60。其中，SA→E表示從節(jié)點(diǎn)A開(kāi)始經(jīng)過(guò)兩步隨機(jī)游走后傳播到節(jié)點(diǎn)E的信息量，SE→A表示從節(jié)點(diǎn)E開(kāi)始經(jīng)過(guò)兩步隨機(jī)游走后傳播到節(jié)點(diǎn)A的信息量。

圖2 加權(quán)投影網(wǎng)絡(luò)的兩步局部隨機(jī)游走信息傳播過(guò)程

2.2 互斥性關(guān)系的發(fā)現(xiàn)

我們?cè)谘芯康倪^(guò)程中發(fā)現(xiàn)網(wǎng)絡(luò)的節(jié)點(diǎn)間存在著一種互斥關(guān)系。在這里，我們首先需要回顧一下存在于節(jié)點(diǎn)間的另外一個(gè)性質(zhì)，也就是關(guān)于節(jié)點(diǎn)間緊密關(guān)系相似性的描述。按照傳統(tǒng)鏈路預(yù)測(cè)的研究，在利用節(jié)點(diǎn)間的相似性來(lái)進(jìn)行鏈路預(yù)測(cè)時(shí)有一個(gè)重要的前提假設(shè)，若兩個(gè)節(jié)點(diǎn)的相似性或者相近性越大，那么這兩節(jié)點(diǎn)之間存在連接的可能性也就越大。描述網(wǎng)絡(luò)節(jié)點(diǎn)間相似性的方法有很多，其中最常用且有效的方法便是利用節(jié)點(diǎn)間的屬性。這里我們可以舉一個(gè)簡(jiǎn)單易于理解的例子：假若存在兩個(gè)商店，他們的店名、商品、信譽(yù)、評(píng)價(jià)以及所在的地域等都相同，那么可以判定這兩個(gè)商店很相似。另一類是結(jié)構(gòu)相似性，完全根據(jù)網(wǎng)絡(luò)的結(jié)構(gòu)信息來(lái)判斷節(jié)點(diǎn)間的相似性。例如，對(duì)有共同鄰居的相似性指標(biāo)來(lái)說(shuō)，兩個(gè)節(jié)點(diǎn)間的相同鄰居越多則越有可能存在公共邊。根據(jù)上面兩種相似性指標(biāo)的方法，我們可以發(fā)現(xiàn)它們都是從節(jié)點(diǎn)間所擁有的共同點(diǎn)為出發(fā)點(diǎn)來(lái)定義相似性，前者是依靠屬性間的共同點(diǎn)，后者是依靠結(jié)構(gòu)的共同點(diǎn)。

與節(jié)點(diǎn)相似性的著眼點(diǎn)不同，本文從另一個(gè)角度來(lái)考慮節(jié)點(diǎn)之間的關(guān)系，主要觀察節(jié)點(diǎn)之間存在的差異。我們發(fā)現(xiàn)了節(jié)點(diǎn)間的互斥關(guān)系是客觀存在的，既然在不同方面擁有共同點(diǎn)的節(jié)點(diǎn)間存在著相似性，代表著節(jié)點(diǎn)間的親密程度，那么，當(dāng)然同樣可以認(rèn)為擁有明顯特征差異的節(jié)點(diǎn)之間存在著互斥性，并且代表著節(jié)點(diǎn)之間的排斥程度。本文提出需要考慮節(jié)點(diǎn)間的互斥關(guān)系，用于描述關(guān)鍵詞間彼此排斥的現(xiàn)象。例如，在論文-關(guān)鍵詞二分網(wǎng)絡(luò)中，關(guān)鍵詞節(jié)點(diǎn)K1和K2出現(xiàn)的頻率都很高，但是從未同時(shí)出現(xiàn)在同一篇論文中，這時(shí)可以認(rèn)為關(guān)鍵詞K1和K2之間的互斥性很強(qiáng)；相應(yīng)地，在用戶-商品網(wǎng)絡(luò)中，若商品A和B不僅出現(xiàn)頻繁，而且總是同時(shí)被購(gòu)買，那么可以說(shuō)商品A和B之間存在著很微弱的互斥性。

在兩節(jié)點(diǎn)最多出現(xiàn)次數(shù)中，一部分為同時(shí)出現(xiàn)的次數(shù)，另一部分是非同時(shí)出現(xiàn)次數(shù)。本文用兩節(jié)點(diǎn)未同時(shí)出現(xiàn)次數(shù)占最多出現(xiàn)次數(shù)的比率來(lái)初步表示節(jié)點(diǎn)間的互斥強(qiáng)度。實(shí)際上，僅用這個(gè)比率來(lái)表示互斥性是不全面的，若所研究的二分網(wǎng)絡(luò)是稀疏的，在兩節(jié)點(diǎn)間共同出現(xiàn)次數(shù)極小的情況下會(huì)導(dǎo)致互斥性接近甚至等于1，顯然這是不合理的。因此，考慮引入指數(shù)e進(jìn)行調(diào)節(jié)，從而避免出現(xiàn)互斥性過(guò)大的情況。另外，互斥強(qiáng)度除了此比率之外，還需要考慮兩節(jié)點(diǎn)最多出現(xiàn)次數(shù)在所有節(jié)點(diǎn)最多出現(xiàn)次數(shù)中的分布情況，這一點(diǎn)將在互斥性公式中有所體現(xiàn)。下面給出節(jié)點(diǎn)間互斥關(guān)系(Mutual Exclusion，簡(jiǎn)稱為ME)的定義：

(4)

根據(jù)公式(4)，我們不難發(fā)現(xiàn)e指數(shù)的引入導(dǎo)致實(shí)際實(shí)驗(yàn)的數(shù)據(jù)變化過(guò)于平緩，從而可能會(huì)導(dǎo)致實(shí)驗(yàn)數(shù)據(jù)不滿足實(shí)際互斥關(guān)系的表現(xiàn)強(qiáng)度。在這種情況下，我們考慮引入調(diào)節(jié)系數(shù)λ來(lái)平衡這種不足，下面給出調(diào)整之后的公式：

ME=λ×ME′

(5)

其中λ∈(0,1)，用于調(diào)節(jié)由于引入的e指數(shù)導(dǎo)致的互斥關(guān)系過(guò)于平緩的問(wèn)題，這樣就可以彌補(bǔ)公式(4)的不足，從而使實(shí)驗(yàn)數(shù)據(jù)更加符合實(shí)際情況。

2.3 引入互斥關(guān)系的節(jié)點(diǎn)預(yù)測(cè)算法

由于本文實(shí)驗(yàn)采用論文-關(guān)鍵詞二分網(wǎng)絡(luò)數(shù)據(jù)集對(duì)未來(lái)有可能產(chǎn)生的論文進(jìn)行預(yù)測(cè)，我們將以該二分網(wǎng)絡(luò)為例來(lái)描述節(jié)點(diǎn)預(yù)測(cè)算法，下面給出利用節(jié)點(diǎn)間互斥性和相似性進(jìn)行節(jié)點(diǎn)預(yù)測(cè)的實(shí)現(xiàn)過(guò)程。

(1)根據(jù)采集到的論文-關(guān)鍵詞二分網(wǎng)絡(luò)，在關(guān)鍵詞節(jié)點(diǎn)一側(cè)進(jìn)行投影，得到只含關(guān)鍵詞節(jié)點(diǎn)的二分網(wǎng)絡(luò)加權(quán)投影，令節(jié)點(diǎn)以隨機(jī)游走的方式進(jìn)行信息傳播，利用基于局部隨機(jī)游走的相似性指標(biāo)得到任意兩個(gè)關(guān)鍵詞的相似性矩陣；

(2)在關(guān)鍵詞的加權(quán)投影網(wǎng)絡(luò)中結(jié)合原二分網(wǎng)絡(luò)及其加權(quán)投影網(wǎng)絡(luò)所反映的信息。例如，某兩個(gè)關(guān)鍵詞在所有論文中的最多出現(xiàn)次數(shù)及其共同出現(xiàn)在同一篇論文的次數(shù)，通過(guò)我們前面給出的節(jié)點(diǎn)間互斥關(guān)系定義計(jì)算得兩個(gè)關(guān)鍵詞節(jié)點(diǎn)之間的互斥關(guān)系矩陣；

(3)在步驟(1)和步驟(2)中得到的相似性和互斥性矩陣中選出滿足相似度大于互斥性的二元關(guān)鍵詞組合(由于我們的算法取得的相似程度選取的是最大值，所以這里在進(jìn)行比較時(shí)取互斥程度的一半進(jìn)行比較)去除其中大量共同出現(xiàn)次數(shù)和最多出現(xiàn)次數(shù)同時(shí)為1而導(dǎo)致互斥性等于0的關(guān)鍵詞之后，認(rèn)為余下滿足條件的二元關(guān)鍵詞組合存在十分緊密的關(guān)系，未來(lái)有很大可能會(huì)同時(shí)出現(xiàn)在一篇論文中；

(4)步驟(3)得到的二元關(guān)鍵詞組合(Ki,Kj)中的兩個(gè)關(guān)鍵詞節(jié)點(diǎn)編號(hào)Ki和Kj分別在互斥性矩陣和相似性矩陣存在其對(duì)應(yīng)行，而且分別代表了與其它關(guān)鍵詞間的互斥性和相似性。因此，我們根據(jù)對(duì)應(yīng)行取幾何平均值可以得到二元關(guān)鍵詞組合(Ki,Kj)與其它關(guān)鍵詞Kx(x

一篇論文常見(jiàn)的關(guān)鍵詞在4個(gè)到5個(gè)，去除非核心及作者自己定義的方法名詞后，通過(guò)(3)中計(jì)算的三組親密度關(guān)系進(jìn)行匹配，得到運(yùn)用3個(gè)關(guān)鍵詞可以概括一篇論文內(nèi)容的主要關(guān)鍵詞。所以，本文認(rèn)為最終獲得的關(guān)系緊密的3元關(guān)鍵詞組可以在某種程度上代表未來(lái)將會(huì)產(chǎn)生的論文，進(jìn)而實(shí)現(xiàn)預(yù)測(cè)新節(jié)點(diǎn)產(chǎn)生的目的。

引入互斥關(guān)系的節(jié)點(diǎn)預(yù)測(cè)算法MENP(node prediction with mutual exclusion)框架描述如下。

輸入：G=(U,V,E):論文-關(guān)鍵詞二部圖；

輸出：關(guān)鍵詞互斥性矩陣En×n,關(guān)鍵詞相似性矩陣Sn×n，二元關(guān)鍵詞組集合K2，三元關(guān)鍵詞組集合K3。

Begin

(1)/*構(gòu)造投影圖Gu=(U,Eu)*/

Eu=?；

Forevery nodeK1inUdo

Forevery nodevinN(K1)do

Forevery nodeK2inN(v)do

Eu=Eu∪{(K1,K2)};

Endfor

Endfor

Endfor

(2)/*計(jì)算得到關(guān)鍵詞加權(quán)投影矩陣Qm×n*/

Forevery edge(K1,K2) inEudo

Calculate the weight of edge(K1,K2);

ReturnQm×n;

Endfor

(3)/*根據(jù)(2)得到的加權(quán)投影矩陣Qm×n，計(jì)算得到關(guān)鍵詞的相似性矩陣Sn×n和互斥性矩陣En×n*/

Forevery node pairK1,K2inQm×ndo

Calculate thesimilarity according to formula(1) and formula(3);

Calculate themutual exclusion according to formula(4)and formula(5);

ReturnSn×n，En×n;

Endfor

(4)/*選出滿足條件的二元關(guān)鍵詞組集合K2*/

Forevery node pairK1,K2do

IFSK1,K2>EK1,K2/2

Put node pairK1,K2inK2；

ReturnK2；

Endfor

(5)/*選出滿足條件的三元關(guān)鍵詞組集合K3*/

Forevery node pairK1,K2inK2do

Take the corresponding row of node pairK1,K2inSn×nasSK1andSK2respectively;

Take the corresponding row of node pairK1,K2in En×nas EK1and EK2respectively;

IFSK1,K2,Kx>EK1,K2,K3/2

Put node pairK1,K2,KxinK3；

ReturnK3；

Endfor

3 實(shí)驗(yàn)結(jié)果

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

本實(shí)驗(yàn)的數(shù)據(jù)集來(lái)源于知網(wǎng)(CNKI)檢索的期刊《軟件學(xué)報(bào)》，該期刊主要發(fā)表反映計(jì)算機(jī)科學(xué)和計(jì)算機(jī)軟件新理論、新方法和技術(shù)以及有關(guān)學(xué)科發(fā)展趨勢(shì)的文獻(xiàn)。實(shí)驗(yàn)數(shù)據(jù)集完全基于真實(shí)的數(shù)據(jù)采集和處理過(guò)程構(gòu)建，中間經(jīng)過(guò)系列的分詞、編號(hào)以及同義詞去重等處理，最終構(gòu)成了本文的數(shù)據(jù)集。實(shí)驗(yàn)數(shù)據(jù)集具體的采集和處理過(guò)程如下。

(1)按照年份批量導(dǎo)出知網(wǎng)上2013-2017年《軟件學(xué)報(bào)》上所有論文的基本信息(不包括投稿指南、專刊介紹和專題前言等非學(xué)術(shù)研究性質(zhì)的論文)，包括論文題目、摘要、作者、關(guān)鍵詞以及發(fā)表時(shí)間等；

(2)由于批量導(dǎo)出功能的限制，導(dǎo)出論文的基本信息條目過(guò)多。因此，利用分詞等相關(guān)技術(shù)提取試驗(yàn)所需要的論文題目以及關(guān)鍵詞；

(3)分別編號(hào)論文題目和關(guān)鍵詞，并對(duì)關(guān)鍵詞進(jìn)行去重和同義詞處理，構(gòu)建論文-關(guān)鍵詞二分網(wǎng)絡(luò)。

下面給出去重和同義詞處理之前的關(guān)鍵詞數(shù)， 表1是實(shí)驗(yàn)采集的數(shù)據(jù)的一些主要統(tǒng)計(jì)量，其中P代表論文數(shù)，K代表對(duì)應(yīng)關(guān)鍵詞數(shù)。

表1 數(shù)據(jù)的主要統(tǒng)計(jì)量

3.2 訓(xùn)練集和測(cè)試集劃分

本實(shí)驗(yàn)的二分網(wǎng)絡(luò)構(gòu)建于2013-2016年的論文和關(guān)鍵詞，網(wǎng)絡(luò)兩側(cè)節(jié)點(diǎn)由814篇論文和3 774個(gè)關(guān)鍵詞組成，其中關(guān)鍵詞進(jìn)行處理后實(shí)際有2 681個(gè)。

測(cè)試集由2017年的208篇論文和993個(gè)關(guān)鍵詞組成，關(guān)鍵詞處理后實(shí)際有861個(gè)。本文節(jié)點(diǎn)預(yù)測(cè)實(shí)驗(yàn)的前提是在二分網(wǎng)絡(luò)投影一側(cè)節(jié)點(diǎn)個(gè)數(shù)基本穩(wěn)定不變的假設(shè)下進(jìn)行，因此測(cè)試集需要進(jìn)行以下處理。

(1)對(duì)在訓(xùn)練集中出現(xiàn)過(guò)的關(guān)鍵詞仍然按照訓(xùn)練集中的序號(hào)進(jìn)行編號(hào)；

(2)將新出現(xiàn)的關(guān)鍵詞從測(cè)試集中去除，同時(shí)為了便于獲取節(jié)點(diǎn)預(yù)測(cè)的實(shí)驗(yàn)效果，我們將處理后的測(cè)試集數(shù)據(jù)按照論文進(jìn)行排序，共得到70篇論文，這樣實(shí)驗(yàn)得到關(guān)鍵詞組的集合后，直接觀察關(guān)鍵詞組集合在測(cè)試集論文中的關(guān)鍵詞匹配情況即可。

3.3 評(píng)價(jià)指標(biāo)

在信息檢索等領(lǐng)域(如搜索引擎)，自然語(yǔ)言處理和檢測(cè)分類中常常會(huì)用到一些指標(biāo)來(lái)評(píng)估實(shí)驗(yàn)方法的有效性以及實(shí)驗(yàn)結(jié)果的質(zhì)量。其中精確率(Precision)和召回率(Recall)是該領(lǐng)域常見(jiàn)的評(píng)價(jià)指標(biāo)。本文在論文-關(guān)鍵詞二分網(wǎng)絡(luò)上進(jìn)行節(jié)點(diǎn)預(yù)測(cè)研究，我們用實(shí)驗(yàn)所得聯(lián)系緊密的關(guān)鍵詞組合去測(cè)試集中匹配擁有相應(yīng)關(guān)鍵詞的論文，達(dá)到預(yù)測(cè)將來(lái)可能發(fā)表的論文的目的。我們?cè)跍y(cè)試集中將關(guān)鍵詞按照論文進(jìn)行分組，以便于評(píng)估節(jié)點(diǎn)預(yù)測(cè)算法的性能。在本文中，由于預(yù)測(cè)節(jié)點(diǎn)算法的性能可以被視為信息檢索任務(wù)，因此這里Precision和Recall可以作為評(píng)估該算法性能的兩個(gè)指標(biāo)。

我們將通過(guò)算法預(yù)測(cè)到的關(guān)鍵詞節(jié)點(diǎn)組合進(jìn)行分類，對(duì)于正確匹配到測(cè)試集中某篇論文所對(duì)應(yīng)關(guān)鍵詞的節(jié)點(diǎn)組合，本文稱其為正樣本，而對(duì)于不能匹配或不存在于訓(xùn)練集和測(cè)試集中的關(guān)鍵詞節(jié)點(diǎn)組合，本文稱其為負(fù)樣本。本文進(jìn)行節(jié)點(diǎn)預(yù)測(cè)實(shí)驗(yàn)的目的就是盡可能將全部正樣本識(shí)別出來(lái)，并且盡量避免錯(cuò)誤地將負(fù)樣本判定成正樣本的情況。正樣本的預(yù)測(cè)情況分為兩類，一種是正樣本被預(yù)測(cè)為正類(True Positive，TP)，另一種是正樣本被判定為負(fù)類(False Negative，F(xiàn)N)；負(fù)樣本的預(yù)測(cè)情況也分為兩類，一種是負(fù)樣本被判定為正類(False Positive，F(xiàn)P)；另一種是負(fù)樣本被判定為負(fù)類(True Negative，TN)。

本文中，Precision指的是節(jié)點(diǎn)預(yù)測(cè)算法成功預(yù)測(cè)到的存在于測(cè)試集中的論文數(shù)目占算法實(shí)際預(yù)測(cè)到的論文數(shù)目的比例,如式(5)所示。

(5)

相應(yīng)地，本文中Recall指的是節(jié)點(diǎn)預(yù)測(cè)算法成功預(yù)測(cè)到的存在于測(cè)試集中的論文數(shù)目占測(cè)試集中包含的所有論文的數(shù)目的比例，如式(6)所示。

(6)

3.4 實(shí)驗(yàn)結(jié)果

算法LRW和算法MLRW是在僅利用對(duì)應(yīng)的相似性指標(biāo)情況下進(jìn)行節(jié)點(diǎn)預(yù)測(cè)，如表2給出了四種預(yù)測(cè)算法的相關(guān)實(shí)驗(yàn)數(shù)據(jù)。接下來(lái)，我們將簡(jiǎn)單說(shuō)明如何在本文的數(shù)據(jù)集上僅利用相似性指標(biāo)進(jìn)行節(jié)點(diǎn)預(yù)測(cè)，其過(guò)程具體描述如下。

(3)我們根據(jù)步驟(2)中得到的三元關(guān)鍵詞組合，觀察他們與測(cè)試集中論文所對(duì)應(yīng)關(guān)鍵詞的匹配程度。

而算法MENP_LRW和MENP_MLRW則是引入了互斥關(guān)系的二分網(wǎng)絡(luò)節(jié)點(diǎn)預(yù)測(cè)算法，利用相似性的同時(shí)結(jié)合了新提出的節(jié)點(diǎn)間互斥關(guān)系，其中相似性算法分別采用LRW和MLRW。表2中所展示的數(shù)值是算法取不同迭代次數(shù)后的最優(yōu)結(jié)果，數(shù)值最大的結(jié)果所在行用加粗表示。

表2 不同預(yù)測(cè)算法的預(yù)測(cè)效果

為了更直接地觀察上述四種算法在不同評(píng)價(jià)指標(biāo)下的實(shí)驗(yàn)效果對(duì)比情況，圖3(a)和圖3(b)分別給出四種不同算法Precision和Recall對(duì)比柱狀圖。

圖3 不同預(yù)測(cè)算法效果對(duì)比

因?yàn)殡S機(jī)游走步數(shù)的不同，算法的實(shí)際實(shí)驗(yàn)效果也會(huì)有所不同。所以，我們針對(duì)本文提出的引入互斥關(guān)系的節(jié)點(diǎn)預(yù)測(cè)算法，在不同隨機(jī)游走步數(shù)下進(jìn)行了節(jié)點(diǎn)預(yù)測(cè)實(shí)驗(yàn)。表3給出了本文提出的節(jié)點(diǎn)預(yù)測(cè)算法MENP_LRW和MENP_MLRW的Precision和Recall隨著局部隨機(jī)游走步數(shù)的變化情況，其中，P代表Precision，R代表Recall，預(yù)測(cè)效果最好的情況用加粗表示。

為了更好地觀察兩種算法下評(píng)價(jià)指標(biāo)的變化圖4(a)和圖4(b)分別給出了采用不同相似性指標(biāo)的節(jié)點(diǎn)預(yù)測(cè)算法MENP_LRW和MENP_MLRW，其Precision和Recall隨著最大值隨機(jī)游走步數(shù)的變化情況。

從表2和圖3我們可以看出，在僅利用相似性指標(biāo)進(jìn)行預(yù)測(cè)的情況下，MLRW算法比LRW算法的精確率Precision高出1.37%，而召回率Recall則高出了12.86%。由此可知，在論文-關(guān)鍵詞二分網(wǎng)絡(luò)上，MLRW指標(biāo)比傳統(tǒng)局部隨機(jī)游走指標(biāo)LRW預(yù)測(cè)新生論文的效果得到顯著提高?？梢?jiàn)本文提出對(duì)雙向傳播過(guò)程的信息量取最大值能夠更好地表達(dá)信息傳播的強(qiáng)度，有利于選出聯(lián)系緊密的關(guān)鍵詞組，從而更好地預(yù)測(cè)新生節(jié)點(diǎn)。

表3 不同隨機(jī)游走步數(shù)下兩種預(yù)測(cè)算法的Precision和Recall

圖4 不同隨機(jī)游走步數(shù)下Precision和Recall變化情況

同時(shí)考慮了相似性和互斥性的節(jié)點(diǎn)預(yù)測(cè)算法MENP_LRW和MENP_MLRW與對(duì)應(yīng)的僅依靠相似性指標(biāo)進(jìn)行節(jié)點(diǎn)預(yù)測(cè)的效果相比也有一定程度的提升，其精確率分別提高了1.32%和0.21%，召回率則分別明顯提升了5.71%和24.28%。這說(shuō)明引入了互斥性的算法在預(yù)測(cè)新生論文時(shí)更有優(yōu)勢(shì)，表明我們提出的互斥關(guān)系概念可以使相似性指標(biāo)在一定程度上更加完善，幫助我們更準(zhǔn)確地定量描述節(jié)點(diǎn)間聯(lián)系的緊密性。其中，預(yù)測(cè)效果最為突出的是MENP_MLRW算法，其精確率達(dá)到3.01%，召回率達(dá)到45.71%，這表明MENP_MLRW節(jié)點(diǎn)預(yù)測(cè)算法在本文的論文-關(guān)鍵詞數(shù)據(jù)集上對(duì)于預(yù)測(cè)未來(lái)可能出現(xiàn)的新生節(jié)點(diǎn)即新生論文的效果最好。

由表3和圖4可以發(fā)現(xiàn)，在局部隨機(jī)游走步數(shù)相同的情況下，MENP_MLRW算法的精確率和召回率相較于MENP_LRW算法均有明顯提升，同樣說(shuō)明了在引入了互斥關(guān)系的節(jié)點(diǎn)預(yù)測(cè)算法下，采用MLRW指標(biāo)比采用傳統(tǒng)指標(biāo)LRW的預(yù)測(cè)效果更好。同時(shí)，隨著局部隨機(jī)游走步數(shù)的變化，節(jié)點(diǎn)預(yù)測(cè)算法MENP_LRW和MENP_MLRW的精確率和召回率都呈現(xiàn)下降趨勢(shì)，在隨機(jī)游走步數(shù)為2時(shí)精確率和召回率最高，表明預(yù)測(cè)效果最好。

根據(jù)表3，可以發(fā)現(xiàn)在實(shí)驗(yàn)結(jié)果最好的情況下，其Precision值可以說(shuō)是較低的。但是我們必須看到，本文實(shí)驗(yàn)的訓(xùn)練集中所有的關(guān)鍵詞組合情況是一個(gè)非常巨大的數(shù)據(jù)量，在這么龐大的數(shù)據(jù)基數(shù)的情況下我們所得到的Precision值雖然很小，但卻是完全有意義的。首先，根據(jù)前面劃分訓(xùn)練集部分內(nèi)容可以知道，最終關(guān)鍵詞處理后的個(gè)數(shù)為2 681，那么所有可能的關(guān)鍵詞組合情況高達(dá)將近720萬(wàn)種，在實(shí)驗(yàn)過(guò)程的最后我們會(huì)選擇對(duì)實(shí)驗(yàn)而言有意義的數(shù)據(jù)，我們知道關(guān)系緊密的關(guān)鍵詞組合大約1 000組左右，然而對(duì)于龐大的所有關(guān)鍵詞組合來(lái)說(shuō)，這1 000組關(guān)鍵詞組合顯然數(shù)目極小，僅僅占所有組合情況的約1/7 000，因此在這種比例下我們得到的Precision值雖然較小卻是非常有意義的。其次，實(shí)驗(yàn)數(shù)據(jù)集采集過(guò)程的不完美也是造成Precision較小的一種原因，《軟件學(xué)報(bào)》本身包含論文種類和領(lǐng)域比較繁瑣，因此我們要找的關(guān)鍵詞數(shù)據(jù)集過(guò)于分散，并且不具有領(lǐng)域性；再然后在關(guān)鍵詞同義詞處理過(guò)程中不可能完全準(zhǔn)確，因而實(shí)驗(yàn)存在一定的誤差。

4 結(jié)論

本文在基于二分網(wǎng)絡(luò)加權(quán)投影上研究預(yù)測(cè)新生節(jié)點(diǎn)的問(wèn)題，發(fā)現(xiàn)了網(wǎng)絡(luò)節(jié)點(diǎn)間存在一種互斥關(guān)系，給出了互斥關(guān)系ME的定義。然后，我們提出了在加權(quán)網(wǎng)絡(luò)上基于最大值隨機(jī)游走的相似性算法MLRW。最后，結(jié)合提出的互斥性和相似性指標(biāo)構(gòu)建了節(jié)點(diǎn)預(yù)測(cè)算法MENP，預(yù)測(cè)網(wǎng)絡(luò)中未來(lái)可能會(huì)出現(xiàn)的節(jié)點(diǎn)，并在采集的論文-關(guān)鍵詞數(shù)據(jù)集上成功驗(yàn)證了算法的優(yōu)勢(shì),其中效果最好的是結(jié)合了相似性MLRW的節(jié)點(diǎn)預(yù)測(cè)算法MENP_MLRW。

本文數(shù)據(jù)集來(lái)自于《軟件學(xué)報(bào)》2013-2017年所有論文。選取該期刊作為本文數(shù)據(jù)集旨在通過(guò)論文-關(guān)鍵詞二分網(wǎng)絡(luò)實(shí)現(xiàn)對(duì)未來(lái)可能產(chǎn)生的新生論文節(jié)點(diǎn)的預(yù)測(cè)，我們的實(shí)驗(yàn)也成功地驗(yàn)證了我們所提出的節(jié)點(diǎn)預(yù)測(cè)算法對(duì)于預(yù)測(cè)未來(lái)新生論文的可行性以及現(xiàn)實(shí)意義。我們的實(shí)驗(yàn)過(guò)程以及結(jié)果也存在一些問(wèn)題，在現(xiàn)階段主要存在以下兩個(gè)方面的困難：第一，在實(shí)驗(yàn)前期的數(shù)據(jù)集采集階段需要經(jīng)過(guò)一系列復(fù)雜的數(shù)據(jù)處理過(guò)程，包括論文信息批量導(dǎo)出，題目和關(guān)鍵詞的提取，關(guān)鍵詞編號(hào)、去重以及同義詞的處理等，這需要耗費(fèi)大量的時(shí)間；其次，我們需要具有較大影響力和較強(qiáng)領(lǐng)域性的期刊作為數(shù)據(jù)集來(lái)源，實(shí)現(xiàn)更好的實(shí)驗(yàn)效果。但實(shí)際的現(xiàn)狀是，一些期刊的論文信息在網(wǎng)站上不具備批量導(dǎo)出功能，這也是導(dǎo)致數(shù)據(jù)集獲取困難的原因。

綜上所述，今后的研究將從兩方面展開(kāi)。第一，在不同特征的網(wǎng)絡(luò)上本文節(jié)點(diǎn)預(yù)測(cè)算法的實(shí)際預(yù)測(cè)效果需要繼續(xù)進(jìn)行研究和探索，我們需要采集其他的實(shí)驗(yàn)數(shù)據(jù)集進(jìn)行下一步驗(yàn)證。第二，互斥性定義的準(zhǔn)確性在不同特征的網(wǎng)絡(luò)上是否具有適用性，也是我們接下來(lái)需要研究的主要內(nèi)容。