本文關鍵詞：復雜網(wǎng)絡的節(jié)點重要性度量算法研究

  更多相關文章： 復雜網(wǎng)絡 重要節(jié)點 貢獻度 KSC算法

【摘要】：近年來,眾多復雜網(wǎng)絡研究學者越來越關注復雜網(wǎng)絡中重要節(jié)點發(fā)現(xiàn)算法的研究。網(wǎng)絡中少量的重要節(jié)點對網(wǎng)絡的影響超乎想象,例如信息通過重要節(jié)點能夠在很短的時間內(nèi)快速傳播到整個網(wǎng)絡,對社會網(wǎng)絡中少量的重要節(jié)點進行免疫能夠有效延緩甚至控制謠言或者病毒的傳播。有效發(fā)現(xiàn)網(wǎng)絡中的重要節(jié)點在諸多領域中都具有非常重要的意義,如政治、經(jīng)濟、生物、電力網(wǎng)、通信網(wǎng)絡等領域。本文針對重要節(jié)點發(fā)現(xiàn)算法的研究做了如下工作:1.針對現(xiàn)有傳統(tǒng)經(jīng)典的重要節(jié)點發(fā)現(xiàn)算法進行了研究,詳細介紹了度中心性,介數(shù)中心性,接近中心性,特征向量以及PageRank算法5種算法,并比較了各自的優(yōu)缺點。2.根據(jù)相連節(jié)點對之間的共同鄰居節(jié)點數(shù)目,提出了貢獻度概念來表征節(jié)點間的相互貢獻。在現(xiàn)實網(wǎng)絡中,節(jié)點與其鄰居節(jié)點的連接關系存在親疏之分,節(jié)點對與其連接親密的鄰居節(jié)點的貢獻度較大,這與傳統(tǒng)算法不同,更符合實際情況。本文通過K-Shell分解算法得到節(jié)點的自身屬性值,認為節(jié)點的重要度取決于節(jié)點自身屬性和鄰居節(jié)點對其影響,由此提出了KSC算法。3.針對真實的Zachary空手道網(wǎng)絡,海豚社會網(wǎng)絡以及計算機生成的ER隨機圖進行仿真。通過分析網(wǎng)絡的拓撲結構,觀察節(jié)點之間的連接情況,驗證本文KSC算法能夠有效發(fā)現(xiàn)網(wǎng)絡中的核心節(jié)點,尤其是發(fā)現(xiàn)社團中的核心節(jié)點很有效。4.編寫傳播仿真程序,采用SIR傳播模型,在單源傳播情況下,KSC算法表現(xiàn)較好。此外還進行重要節(jié)點免疫實驗仿真,實驗結果表明:免疫KSC算法發(fā)現(xiàn)的重要節(jié)點,能夠有效阻止惡意信息的傳播。
【關鍵詞】：復雜網(wǎng)絡 重要節(jié)點 貢獻度 KSC算法
【學位授予單位】：南京郵電大學
【學位級別】：碩士
【學位授予年份】：2015
【分類號】：O157.5
【目錄】：

• 摘要4-5
• Abstract5-8
• 專用術語注釋表8-10
• 第一章 緒論10-18
• 1.1 復雜網(wǎng)絡研究背景10-14
• 1.1.1 ER隨機圖模型12-13
• 1.1.2 WS小世界模型13
• 1.1.3 無標度網(wǎng)絡模型13-14
• 1.2 課題研究意義14-15
• 1.3 國內(nèi)外研究現(xiàn)狀15-17
• 1.4 本文內(nèi)容安排17-18
• 第二章 復雜網(wǎng)絡節(jié)點重要性評估指標研究18-30
• 2.1 圖的基本理論18-20
• 2.1.1 網(wǎng)絡的圖表示18-19
• 2.1.2 圖的計算機表示19-20
• 2.2 復雜網(wǎng)絡相關概念20-23
• 2.2.1 度與度分布20
• 2.2.2 平均路徑長度20-22
• 2.2.3 網(wǎng)絡直徑22
• 2.2.4 聚類系數(shù)22-23
• 2.2.5 社團結構23
• 2.3 幾種常見的重要節(jié)點評估指標23-29
• 2.3.1 度中心性24
• 2.3.2 介數(shù)中心性24-26
• 2.3.3 接近中心性26-27
• 2.3.4 特征向量中心性27-28
• 2.3.5 PageRank算法28-29
• 2.3.6 傳統(tǒng)重要節(jié)點發(fā)現(xiàn)算法對比29
• 2.4 本章小結29-30
• 第三章 基于K-Shell的重要節(jié)點發(fā)現(xiàn)算法30-39
• 3.1 K-Shell分解算法30-32
• 3.2 貢獻度引入32-35
• 3.2.1 無權無向網(wǎng)絡的貢獻度32-34
• 3.2.2 加權有向網(wǎng)絡的貢獻度34-35
• 3.3 KSC算法模型35-37
• 3.3.1 重要度貢獻矩陣35-37
• 3.3.2 KSC算法流程描述37
• 3.4 算法復雜度分析37-38
• 3.5 本章小結38-39
• 第四章 算法仿真與分析39-52
• 4.1 Zachary空手道網(wǎng)絡仿真分析39-43
• 4.1.1 K-Shell分解結果39-40
• 4.1.2 實驗結果與分析40-43
• 4.2 海豚社會網(wǎng)絡仿真分析43-48
• 4.2.1 K-Shell分解結果43-45
• 4.2.2 實驗結果與分析45-48
• 4.3 ER隨機網(wǎng)絡仿真分析48-51
• 4.3.1 K-Shell分解結果48-50
• 4.3.2 實驗結果與分析50-51
• 4.4 本章小結51-52
• 第五章 重要節(jié)點發(fā)現(xiàn)算法有效性研究52-61
• 5.1 傳播動力學模型評價排序算法52-56
• 5.1.1 經(jīng)典傳播模型52-53
• 5.1.2 單傳播源傳播仿真53-55
• 5.1.3 多傳播源傳播仿真55-56
• 5.2 重要節(jié)點免疫研究56-59
• 5.2.1 傳統(tǒng)免疫策略56-57
• 5.2.2 免疫重要節(jié)點傳播仿真57-59
• 5.3 本章小結59-61
• 第六章 總結與展望61-63
• 6.1 本文總結61-62
• 6.2 展望62-63
• 參考文獻63-66
• 附錄1 程序清單66-68
• 附錄2 攻讀碩士學位期間撰寫的論文68-69
• 致謝69

【參考文獻】

中國碩士學位論文全文數(shù)據(jù)庫 前1條

1 司曉靜;復雜網(wǎng)絡中節(jié)點重要性排序的研究[D];西安電子科技大學;2012年

，

本文編號：643943