本文關(guān)鍵詞：基于群體智能優(yōu)化的社會(huì)網(wǎng)絡(luò)影響最大化研究

  更多相關(guān)文章： 影響最大化 群體智能優(yōu)化 粒子群優(yōu)化 進(jìn)化算法 社會(huì)網(wǎng)絡(luò)分析

【摘要】：隨著各種在線社交平臺(tái)的蓬勃發(fā)展,它們已經(jīng)逐漸成為社會(huì)成員進(jìn)行信息分享和傳播的重要媒介。近年來(lái),越來(lái)越多的企業(yè)和商家選擇了各種線上社交網(wǎng)絡(luò)進(jìn)行產(chǎn)品和服務(wù)的推廣,而這種利用社會(huì)關(guān)系進(jìn)行“口口相傳”的營(yíng)銷方式往往能夠以較低的成本而帶來(lái)巨大的利潤(rùn)。影響最大化問(wèn)題旨在挖掘出社會(huì)網(wǎng)絡(luò)中具有影響力的群體作為信息源,通過(guò)它們的影響力使得網(wǎng)絡(luò)中的信息達(dá)到最大范圍的傳播。影響最大化是社會(huì)網(wǎng)絡(luò)中信息傳播研究領(lǐng)域的核心問(wèn)題,它具有廣泛的應(yīng)用場(chǎng)景,比如廣告投放、市場(chǎng)營(yíng)銷、水質(zhì)監(jiān)測(cè)和輿情控制等,因此具有重要的研究?jī)r(jià)值和社會(huì)意義。在影響最大化問(wèn)題中,節(jié)點(diǎn)組合的選擇策略對(duì)應(yīng)的準(zhǔn)確度和運(yùn)行效率是需要考慮的兩個(gè)重要問(wèn)題,如何從社會(huì)網(wǎng)絡(luò)中高效地挖掘出目標(biāo)組合是解決影響最大化問(wèn)題的首要目標(biāo)。在已有的解決影響最大化問(wèn)題的算法中,貪婪算法具有較高的準(zhǔn)確率,但是其運(yùn)行效率較為低下,不能被用于求解大規(guī)模社會(huì)網(wǎng)絡(luò)的影響最大化問(wèn)題。相反,一些啟發(fā)式的方法具有很高的運(yùn)行效率,然而這些算法往往存在準(zhǔn)確率不高、算法不穩(wěn)定等問(wèn)題。針對(duì)上述影響最大化研究中存在的問(wèn)題,本文從以下幾個(gè)方面對(duì)社會(huì)網(wǎng)絡(luò)影響最大化問(wèn)題進(jìn)行了研究:在社會(huì)網(wǎng)絡(luò)中計(jì)算節(jié)點(diǎn)或者節(jié)點(diǎn)集合的影響傳播范圍被證明是一種#P難(sharp-P hard)問(wèn)題,傳統(tǒng)的影響最大化算法均采用計(jì)算復(fù)雜度極高的蒙特卡洛模擬來(lái)獲得。本文通過(guò)深入分析社會(huì)網(wǎng)絡(luò)的傳播特性,針對(duì)獨(dú)立級(jí)聯(lián)模型和權(quán)重級(jí)聯(lián)模型構(gòu)造了一種局部影響力評(píng)估方程來(lái)近似計(jì)算節(jié)點(diǎn)的影響傳播范圍。在此基礎(chǔ)上,我們將社會(huì)網(wǎng)絡(luò)影響最大化問(wèn)題建模為一種目標(biāo)函數(shù)的優(yōu)化問(wèn)題,并提出了一種基于離散形式的粒子群優(yōu)化算法。在提出的算法中,我們針對(duì)問(wèn)題的特性設(shè)計(jì)了基于度中心性的初始化方法和基于鄰域的局部搜索算子,從而在很大程度上加速了算法的收斂,提高了算法的運(yùn)行效率。此外,我們針對(duì)之前影響最大化的研究中沒(méi)有考慮節(jié)點(diǎn)選擇代價(jià)的問(wèn)題,通過(guò)引入節(jié)點(diǎn)選擇代價(jià)的概念提出了一種預(yù)算影響最大化模型。為了能以較低的選擇代價(jià)來(lái)達(dá)到社會(huì)網(wǎng)絡(luò)的影響最大化,我們將預(yù)算影響最大化問(wèn)題作為一種多目標(biāo)優(yōu)化問(wèn)題來(lái)解決,并提出了一種進(jìn)化多目標(biāo)優(yōu)化算法。實(shí)驗(yàn)證明,該算法所選的初始激活節(jié)點(diǎn)集合在保持最大影響范圍的同時(shí),還具有較低的選擇代價(jià)。
【關(guān)鍵詞】：影響最大化 群體智能優(yōu)化 粒子群優(yōu)化 進(jìn)化算法 社會(huì)網(wǎng)絡(luò)分析
【學(xué)位授予單位】：西安電子科技大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2015
【分類號(hào)】：TP18;TP393.09
【目錄】：

