網(wǎng)絡影響力分析是復雜網(wǎng)絡研究的熱點內容,其包括節(jié)點影響力度量問題和影響力最大化問題,前者是評估網(wǎng)絡中各個節(jié)點的影響力,后者是評估網(wǎng)絡中節(jié)點集合整體的影響力,并從中選出傳播范圍最大的集合,這兩項研究對于生物信息和基因學、市場營銷、傳染病控制和網(wǎng)絡監(jiān)控等均具有重要的現(xiàn)實意義。本文結合節(jié)點影響力度量與影響力最大化的研究現(xiàn)狀及存在的問題,提出了一種新的影響力度量方法,并在此基礎上提出了三個影響力最大化算法,具體內容概括如下:首先,由于K-shell是一種粗粒度的度量方法,并且不能有效地識別處于關鍵樞紐位置的節(jié)點,為此本文提出了一種將K-shell方法和結構洞指標相融合的節(jié)點影響力度量方法KSSH。通過相關性和分辨率指標表明KSSH方法具有良好的準確度和區(qū)分度。其次,本文將KSSH方法引入到影響力最大化問題中,并討論了網(wǎng)絡中節(jié)點之間的影響力重疊效應。本文采用KSSH方法評估各個節(jié)點的影響力,并基于節(jié)點的聚類系數(shù)、節(jié)點的鄰居節(jié)點中被選為種子節(jié)點的個數(shù)、傳播概率以及節(jié)點的一階、二階鄰域提出了兩個削弱重疊影響力的影響力最大化算法KSSH_DisN與KSSH_Di... 

【文章來源】：蘭州大學甘肅省 211工程院校 985工程院校 教育部直屬院校

【文章頁數(shù)】：69 頁

【學位級別】：碩士

【部分圖文】：

航空網(wǎng)絡示意圖

蘭州大學碩士學位論文復雜網(wǎng)絡節(jié)點影響力度量與影響力最大化研究9第二章復雜網(wǎng)絡相關理論知識本章將詳細介紹復雜網(wǎng)絡研究必備的基礎理論及本文后面章節(jié)涉及到的相關知識，包括網(wǎng)絡的表示形式、網(wǎng)絡的基本拓撲性質、節(jié)點影響力度量的常用方法、影響力最大化問題的定義和常用算法、經典的傳播模型等。2.1網(wǎng)絡基礎理論概述2.1.1網(wǎng)絡的圖表示圖是復雜網(wǎng)絡的常用表示工具，它提供了一種用點和線來抽象地描述各種真實網(wǎng)絡的規(guī)范化方法。網(wǎng)絡可抽象為圖=(,)，其中是節(jié)點的集合，是連邊的集合，節(jié)點總數(shù)為=||，邊的總數(shù)為=||。除此之外，節(jié)點間的連邊分為不同的情況，即連邊是否有方向和是否具有表示連接強度的權值，并據(jù)此將圖分為四類：連邊無方向無權值的無向無權圖、連邊無方向有權值的無向有權圖、連邊有方向無權值的有向無權圖、連邊有方向有權值的有向有權圖。在圖論中，通常用來描述圖的結構有鄰接矩陣和鄰接表。圖的鄰接矩陣表示形式如下：圖的鄰接矩陣*()ijNNA=a是一個的方陣，若節(jié)點到節(jié)點之間存在有向連邊，則在該矩陣的第行第列填上1或者權值；若它們之間存在無向連邊，則在第行第列和第行第列分別填上1或者權值；若沒有連邊則填上0。實際上，大規(guī)模復雜網(wǎng)絡中節(jié)點之間的連邊一般是很稀疏的，這意味著與之對應的鄰接矩陣中大多數(shù)元素是0，用這種方式存儲稀疏圖既浪費了存儲空間又降低了利用率，故對于稀疏的無權圖，還有另外一種表示方式——鄰接表，它為每個節(jié)點創(chuàng)建一個單鏈表，鏈表中的元素即是與該節(jié)點直接相連的其他節(jié)點。圖2-1是一個圖表示的實例，其中最左邊是一個無向無權圖，中間是該圖的鄰接矩陣，最右邊是該圖的鄰接表。圖2-1圖表示的實例

蘭州大學碩士學位論文復雜網(wǎng)絡節(jié)點影響力度量與影響力最大化研究15出值是種子集合。算法1：GeneralGreedy算法Input：(,),Output:1.Initialize=2.for=1todo:3.select=argmaxv{(∪{})()|∈\}4.=∪{}5.endfor6.returnS（2）CELF算法GeneralGreedy算法在每次篩選種子節(jié)點時，都必須重新計算網(wǎng)絡中每個非種子節(jié)點能帶來的影響力收益，而每次計算節(jié)點的影響力收益時又需要進行大量的蒙特卡洛模擬實驗，這無疑大大增加了時間復雜度。Leskovec等人[48]利用影響力函數(shù)的子模性在GeneralGreedy算法的基礎上提出了CELF算法，它通過減少需要進行蒙特卡洛模擬的節(jié)點數(shù)量來降低算法的時間復雜度。圖2-2CELF算法的計算過程CELF算法的詳細過程如下：首先計算網(wǎng)絡中所有節(jié)點的影響力，將影響力最大的節(jié)點選為種子節(jié)點，在下次選取種子節(jié)點時，利用函數(shù)的子模性，只計算當前影響力增益最大的節(jié)點的新影響力增益，若比之前增益次大的節(jié)點的影響力增益值大，則將其加入到種子集合中，否則將重新計算所有非種子節(jié)點的影響力增益，重復上述過程直至選出個種子節(jié)點為止。圖2-2是CELF算法的一個計算實例，首先計算網(wǎng)絡中所有節(jié)點的影響力增益并按序存儲，此時增益最大的是節(jié)點A，將節(jié)點A加入種子集合，再進行第二輪種子節(jié)點選擇，計算當前增益最大的節(jié)點B的新影響力增益，若大于之前增益次大的節(jié)點C的增益10，則將B加入到種子集合中，不需要再計算節(jié)點C、D、E、F的影響力增益，這是因為影響力函數(shù)的子模性，這些節(jié)點在這一輪的新增益必定小于上一輪的增益，故直接


本文編號：3008940