影響最大化問題是社交網(wǎng)絡和病毒傳播領域的經(jīng)典傳播優(yōu)化問題。它旨在從給定網(wǎng)絡中尋找k個最優(yōu)節(jié)點作為傳播的初始點集合,使得傳播結(jié)束后被影響的節(jié)點最多。影響最大化問題的實際應用廣泛,如新產(chǎn)品或新理念的有效推廣、病毒或災害的有效控制、輿情預警以及社會安定的綜合管理等。為了能更好地處理大型網(wǎng)絡中的影響最大化問題,目前對該問題的研究主要集中在如何保證選取的節(jié)點集合不減少影響范圍的前提下,盡可能提高選擇種子節(jié)點的時間效率。針對目前具有線性時間復雜度的影響最大化算法還很少的現(xiàn)狀,本文提出了兩個具有線性時間復雜度的影響最大化模型:（1）基于多層鄰居潛力和社區(qū)結(jié)構(gòu)的線性時間復雜度模型和（2）基于節(jié)點鄰域和迭代尋優(yōu)的線性時間復雜度模型。基于多層鄰居潛力和社區(qū)結(jié)構(gòu)的線性時間復雜度模型充分利用了社區(qū)間連接稀疏,社區(qū)內(nèi)連接緊密的特性,并假設后續(xù)被激活節(jié)點的影響力被限制在其社區(qū)內(nèi)部。該模型假設傳播分為兩個階段:第一階段為傳播初期種子,節(jié)點在不同社區(qū)間的擴張,即允許跨社區(qū)傳播;第二階段為已激活節(jié)點在社區(qū)內(nèi)部的獨立傳播,即不同社區(qū)間不再相互傳播。基于上述假設,本文推導出具有次模特性的目標函數(shù)并給出了具有線性時間復雜度的... 

【文章來源】：重慶大學重慶市 211工程院校 985工程院校 教育部直屬院校

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

【學位級別】：碩士

【部分圖文】：

加權(quán)有向圖

學位論文 一定存在邊j iu u。無權(quán)意味著邊的權(quán)值都相等，通常假，例圖 2.4無向圖向圖，由于是無向圖，所以邊是沒有方向的，即是對稱的以邊的權(quán)值都相等，例圖 2.5。

10圖 2.4 無權(quán)有向圖Fig. 2.4 Unweighted directed graph這幾種類型的圖，我們也可以得到加權(quán)有向圖、加權(quán)無向圖間的相互轉(zhuǎn)化關系，如圖 2.6。加權(quán)有向圖其實化處理得到，加權(quán)無向圖是由加權(quán)有向圖邊的對稱化


本文編號：3370233