• 摘要5-6
• ABSTRACT6-10
• 符號(hào)對(duì)照表10-11
• 縮略語(yǔ)對(duì)照表11-14
• 第一章 緒論14-20
• 1.1 研究背景和意義14-15
• 1.2 國(guó)內(nèi)外研究現(xiàn)狀15-16
• 1.3 本文主要的研究?jī)?nèi)容16-17
• 1.4 本文章節(jié)安排17-20
• 第二章 影響最大化相關(guān)概念及算法20-34
• 2.1 社會(huì)網(wǎng)絡(luò)20-23
• 2.1.1 社會(huì)網(wǎng)絡(luò)的基本概念和表示20-21
• 2.1.2 社會(huì)網(wǎng)絡(luò)的特性21-23
• 2.2 信息傳播模型23-26
• 2.2.1 獨(dú)立級(jí)聯(lián)模型24
• 2.2.2 權(quán)重級(jí)聯(lián)模型24-25
• 2.2.3 線性閾值模型25-26
• 2.3 影響最大化問(wèn)題26
• 2.4 影響最大化相關(guān)算法26-33
• 2.4.1 基于網(wǎng)絡(luò)特性的啟發(fā)式方法26-29
• 2.4.2 貪婪方法及其改進(jìn)方法29-31
• 2.4.3 基于目標(biāo)函數(shù)優(yōu)化的方法31-33
• 2.5 本章小結(jié)33-34
• 第三章 基于離散粒子群優(yōu)化的影響最大化算法34-54
• 3.1 引言34
• 3.2 粒子群優(yōu)化34-36
• 3.3 基于離散粒子群優(yōu)化的影響最大化算法36-42
• 3.3.1 算法框架36
• 3.3.2 編碼方式36-37
• 3.3.3 目標(biāo)函數(shù)37-38
• 3.3.4 基于度中心性的啟發(fā)式初始化方法38-39
• 3.3.5 位置和速度迭代算子39-41
• 3.3.6 局部搜索算子41-42
• 3.3.7 算法時(shí)間復(fù)雜度分析42
• 3.4 實(shí)驗(yàn)分析42-52
• 3.4.1 實(shí)驗(yàn)設(shè)置42-43
• 3.4.2 人工網(wǎng)絡(luò)實(shí)驗(yàn)43-45
• 3.4.3 真實(shí)網(wǎng)絡(luò)實(shí)驗(yàn)45-51
• 3.4.4 算法參數(shù)影響分析51-52
• 3.5 本章小結(jié)52-54
• 第四章 基于進(jìn)化多目標(biāo)優(yōu)化的預(yù)算影響最大化算法54-66
• 4.1 引言54
• 4.2 進(jìn)化多目標(biāo)優(yōu)化54-56
• 4.2.1 多目標(biāo)優(yōu)化的相關(guān)概念54-55
• 4.2.2 進(jìn)化多目標(biāo)優(yōu)化算法55-56
• 4.3 預(yù)算影響最大化問(wèn)題56-57
• 4.4 基于進(jìn)化多目標(biāo)優(yōu)化的預(yù)算影響最大化算法57-60
• 4.4.1 算法框架57
• 4.4.2 編碼方式和種群初始化57-58
• 4.4.3 非支配排序、擁擠度距離計(jì)算與個(gè)體選擇58-59
• 4.4.4 交叉和變異算子59-60
• 4.4.5 算法時(shí)間復(fù)雜度分析60
• 4.5 實(shí)驗(yàn)分析60-64
• 4.5.1 實(shí)驗(yàn)設(shè)置61
• 4.5.2 實(shí)驗(yàn)結(jié)果評(píng)價(jià)指標(biāo)61
• 4.5.3 實(shí)驗(yàn)結(jié)果分析61-64
• 4.6 本章小結(jié)64-66
• 第五章 總結(jié)與展望66-68
• 5.1 總結(jié)66-67
• 5.2 展望67-68
• 參考文獻(xiàn)68-74
• 致謝74-76
• 作者簡(jiǎn)介76-77

【參考文獻(xiàn)】

中國(guó)期刊全文數(shù)據(jù)庫(kù) 前1條

1 俞靚亮;王萬(wàn)良;介婧;;基于混合粒子群優(yōu)化算法的旅行商問(wèn)題求解[J];計(jì)算機(jī)工程;2010年11期

，

本文編號(hào)：1119370