基于鏈路預測的復雜網絡瓦解建模與分析.pdf

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

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

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

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

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

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

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