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

1、在自然界與人類社會活動中，各種復雜類型的系統(tǒng)都可以轉(zhuǎn)化成相應的復雜網(wǎng)絡(luò)，比如經(jīng)濟系統(tǒng)、生物系統(tǒng)、群體生態(tài)系統(tǒng)以及其他領(lǐng)域內(nèi)系統(tǒng)。復雜網(wǎng)絡(luò)分析領(lǐng)域的一個重要研究方向是它的鏈接預測?，F(xiàn)在，鏈接預測問題在社會學、人類學、信息科學以及計算機科學等各個領(lǐng)域都受到了廣泛的關(guān)注。
　　相對于單分網(wǎng)絡(luò)，二分網(wǎng)絡(luò)不僅是復雜網(wǎng)絡(luò)中重要的表現(xiàn)形式之一，而且在現(xiàn)實社會復雜網(wǎng)絡(luò)中具有普遍性，已經(jīng)成為復雜網(wǎng)絡(luò)的重要研究對象。在現(xiàn)實社會中，許多復雜網(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)中終端計算與交互數(shù)據(jù)的網(wǎng)絡(luò)等。因此，二分網(wǎng)絡(luò)鏈接預測對于研究復雜網(wǎng)絡(luò)有非常重要的理論意義和實用價值。譬如，在學術(shù)圈的探測、功能分析、推薦系統(tǒng)、疾病診斷以及鏈接預測等方面都有很多重要的應用。
　　雖然已有一些工作提出了對于二分網(wǎng)絡(luò)鏈接預測的

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

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

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