基于滲流理論的鏈路預測算法研究.pdf

1、大數(shù)據時代，信息以網絡的形式呈現(xiàn)，可以說網絡是對復雜系統(tǒng)的一種抽象表達。節(jié)點表示復雜系統(tǒng)中的主體，連邊表示主體間的相互作用關系。對網絡的研究有助于我們更深刻地理解和認識其所對應的復雜系統(tǒng)。網絡中的鏈路預測則是對復雜系統(tǒng)中主體間相互作用關系的預測。它根據觀察到的網絡結構等信息，預測實際存在但未被檢測到的，或者未來某一時刻可能會出現(xiàn)的連邊。
　　隨著信息技術的發(fā)展，大量來自社會經濟系統(tǒng)中的數(shù)據更容易獲取和收集，但是由于數(shù)量龐大，結構復

2、雜等特點，使得收集的數(shù)據存在錯誤和缺失的問題，這為科學研究的可靠性帶來極大的挑戰(zhàn)。應用鏈路預測方法可以對網絡中的虛假信息進行識別，對于缺失連接進行補充，進而對網絡實現(xiàn)重構，使其更接近于真實的情況。
　　本文首先回顧了近幾年鏈路預測的研究進展，以及滲流理論在物理和網絡科學中的發(fā)展概況，然后提出一種創(chuàng)新的基于網絡鍵滲流過程的鏈路預測方法。網絡中每一條邊以概率p保留，1-p刪除，隨著p增大網絡形成一個最大的連通分量，此時網絡處于滲流狀態(tài)

3、，所對應的p為滲流臨界值，即pc。滲流鏈路預測方法的基本假設是經過刪邊過程，網絡破碎成多個小的連通分量，如果兩個節(jié)點處于同一連通分量的概率較大，則他們之間更有可能產生連邊。在四個真實網絡中的實驗結果表明，本算法在網絡臨界值附近能夠獲得較高的預測精度，并優(yōu)于一些傳統(tǒng)的鏈路預測方法。同時，由于該算法可以并行化計算，因此可以處理大規(guī)模網絡的鏈路預測問題。為了探究算法的適用性及其內在機制，本論文設計了一系列網絡模型來考察算法的影響因素，包括可調

4、節(jié)網絡集聚系數(shù)的模型，可調節(jié)網絡平均度的模型以及可調節(jié)模塊度的模型。結果發(fā)現(xiàn)：隨著集聚系數(shù)增加，網絡的預測效果越來越好；隨著網絡密度的增加，最優(yōu)的預測參數(shù) p*越來越接近網絡滲流臨界值pc；模塊度對p*的影響不明顯，但是隨著模塊度的增加pc越來越大，使得 p*向左偏離 pc；相比傳統(tǒng)預測方法，滲流預測方法在集聚系數(shù)小且模塊度較大的網絡中表現(xiàn)出更大的優(yōu)勢。最后，我們將本算法進一步擴展到含權網絡中，提出含權滲流鏈路預測方法，并應用到腦網絡連