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

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

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

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

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