基于鏈路預(yù)測的復(fù)雜網(wǎng)絡(luò)瓦解建模與分析.pdf

1、隨著科學技術(shù)的高速發(fā)展，21世紀的人類社會常被冠以“網(wǎng)絡(luò)時代”的頭銜?？梢哉f，我們的生活離不開網(wǎng)絡(luò)。但是，人類在享受信息化生活帶來的便利的同時也面臨著一系列嚴峻的問題。近十年來，從SARS、埃博拉到熊貓燒香、灰鴿子，計算機及生物病毒的爆發(fā)和傳播越發(fā)頻繁且難以控制；9.11事件后，各種恐怖組織網(wǎng)絡(luò)的破壞活動更加猖獗。對于病毒傳播網(wǎng)絡(luò)、恐怖組織網(wǎng)絡(luò)這類有害的網(wǎng)絡(luò)，我們希望通過免疫、擾動、瓦解等手段摧毀其網(wǎng)絡(luò)結(jié)構(gòu)，使其網(wǎng)絡(luò)功能不能正常發(fā)揮。因

2、此，網(wǎng)絡(luò)科學問題中復(fù)雜網(wǎng)絡(luò)瓦解策略研究的越來越具有重大理論意義和應(yīng)用價值。從最初基于零信息、完全信息的研究，到近來基于不確定或不完全信息條件下瓦解策略的研究，關(guān)于復(fù)雜網(wǎng)絡(luò)瓦解策略的研究更加貼近現(xiàn)實世界實際情況，成為極其重要而且富有挑戰(zhàn)性的前沿課題。
　　本文針對目前不完全信息條件下復(fù)雜網(wǎng)絡(luò)瓦解策略研究中存在的不足，以復(fù)雜網(wǎng)絡(luò)和鏈路預(yù)測相關(guān)理論知識為指導(dǎo)，在復(fù)雜網(wǎng)絡(luò)瓦解建模中引入鏈路預(yù)測用以恢復(fù)部分缺失信息，圍繞瓦解信息的刻畫、瓦解

3、模式的定義以及瓦解效果的評估三個問題，綜合運用統(tǒng)計物理中傳統(tǒng)圖論知識，以及矩陣論、線性代數(shù)、軍事運籌學、博弈論、概率論與數(shù)理統(tǒng)計、控制仿真等多學科領(lǐng)域知識，深入系統(tǒng)的研究了復(fù)雜網(wǎng)絡(luò)瓦解問題的建模、分析以及鏈路預(yù)測的作用。論文主要研究工作及創(chuàng)新點如下：
　　（1）將鏈路預(yù)測引入復(fù)雜網(wǎng)絡(luò)瓦解建模問題。從復(fù)雜網(wǎng)絡(luò)的角度研究和分析鏈路預(yù)測，在不完全信息條件下，將具有數(shù)據(jù)挖掘、恢測以及網(wǎng)絡(luò)演化重構(gòu)作用的鏈路預(yù)測技術(shù)引入到網(wǎng)絡(luò)瓦解建模中?；?/p>

4、已知信息，通過鏈路預(yù)測算法刻畫網(wǎng)絡(luò)結(jié)構(gòu)相似性，有效地還原了部分缺失的網(wǎng)絡(luò)結(jié)構(gòu)信息。分析了在網(wǎng)絡(luò)瓦解層面多種鏈路預(yù)測的作用。研究發(fā)現(xiàn)，相對于隨機加邊，鏈路預(yù)測算法預(yù)測精度和效率的提高在10倍以上。然后，鏈路預(yù)測的作用遠大于其此，從網(wǎng)絡(luò)瓦解的角度出發(fā)，其衡量標準并不關(guān)心是否準確的恢復(fù)出缺失連邊，而是是否找到重要節(jié)點，鏈路預(yù)測對某些邊的“張冠李戴”，是將網(wǎng)絡(luò)理想化的趨勢，導(dǎo)致的自身精度下降，卻并不影響我們找到網(wǎng)絡(luò)結(jié)構(gòu)層面上的重要節(jié)點和網(wǎng)絡(luò)瓦解

5、效果的提升。
　　（2）建立了基于鏈路預(yù)測的復(fù)雜網(wǎng)絡(luò)瓦解模型。通過瓦解信息、瓦解模式、瓦解效果以及鏈路預(yù)測的定量描述，構(gòu)建了基于鏈路預(yù)測的網(wǎng)絡(luò)瓦解模型，并在無標度網(wǎng)絡(luò)和ER隨機模型網(wǎng)絡(luò)上進行了仿真分析。研究發(fā)現(xiàn)，在無標度網(wǎng)絡(luò)中，相對于現(xiàn)有的在不完全信息條件下，基于已知信息進行網(wǎng)絡(luò)瓦解和隨機攻擊，模型中的瓦解方法顯著提高了的復(fù)雜網(wǎng)絡(luò)瓦解效果；而由于ER網(wǎng)絡(luò)節(jié)點間連邊是一個概率事件，本身具有隨機性，其相似性難以刻畫，我們很難通過鏈路預(yù)

6、測找到重要節(jié)點實施重點打擊，故對瓦解效果提高不明顯；進一步，我們分析了10種預(yù)測算法在模型中的表現(xiàn)，發(fā)現(xiàn)這些算法普遍表現(xiàn)較好；最后，我們針對不同的信息缺失比例，仿真分析了其了最優(yōu)的鏈路預(yù)測強度，為攻擊者提供了建議和指導(dǎo)。
　?。?）揭示了鏈路預(yù)測的漫畫效應(yīng)。研究發(fā)現(xiàn)，在信息丟失比例不大的情況下，通過鏈路預(yù)測，雖然不能完整地恢復(fù)網(wǎng)絡(luò)結(jié)構(gòu)的所有信息，卻可以使網(wǎng)絡(luò)的結(jié)構(gòu)特征更加突出，使得網(wǎng)絡(luò)瓦解效果優(yōu)于完全信息下的瓦解效果。這是因為，在

7、網(wǎng)絡(luò)瓦解層面，其關(guān)注的不是每一個節(jié)點每一條邊的真實性，而是在網(wǎng)絡(luò)瓦解層面從結(jié)構(gòu)上如何捕捉那些對網(wǎng)絡(luò)結(jié)構(gòu)功能影響很大的重要節(jié)點，即網(wǎng)絡(luò)的特征。我們可以認為，鏈路預(yù)測作為一種工具，在恢復(fù)和重構(gòu)網(wǎng)絡(luò)時，通過計算網(wǎng)絡(luò)結(jié)構(gòu)相似性，能夠在加邊時夸張和加強這種效果。鏈路預(yù)測如同具有銳化功能的畫圖工具一樣，同一張人物肖像照，通過鏈路預(yù)測展現(xiàn)出來就像一幅漫畫，雖沒有原來的照片真實清晰，卻更好的反映了所刻畫人物的外貌特征，使人過目不忘，印象更深。我們稱鏈路