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

1、在自然界與人類社會(huì)活動(dòng)中，各種復(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ù)測(cè)?，F(xiàn)在，鏈接預(yù)測(cè)問(wèn)題在社會(huì)學(xué)、人類學(xué)、信息科學(xué)以及計(jì)算機(jī)科學(xué)等各個(gè)領(lǐng)域都受到了廣泛的關(guān)注。
　　相對(duì)于單分網(wǎng)絡(luò)，二分網(wǎng)絡(luò)不僅是復(fù)雜網(wǎng)絡(luò)中重要的表現(xiàn)形式之一，而且在現(xiàn)實(shí)社會(huì)復(fù)雜網(wǎng)絡(luò)中具有普遍性，已經(jīng)成為復(fù)雜網(wǎng)絡(luò)的重要研究對(duì)象。在現(xiàn)實(shí)社會(huì)中，許多復(fù)雜網(wǎng)絡(luò)都自然地

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

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

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

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