基于社團結(jié)構(gòu)和自信息的復(fù)雜網(wǎng)絡(luò)鏈路預(yù)測算法研究.pdf

1、現(xiàn)實世界中很多復(fù)雜系統(tǒng)諸如社會、生物、信息系統(tǒng)甚至自然道路河流都可以用復(fù)雜網(wǎng)絡(luò)來抽象表示，以網(wǎng)絡(luò)中的結(jié)點表示對象，以邊表示對象之間的交互關(guān)系。復(fù)雜網(wǎng)絡(luò)蘊藏的信息會隨著真實系統(tǒng)不斷演化而疊積，交互關(guān)系（鏈接）作為其中的一種重要信息載體，對其進行挖掘顯得十分必要。作為信息挖掘的基礎(chǔ)研究問題之一，鏈路預(yù)測能夠根據(jù)已知的網(wǎng)絡(luò)拓撲結(jié)構(gòu)，網(wǎng)絡(luò)節(jié)點屬性等一系列特征來發(fā)掘其中的隱含信息，同時它也是對網(wǎng)絡(luò)不完整性的一種補全手段。具體來說，鏈路預(yù)測就是通過

2、衡量各種與網(wǎng)絡(luò)密切相關(guān)的影響因素，充分利用這些因素來預(yù)測網(wǎng)絡(luò)中丟失的鏈接和未來可能產(chǎn)生的鏈接。
　　隨著大數(shù)據(jù)時代的降臨，已有的某些預(yù)測算法已經(jīng)不能滿足實際問題的需要，算法的預(yù)測準(zhǔn)度還需要進一步提高。目前鏈路預(yù)測的主流研究方向是基于相似性度量的方法，此類方法有著較低的時間復(fù)雜度和較高的預(yù)測能力?；诟怕誓Ｐ偷姆椒ㄒ驗榧夹g(shù)手段的革新也受到越來越多的重視，此類方法隨著模型的精確構(gòu)建而有著越來越高的預(yù)測精度，同時時間復(fù)雜度也逐步被降低。

3、
　　本文在前人工作的基礎(chǔ)上分別對這兩類預(yù)測算法進行了深入研究，并在此基礎(chǔ)上從網(wǎng)絡(luò)結(jié)構(gòu)特性和信息論角度出發(fā)，提出了基于網(wǎng)絡(luò)社團結(jié)構(gòu)的CS-Based算法和基于自信息的CNSI算法。CS-Based算法思想來源于復(fù)雜網(wǎng)絡(luò)社團結(jié)構(gòu)本身的特性：社團內(nèi)部聯(lián)系緊密，社團與社團之間連接相對稀疏。本文認(rèn)為這一性質(zhì)對鏈路預(yù)測有著重要的促進作用，社團內(nèi)的節(jié)點相似度會因社團本身的緊密程度而得到提升，社團之間的節(jié)點相似度也會因為社團之間的緊密度而提升。

4、如果將社團這種特性加入到鏈路預(yù)測中，將會很大程度上提高算法的準(zhǔn)度。真實數(shù)據(jù)集上的實驗得出，CS-Based算法預(yù)測性能優(yōu)于其他經(jīng)典方法。對于 CNSI算法，本文通過信息論知識建立預(yù)測模型，將節(jié)點間的相似度轉(zhuǎn)化為網(wǎng)絡(luò)中某些重要特征存在的前提下節(jié)點成鏈的條件自信息，如果越多的特征存在，比如本文中用到的共同鄰居、不同長度的路徑等，自信息就越小，由此反映出節(jié)點間發(fā)生鏈接的可能性越大。最后通過實驗同樣證明了 CNSI方法較好的預(yù)測能力，優(yōu)于其他對