【摘要】：復(fù)雜網(wǎng)絡(luò)的鏈接預(yù)測問題已經(jīng)引起各個領(lǐng)域的越來越多的關(guān)注,如社會學(xué)、人類學(xué)、信息科學(xué)和計(jì)算機(jī)科學(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)注點(diǎn)是某些未知或未來的事件發(fā)生的可能性。在動態(tài)復(fù)雜的網(wǎng)絡(luò)中,時序的拓?fù)湫畔⑹窃O(shè)計(jì)實(shí)體之間的相似度函數(shù)的主要依據(jù)之一。但現(xiàn)有的動態(tài)網(wǎng)絡(luò)鏈路預(yù)測的算法往往不能充分應(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ù)我們所知,以前很少有文獻(xiàn)研究以鏈接發(fā)生頻率的時間序列作為輸入的鏈接預(yù)測工作。在本文中,我們研究設(shè)計(jì)整合時間和拓?fù)湫畔⒌挠行Х椒▉眍A(yù)測具有一定的不確定性、頂點(diǎn)具有屬性等動態(tài)鏈接的網(wǎng)絡(luò)的未來鏈接的有效方法。本文的主要貢獻(xiàn)如下：(1)我們提出了通過整合網(wǎng)絡(luò)中的時序信息、社區(qū)結(jié)構(gòu)和節(jié)點(diǎn)中心度的動態(tài)網(wǎng)絡(luò)鏈路預(yù)測的方法。該方法所使用的這些拓?fù)涮卣鲗τ陬A(yù)測復(fù)雜網(wǎng)絡(luò)的潛在鏈接是非常重要的。時序信息有助于分析動態(tài)網(wǎng)絡(luò)中的節(jié)點(diǎn)出現(xiàn)鏈接的規(guī)律。而社區(qū)結(jié)構(gòu)則使我們可以根據(jù)兩個頂點(diǎn)是否共位于同一個社區(qū),來分析他們之間的連接的緊密程度。一個節(jié)點(diǎn)的中心度是度量它在網(wǎng)絡(luò)內(nèi)相對重要性的指標(biāo),和它在復(fù)雜網(wǎng)絡(luò)中是否會有未來的鏈接具有高度的相關(guān)性。我們通過節(jié)點(diǎn)的特征向量中心度預(yù)測它未來的重要性,并作為鏈接預(yù)測的重要信息。我們整合網(wǎng)絡(luò)中包括社區(qū)結(jié)構(gòu)和中心度等各種拓?fù)湫畔?結(jié)合時序信息生成更加接近網(wǎng)絡(luò)實(shí)際的模型,在此基礎(chǔ)上進(jìn)行動態(tài)網(wǎng)絡(luò)鏈接預(yù)測。(2)我們提出了一種在不確定動態(tài)網(wǎng)絡(luò)中進(jìn)行鏈接預(yù)測的方法。由于觀察數(shù)據(jù)的不精確性、不完全性以及噪聲數(shù)據(jù)的干擾,在現(xiàn)實(shí)世界的網(wǎng)絡(luò)中,不確定性是一個自然的特征。在這樣的網(wǎng)絡(luò)中,每條邊與一個指示其在網(wǎng)絡(luò)中的存在的概率值相關(guān)聯(lián)。因此,在不確定網(wǎng)絡(luò)進(jìn)行鏈接預(yù)測的問題和在確定性網(wǎng)絡(luò)的鏈接預(yù)測有本質(zhì)的不同,它更具有挑戰(zhàn)性。我們提出了在不確定鏈接的動態(tài)網(wǎng)絡(luò)中的鏈接預(yù)測的方法。在該方法中,預(yù)測問題被形式化為一個設(shè)計(jì)在不確定時序網(wǎng)絡(luò)中的隨機(jī)游走。該算法首先將在不確定的網(wǎng)絡(luò)鏈路預(yù)測問題轉(zhuǎn)換成在確定性的網(wǎng)絡(luò)隨機(jī)游走問題。然后對每一個節(jié)點(diǎn)建立一個子圖,這個節(jié)點(diǎn)和它的鄰居之間的相似性得分可以在圍繞這個節(jié)點(diǎn)的子圖內(nèi)計(jì)算,以減少計(jì)算時間。(3)我們提出了一種解決頂點(diǎn)帶屬性的動態(tài)網(wǎng)絡(luò)鏈接預(yù)測問題的方法。在很多實(shí)際網(wǎng)絡(luò)中,頂點(diǎn)所代表的對象具有各種屬性,這些屬性值對鏈接預(yù)測有很高的參考價值。為此,我們提出了一種基于非負(fù)矩陣分解(NMF)的方法的對頂點(diǎn)帶屬性的動態(tài)網(wǎng)絡(luò)進(jìn)行鏈接預(yù)測。該方法從網(wǎng)絡(luò)中的動態(tài)拓?fù)浣Y(jié)構(gòu)以及頂點(diǎn)屬性信息中獲取隱特征,以獲得更高的預(yù)測結(jié)果。我們提出了進(jìn)行非負(fù)矩陣分解的迭代算法,并證明了這些算法的收斂性和正確性。通過非負(fù)矩陣分解可得到反映網(wǎng)絡(luò)重要的動態(tài)隱拓?fù)涮卣鞯牡碗A矩陣,集成了動態(tài)網(wǎng)絡(luò)中的時序信息和全局拓?fù)湫畔?并能獲得更準(zhǔn)確的結(jié)果。我們在真實(shí)社交網(wǎng)絡(luò)上的實(shí)驗(yàn)結(jié)果表明,該方法能夠有效預(yù)測頂點(diǎn)帶屬性社交網(wǎng)絡(luò)中未來的鏈接,并取得比其他類似的方法更高質(zhì)量的預(yù)測效果。(4)我們提出了一種基于抽樣的方法,對動態(tài)網(wǎng)絡(luò)中某些感興趣的頂點(diǎn)進(jìn)行鏈接預(yù)測。在許多動態(tài)網(wǎng)絡(luò)的實(shí)際應(yīng)用中,我們僅需要預(yù)測與某些感興趣的頂點(diǎn)相關(guān)的鏈接,即只需計(jì)算與用戶感興趣的頂點(diǎn)之間的相似性得分,而不是預(yù)測網(wǎng)絡(luò)中所有頂點(diǎn)對之間的相似性。顯然在這種情況下,我們并不需要使用傳統(tǒng)的方法對整個網(wǎng)絡(luò)進(jìn)行鏈接預(yù)測。為此,我們提出了一種基于抽樣的快速方法來預(yù)測在動態(tài)網(wǎng)絡(luò)中相關(guān)的感興趣的節(jié)點(diǎn)的鏈接。在該方法中,我們使用一個適當(dāng)?shù)乃p因子來對較近的網(wǎng)絡(luò)拓?fù)湫畔①x予較高的權(quán)重。然后,我們用隨機(jī)游走的方法以網(wǎng)絡(luò)中所關(guān)注的節(jié)點(diǎn)為中心構(gòu)造一個加權(quán)子圖。我們選擇這個子圖的一個適當(dāng)?shù)拇笮?從而使得所估計(jì)的相似度誤差限定在一個給定的閾值范圍內(nèi)。由于相似性得分可以在一個很小的子圖內(nèi)計(jì)算得到,該算法可以大大減少計(jì)算時間。該方法也擴(kuò)展到預(yù)測整個網(wǎng)絡(luò)的潛在鏈接,以達(dá)到較高的處理速度和準(zhǔn)確性。由于所提出的方法能夠集成網(wǎng)絡(luò)時序信息和全局拓?fù)湫畔?因而能獲得更準(zhǔn)確的預(yù)測結(jié)果。上述本文所提出的所有方法都已經(jīng)在不同的實(shí)際網(wǎng)絡(luò)上進(jìn)行了測試。我們通過實(shí)驗(yàn)來驗(yàn)證所提出方法的性能,并通過設(shè)置不同的參數(shù)值來分析他們的結(jié)果,同時還與其他類似的方法比較他們的性能。大量的實(shí)驗(yàn)結(jié)果表明,我們的方法可在較少的時間內(nèi)獲得比其他方法質(zhì)量較高的預(yù)測結(jié)果。
[Abstract]:......
【學(xué)位授予單位】：揚(yáng)州大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2016
【分類號】：O157.5
，

本文編號：2351852