復(fù)雜動態(tài)網(wǎng)絡(luò)的鏈接預(yù)測.pdf

1、復(fù)雜網(wǎng)絡(luò)的鏈接預(yù)測問題已經(jīng)引起各個領(lǐng)域的越來越多的關(guān)注，如社會學(xué)、人類學(xué)、信息科學(xué)和計算機科學(xué)。至今為止，鏈路預(yù)測研究的工作大部分是基于靜態(tài)網(wǎng)絡(luò)上的。在靜態(tài)的網(wǎng)絡(luò)中，部分網(wǎng)絡(luò)結(jié)構(gòu)是已知的，其目標(biāo)是預(yù)測其他的潛在的鏈接。在這樣的靜態(tài)網(wǎng)絡(luò)中，鏈路的產(chǎn)生通常建模為一次性事件，我們的主要關(guān)注點是某些未知或未來的事件發(fā)生的可能性。在動態(tài)復(fù)雜的網(wǎng)絡(luò)中，時序的拓?fù)湫畔⑹窃O(shè)計實體之間的相似度函數(shù)的主要依據(jù)之一。但現(xiàn)有的動態(tài)網(wǎng)絡(luò)鏈路預(yù)測的算法往往不能充分

2、應(yīng)用時序的拓?fù)湫畔?。一般來說，基于靜態(tài)圖表示的鏈接預(yù)測方法不能處理在動態(tài)網(wǎng)絡(luò)中重復(fù)出現(xiàn)的鏈接，也無法識別動態(tài)網(wǎng)絡(luò)巾的時間序列模式，而這兩者是動態(tài)網(wǎng)絡(luò)鏈接預(yù)測中所用到的主要信息。因此，有必要研究適用于預(yù)測動態(tài)網(wǎng)絡(luò)鏈接的有效方法。據(jù)我們所知，以前很少有文獻研究以鏈接發(fā)生頻率的時間序列作為輸入的鏈接預(yù)測工作。在本文中，我們研究設(shè)計整合時間和拓?fù)湫畔⒌挠行Х椒▉眍A(yù)測具有一定的不確定性、頂點具有屬性等動態(tài)鏈接的網(wǎng)絡(luò)的未來鏈接的有效方法。本文的主要

3、貢獻如下:
　　(1)我們提出了通過整合網(wǎng)絡(luò)中的時序信息、社區(qū)結(jié)構(gòu)和節(jié)點中心度的動態(tài)網(wǎng)絡(luò)鏈路預(yù)測的方法。該方法所使用的這些拓?fù)涮卣鲗τ陬A(yù)測復(fù)雜網(wǎng)絡(luò)的潛在鏈接是非常重要的。時序信息有助于分析動態(tài)網(wǎng)絡(luò)中的節(jié)點出現(xiàn)鏈接的規(guī)律。而社區(qū)結(jié)構(gòu)則使我們可以根據(jù)兩個頂點是否共位于同一個社區(qū)，來分析他們之間的連接的緊密程度。一個節(jié)點的中心度是度量它在網(wǎng)絡(luò)內(nèi)相對重要性的指標(biāo)，和它在復(fù)雜網(wǎng)絡(luò)中是否會有未來的鏈接具有高度的相關(guān)性。我們通過節(jié)點的特征向量中

4、心度預(yù)測它未來的重要性，并作為鏈接預(yù)測的重要信息。我們整合網(wǎng)絡(luò)中包括社區(qū)結(jié)構(gòu)和中心度等各種拓?fù)湫畔?，結(jié)合時序信息生成更加接近網(wǎng)絡(luò)實際的模型，在此基礎(chǔ)上進行動態(tài)網(wǎng)絡(luò)鏈接預(yù)測。
　　(2)我們提出了一種在不確定動態(tài)網(wǎng)絡(luò)中進行鏈接預(yù)測的方法。由于觀察數(shù)據(jù)的不精確性、不完全性以及噪聲數(shù)據(jù)的干擾，在現(xiàn)實世界的網(wǎng)絡(luò)中，不確定性是一個自然的特征。在這樣的網(wǎng)絡(luò)中，每條邊與一個指示其在網(wǎng)絡(luò)中的存在的概率值相關(guān)聯(lián)。因此，在不確定網(wǎng)絡(luò)進行鏈接預(yù)測的問題

