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

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

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

• 摘要5-6
• ABSTRACT6-10
• 符號對照表10-11
• 縮略語對照表11-14
• 第一章 緒論14-20
• 1.1 研究背景和意義14-15
• 1.2 國內(nèi)外研究現(xiàn)狀15-16
• 1.3 本文主要的研究內(nèi)容16-17
• 1.4 本文章節(jié)安排17-20
• 第二章 影響最大化相關(guān)概念及算法20-34
• 2.1 社會網(wǎng)絡(luò)20-23
• 2.1.1 社會網(wǎng)絡(luò)的基本概念和表示20-21
• 2.1.2 社會網(wǎng)絡(luò)的特性21-23
• 2.2 信息傳播模型23-26
• 2.2.1 獨立級聯(lián)模型24
• 2.2.2 權(quán)重級聯(lián)模型24-25
• 2.2.3 線性閾值模型25-26
• 2.3 影響最大化問題26
• 2.4 影響最大化相關(guān)算法26-33
• 2.4.1 基于網(wǎng)絡(luò)特性的啟發(fā)式方法26-29
• 2.4.2 貪婪方法及其改進方法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 算法時間復(fù)雜度分析42
• 3.4 實驗分析42-52
• 3.4.1 實驗設(shè)置42-43
• 3.4.2 人工網(wǎng)絡(luò)實驗43-45
• 3.4.3 真實網(wǎng)絡(luò)實驗45-51
• 3.4.4 算法參數(shù)影響分析51-52
• 3.5 本章小結(jié)52-54
• 第四章 基于進化多目標(biāo)優(yōu)化的預(yù)算影響最大化算法54-66
• 4.1 引言54
• 4.2 進化多目標(biāo)優(yōu)化54-56
• 4.2.1 多目標(biāo)優(yōu)化的相關(guān)概念54-55
• 4.2.2 進化多目標(biāo)優(yōu)化算法55-56
• 4.3 預(yù)算影響最大化問題56-57
• 4.4 基于進化多目標(biāo)優(yōu)化的預(yù)算影響最大化算法57-60
• 4.4.1 算法框架57
• 4.4.2 編碼方式和種群初始化57-58
• 4.4.3 非支配排序、擁擠度距離計算與個體選擇58-59
• 4.4.4 交叉和變異算子59-60
• 4.4.5 算法時間復(fù)雜度分析60
• 4.5 實驗分析60-64
• 4.5.1 實驗設(shè)置61
• 4.5.2 實驗結(jié)果評價指標(biāo)61
• 4.5.3 實驗結(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
• 作者簡介76-77

【參考文獻(xiàn)】

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

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

，

本文編號：1119370