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

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

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

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

【部分圖文】：

加權(quán)有向圖

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

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


本文編號(hào)：3370233