5、和在確定性網(wǎng)絡(luò)的鏈接預(yù)測有本質(zhì)的不同，它更具有挑戰(zhàn)性。我們提出了在不確定鏈接的動態(tài)網(wǎng)絡(luò)中的鏈接預(yù)測的方法。在該方法中，預(yù)測問題被形式化為一個設(shè)計在不確定時序網(wǎng)絡(luò)中的隨機游走。該算法首先將在不確定的網(wǎng)絡(luò)鏈路預(yù)測問題轉(zhuǎn)換成在確定性的網(wǎng)絡(luò)隨機游走問題。然后對每一個節(jié)點建立一個子圖，這個節(jié)點和它的鄰居之間的相似性得分可以在圍繞這個節(jié)點的子圖內(nèi)計算，以減少計算時間。
　　(3)我們提出了一種解決頂點帶屬性的動態(tài)網(wǎng)絡(luò)鏈接預(yù)測問題的方法。在很多

6、實際網(wǎng)絡(luò)中，頂點所代表的對象具有各種屬性，這些屬性值對鏈接預(yù)測有很高的參考價值。為此，我們提出了一種基于非負(fù)矩陣分解(NMF)的方法的對頂點帶屬性的動態(tài)網(wǎng)絡(luò)進行鏈接預(yù)測。該方法從網(wǎng)絡(luò)中的動態(tài)拓?fù)浣Y(jié)構(gòu)以及頂點屬性信息中獲取隱特征，以獲得更高的預(yù)測結(jié)果。我們提出了進行非負(fù)矩陣分解的迭代算法，并證明了這些算法的收斂性和正確性。通過非負(fù)矩陣分解可得到反映網(wǎng)絡(luò)重要的動態(tài)隱拓?fù)涮卣鞯牡碗A矩陣，集成了動態(tài)網(wǎng)絡(luò)中的時序信息和全局拓?fù)湫畔?，并能獲得更準(zhǔn)確

7、的結(jié)果。我們在真實社交網(wǎng)絡(luò)上的實驗結(jié)果表明，該方法能夠有效預(yù)測頂點帶屬性社交網(wǎng)絡(luò)中未來的鏈接，并取得比其他類似的方法更高質(zhì)量的預(yù)測效果。
　　(4)我們提出了一種基于抽樣的方法，對動態(tài)網(wǎng)絡(luò)中某些感興趣的頂點進行鏈接預(yù)測。在許多動態(tài)網(wǎng)絡(luò)的實際應(yīng)用中，我們僅需要預(yù)測與某些感興趣的頂點相關(guān)的鏈接，即只需計算與用戶感興趣的頂點之間的相似性得分，而不是預(yù)測網(wǎng)絡(luò)中所有頂點對之間的相似性。顯然在這種情況下，我們并不需要使用傳統(tǒng)的方法對整個網(wǎng)絡(luò)進

8、行鏈接預(yù)測。為此，我們提出了一種基于抽樣的快速方法來預(yù)測在動態(tài)網(wǎng)絡(luò)中相關(guān)的感興趣的節(jié)點的鏈接。在該方法中，我們使用一個適當(dāng)?shù)乃p因子來對較近的網(wǎng)絡(luò)拓?fù)湫畔①x予較高的權(quán)重。然后，我們用隨機游走的方法以網(wǎng)絡(luò)中所關(guān)注的節(jié)點為中心構(gòu)造一個加權(quán)子圖。我們選擇這個子圖的一個適當(dāng)?shù)拇笮?，從而使得所估計的相似度誤差限定在一個給定的閾值范圍內(nèi)。由于相似性得分可以在一個很小的子圖內(nèi)計算得到，該算法可以大大減少計算時間。該方法也擴展到預(yù)測整個網(wǎng)絡(luò)的潛在鏈接，