隨著信息技術的飛速發(fā)展,各種社交平臺不斷涌現(xiàn),人與人之間的交互形成規(guī)模龐大,結(jié)構復雜的社交網(wǎng)絡。分析網(wǎng)絡結(jié)構,研究網(wǎng)絡的信息傳播機制,對于輿論控制、病毒式營銷、傳染病控制等都具有重要的理論意義和實用價值,其中影響力最大化就是一個重要的研究方向。影響力最大化問題就是在一個網(wǎng)絡中尋找部分種子節(jié)點作為信息傳播源,使得這些種子節(jié)點組合在一起的影響力傳播范圍最大,即信息在網(wǎng)絡中的傳播范圍最廣。最近十幾年,針對該問題,雖然已經(jīng)有很多的研究工作發(fā)表,但是當前的算法在處理大規(guī)模網(wǎng)絡時依然難以同時滿足精確性、時間效率和空間效率的要求。本文將從以下幾個方面來研究精確、有效的影響力最大化算法:首先,基于一階鄰居提出相似性框架,用來解決種子節(jié)點之間的影響力覆蓋問題。通過將提出的相似性框架應用到兩個現(xiàn)有的算法,度剪枝和基于傳播路徑的PMD算法,證明所提出來的相似性框架能夠有效提高啟發(fā)式算法的精度。其次,提出兩階段的框架來提高現(xiàn)有貪心算法的時間效率。該框架首先利用提出的改進度剪枝算法選出候選種子節(jié)點,縮小種子節(jié)點的選擇范圍,然后利用現(xiàn)有的貪心算法從候選節(jié)點中選出種子節(jié)點。然后,提出反向隨機游走的策略來評估節(jié)點的重... 

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

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

【學位級別】：碩士

【部分圖文】：

一個無向無權網(wǎng)絡

圖 3-3 不同相似性閾值下影響力的傳播范圍圖 3-3 展示了 SDD(SSD)和 SPMD 算法在不同相似性閾值下的影響力傳播范圍。橫坐標表示相似性閾值，變化范圍從 0.1 到 1.0，縱坐標表示選擇 50 個種子節(jié)點的影響力傳播范圍。從圖 3-3 的六個圖中可以看出，在大多數(shù)情況下當 的值從 0.1 到 0.9 變化，無論是在獨立級聯(lián)模型還是在權重級聯(lián)模型，影響力的傳播范圍都是逐漸增加，這表明當 取 0.9 的時候 SDD(SSD)和 SPMD 能取得最優(yōu)的傳播范圍。3.4.2 不同算法的影響力傳播范圍對比圖 3-4 展示了不同算法在獨立級聯(lián)模型，傳播概率為 0.01 的情況下在 12 個真實數(shù)據(jù)集上選出 50 個種子節(jié)點的影響力傳播范圍。橫軸表示種子節(jié)點的個數(shù)從 1 到 50，縱軸表示影響力傳播范圍，即最終激活的節(jié)點數(shù)量。為了對比公平，影響力傳播范圍都是通過 10000 次的蒙特卡洛模擬計算的，下文所有涉及影響力傳播范圍的不同百分比都是在 = 50情況下計算的。

30圖 3-4 各種算法在 12 個真實數(shù)據(jù)集上的影響力傳播范圍（IC 模型， = 0 01）不同算法在 12 個真實網(wǎng)絡上，在權重級聯(lián)模型下的影響力傳播范圍如圖 3-5 所示。同樣橫軸表示節(jié)點個數(shù)，縱軸表示傳播范圍，可以看出 SDDCELF 算法在 10 個網(wǎng)絡上和 CELF 取得幾乎一樣的精度�；谙嗨菩愿倪M的算法 SPMD 選出的節(jié)點的傳播范圍總是比 PMD 高，例如在 astro-ph、ca-AstroPh、email-EuAll、facebook、soc-Epinions、Wiki-vote 上分別高出 28.6%、35.6%、64%、36.3%、53.3%、22%。提出的 SSD 算法總是比 SD 在精確度上高或者相同，例如在 astro-ph、com-


本文編號：3072137