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

【文章來(lái)源】：蘭州大學(xué)甘肅省 211工程院校 985工程院校 教育部直屬院校

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

【學(xué)位級(jí)別】：碩士

【部分圖文】：

一個(gè)無(wú)向無(wú)權(quán)網(wǎng)絡(luò)

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

30圖 3-4 各種算法在 12 個(gè)真實(shí)數(shù)據(jù)集上的影響力傳播范圍（IC 模型， = 0 01）不同算法在 12 個(gè)真實(shí)網(wǎng)絡(luò)上，在權(quán)重級(jí)聯(lián)模型下的影響力傳播范圍如圖 3-5 所示。同樣橫軸表示節(jié)點(diǎn)個(gè)數(shù)，縱軸表示傳播范圍，可以看出 SDDCELF 算法在 10 個(gè)網(wǎng)絡(luò)上和 CELF 取得幾乎一樣的精度�；谙嗨菩愿倪M(jìn)的算法 SPMD 選出的節(jié)點(diǎn)的傳播范圍總是比 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-


本文編號(hào)：3072137