基于網(wǎng)絡(luò)拓?fù)湫再|(zhì)和路徑的鏈路預(yù)測算法.pdf

1、我們處在一個由許許多多的復(fù)雜系統(tǒng)所構(gòu)成的世界中，如我們所在的生物圈、我們所在的社會等等，而滲透在我們生活中的這些復(fù)雜系統(tǒng)都可以被抽象為復(fù)雜網(wǎng)絡(luò)，在這個網(wǎng)絡(luò)中，節(jié)點表示真實世界中的對象，邊表示的是它們之間的關(guān)系。網(wǎng)絡(luò)中蘊(yùn)含著大量的信息，而且這些信息會隨著網(wǎng)絡(luò)的不斷演化而變化，所以在當(dāng)前復(fù)雜網(wǎng)絡(luò)的研究中網(wǎng)絡(luò)的演化是一個熱點，而在網(wǎng)絡(luò)演化的研究中有一個基本的問題就是網(wǎng)絡(luò)的鏈路預(yù)測。鏈路預(yù)測是挖掘網(wǎng)絡(luò)中的隱含信息和預(yù)測網(wǎng)絡(luò)將要演化的方向。具體的

2、說，就是利用網(wǎng)絡(luò)中的各種信息，對網(wǎng)絡(luò)中丟失的連邊進(jìn)行尋找和對目前不存在的連邊進(jìn)行預(yù)測。
　　處理鏈路預(yù)測的傳統(tǒng)方法是利用機(jī)器學(xué)習(xí)對網(wǎng)絡(luò)中的節(jié)點和邊按照它們的屬性進(jìn)行分類。隨著我們進(jìn)入了一個數(shù)據(jù)爆發(fā)的時代，網(wǎng)絡(luò)的規(guī)模越來越大，基于機(jī)器學(xué)習(xí)的方法已經(jīng)不能夠提供良好的預(yù)測準(zhǔn)確性。所以我們將目光轉(zhuǎn)向了利用網(wǎng)絡(luò)的結(jié)構(gòu)信息來進(jìn)行預(yù)測。目前基于相似性的鏈路預(yù)測算法是一種受關(guān)注度較高的方向，這種算法往往能帶給我們較好的預(yù)測結(jié)果以及相對低的時間復(fù)雜

3、度。因此本文主要關(guān)注在相似性算法的基礎(chǔ)上如何對鏈路預(yù)測的結(jié)果進(jìn)行提升。
　　網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)是網(wǎng)絡(luò)中所包含的重要結(jié)構(gòu)，是網(wǎng)絡(luò)性質(zhì)的決定因素。評價網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的方式有網(wǎng)路聚集系數(shù)和社團(tuán)結(jié)構(gòu)。本文首先將聚集系數(shù)應(yīng)用到相似性指標(biāo)中，來提高預(yù)測結(jié)果的準(zhǔn)確性。一般來說，聚集系數(shù)較高的網(wǎng)絡(luò)，各種相似性指標(biāo)均可以獲得較為理想的結(jié)果，尤其是CN指標(biāo)，AA指標(biāo)和RA指標(biāo)。所以我們將節(jié)點的聚集系數(shù)結(jié)合到基于局部結(jié)構(gòu)的相似性指標(biāo)中，并在多個網(wǎng)絡(luò)上進(jìn)行實驗

4、，獲得了良好的預(yù)測結(jié)果。其次，社團(tuán)結(jié)構(gòu)是網(wǎng)絡(luò)中另一個重要的拓?fù)浣Y(jié)構(gòu)，社團(tuán)結(jié)構(gòu)內(nèi)部節(jié)點之間聯(lián)系緊密，不同社團(tuán)之間節(jié)點的聯(lián)系相對稀疏，所以社團(tuán)結(jié)構(gòu)的這種特性與節(jié)點之間的相似性有天然的聯(lián)系。因此，我們將社團(tuán)的這種特性結(jié)合到相似性指標(biāo)中，先定義節(jié)點之間的緊密程度，隨后提出基于節(jié)點間緊密度的一類相似性指標(biāo)，并在多個真實網(wǎng)絡(luò)上進(jìn)行實驗，驗證了基于社團(tuán)結(jié)構(gòu)的算法的有效性。最后，資源分配的相似性算法是一個預(yù)測性能非常好的算法，于是我們它擴(kuò)展到高階的路徑