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

本文編號(hào)：2351852