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

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

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

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

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

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

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

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