基于網(wǎng)絡拓撲性質(zhì)和路徑的鏈路預測算法.pdf

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

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

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

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