二分網(wǎng)絡(luò)鏈接預(yù)測的研究及應(yīng)用.pdf

1、在自然界與人類社會活動中，各種復(fù)雜類型的系統(tǒng)都可以轉(zhuǎn)化成相應(yīng)的復(fù)雜網(wǎng)絡(luò)，比如經(jīng)濟(jì)系統(tǒng)、生物系統(tǒng)、群體生態(tài)系統(tǒng)以及其他領(lǐng)域內(nèi)系統(tǒng)。復(fù)雜網(wǎng)絡(luò)分析領(lǐng)域的一個(gè)重要研究方向是它的鏈接預(yù)測?，F(xiàn)在，鏈接預(yù)測問題在社會學(xué)、人類學(xué)、信息科學(xué)以及計(jì)算機(jī)科學(xué)等各個(gè)領(lǐng)域都受到了廣泛的關(guān)注。
　　相對于單分網(wǎng)絡(luò)，二分網(wǎng)絡(luò)不僅是復(fù)雜網(wǎng)絡(luò)中重要的表現(xiàn)形式之一，而且在現(xiàn)實(shí)社會復(fù)雜網(wǎng)絡(luò)中具有普遍性，已經(jīng)成為復(fù)雜網(wǎng)絡(luò)的重要研究對象。在現(xiàn)實(shí)社會中，許多復(fù)雜網(wǎng)絡(luò)都自然地

2、呈現(xiàn)出二分結(jié)構(gòu)。譬如:作者與文章的合作網(wǎng)絡(luò)、演員與影視作品的合作網(wǎng)絡(luò)、投資者與股份制公司的股份合作網(wǎng)絡(luò)、疾病與基因的作用網(wǎng)絡(luò)、俱樂部成員與俱樂部舉辦活動的參與網(wǎng)絡(luò)、觀眾與歌曲的喜好網(wǎng)絡(luò)、P2P系統(tǒng)中終端計(jì)算與交互數(shù)據(jù)的網(wǎng)絡(luò)等。因此，二分網(wǎng)絡(luò)鏈接預(yù)測對于研究復(fù)雜網(wǎng)絡(luò)有非常重要的理論意義和實(shí)用價(jià)值。譬如，在學(xué)術(shù)圈的探測、功能分析、推薦系統(tǒng)、疾病診斷以及鏈接預(yù)測等方面都有很多重要的應(yīng)用。
　　雖然已有一些工作提出了對于二分網(wǎng)絡(luò)鏈接預(yù)測的

3、算法，但是這些算法都具有復(fù)雜度較高、預(yù)測困難等問題，不能應(yīng)用于大規(guī)模網(wǎng)絡(luò)。本文針對以上問題，研究二分網(wǎng)絡(luò)鏈接預(yù)測的有效算法，主要工作以及研究成果有:
　　(1)我們提出了基于投影的二分網(wǎng)絡(luò)鏈接預(yù)測算法。算法首先將二部圖投影到一個(gè)單部圖，在此基礎(chǔ)上定義了潛在邊的概念，使得對二分網(wǎng)絡(luò)鏈接預(yù)測僅在潛在邊中進(jìn)行，大大降低了預(yù)測算法的復(fù)雜度。我們定義了潛在邊所覆蓋的模式以及模式的權(quán)重，通過潛在邊所覆蓋的模式的權(quán)重來計(jì)算潛在邊的可信度，作為該

4、潛在邊上存在實(shí)際鏈接的評分。實(shí)驗(yàn)結(jié)果表明，所提出的算法能夠有效地提高鏈接預(yù)測的速度和結(jié)果的精度。
　　(2)針對二分網(wǎng)絡(luò)中數(shù)據(jù)存在的高維稀疏性特點(diǎn)，受壓縮感知中對缺失數(shù)據(jù)恢復(fù)方法的啟發(fā)，提出基于低秩矩陣完全的網(wǎng)絡(luò)鏈接預(yù)測算法。已有的鏈接預(yù)測算法難免受數(shù)據(jù)稀疏性的影響而降低預(yù)測的準(zhǔn)確性，基于低秩矩陣完全的網(wǎng)絡(luò)鏈接預(yù)測算法可以在不改變原有數(shù)據(jù)的情況下恢復(fù)缺失數(shù)據(jù)并進(jìn)行填充，從而對未鏈接的邊進(jìn)行預(yù)測。通過大量的對比實(shí)驗(yàn)驗(yàn)證，所提出的算法

5、可以取得較高的預(yù)測精度。
　　(3)在實(shí)際的推薦問題中，由于數(shù)據(jù)的高維稀疏性等問題存在，使得推薦的過程耗時(shí)長，算法時(shí)間復(fù)雜度高。已有的算法對于實(shí)時(shí)更新的網(wǎng)絡(luò)的推薦準(zhǔn)確度較低。我們在二分網(wǎng)絡(luò)上提出基于非負(fù)矩陣分解的動態(tài)推薦算法。算法主要針對兩種經(jīng)常出現(xiàn)的數(shù)據(jù)更新情況。第一種是針對用戶評分矩陣中用戶修改評分的情況，第二種是針對用戶評分矩陣中新增加用戶評分向量的情況。算法的主要思路是運(yùn)用非負(fù)矩陣分解方法，將原始矩陣分解成兩個(gè)非負(fù)的基矩陣