本文關鍵詞：社會網(wǎng)絡中影響最大化問題的研究，由筆耕文化傳播整理發(fā)布。

【摘要】：社會網(wǎng)絡相關研究領域的一個關鍵問題就是影響最大化問題。影響最大化問題旨在通過算法發(fā)現(xiàn)社會網(wǎng)絡中最有影響力的節(jié)點集合,廣泛應用于市場營銷、廣告發(fā)布、輿情預警等場景,具有極高的研究意義和應用價值。由于影響最大化問題本身的NP-Hard復雜度,決定了這是一個優(yōu)化問題,尋找與最優(yōu)解有高近似比的快速求解算法和使算法實用化是主要的兩個研究方向。本文作者對影響最大化問題做了相關研究,提出了自己的算法,主要研究成果及貢獻如下:對多因素組合的影響最大化問題進行了研究。通過向傳統(tǒng)影響最大化問題加入地理位置約束和時間約束來解決現(xiàn)實生活中對某特定區(qū)域特定時間段最大化影響的問題。提出樸素的基于貪心的Multi Factor-Greedy算法和基于MIA模型的動態(tài)規(guī)劃TG-IM算法。通過一系列實驗證明,算法在保證運行時間復雜度不增高的情況下成功解決了多因素組合的影響最大化問題。對基于MapReduce模型的并行影響最大化問題做了研究。通過分析影響最大化問題的可并行性,發(fā)掘層次依賴關系,解耦合,提出了一種基于MapReduce的MP-IM算法,加速問題求解。實驗結果證明,該并行算法極大提升了影響力計算過程的效率,大大減少用戶得到種子集合S的等待時間且具有良好的可擴展性。將MapReduce模型應用于解決多因素組合的影響最大化問題。由于TG-IM算法不能直接用于并行計算,本文提出了應用新模型并行求解多因素組合影響最大化問題的MPTG-IM算法。通過實驗證明了算法的有效性和高效性,為解決可應用的影響最大化問題鋪平了道路。
【關鍵詞】：社會網(wǎng)絡 影響最大化 多因素 并行
【學位授予單位】：黑龍江大學
【學位級別】：碩士
【學位授予年份】：2016
【分類號】：TP393.09
【目錄】：

• 中文摘要4-5
• Abstract5-10
• 第1章 緒論10-21
• 1.1 社會網(wǎng)絡研究概述10-14
• 1.2 社會網(wǎng)絡影響最大化問題14-18
• 1.2.1 研究意義14-15
• 1.2.2 算法度量標準15-17
• 1.2.3 面臨的挑戰(zhàn)17-18
• 1.3 本文主要研究內(nèi)容18-19
• 1.4 本文的組織安排19-21
• 第2章 相關研究21-34
• 2.1 社會網(wǎng)絡影響最大化問題基本定義21-22
• 2.2 影響傳播模型22-25
• 2.2.1 獨立級聯(lián)模型22-23
• 2.2.2 線性閾值模型23-24
• 2.2.3 其它影響傳播模型24-25
• 2.3 影響最大化問題求解算法25-31
• 2.3.1 貪心算法25-28
• 2.3.2 啟發(fā)式算法28-31
• 2.4 影響最大化問題的延伸31-33
• 2.5 本章小結33-34
• 第3章 多因素組合的影響最大化算法34-51
• 3.1 引言34-36
• 3.2 算法設計36-42
• 3.2.1 問題定義36-37
• 3.2.2 MultiFactor-Greedy算法37-39
• 3.2.3 TG-IM算法39-42
• 3.3 實驗與分析42-50
• 3.3.1 實驗設置42-43
• 3.3.2 算法精度分析43-45
• 3.3.3 算法時間分析45-47
• 3.3.4 參數(shù)評估47-50
• 3.4 本章小結50-51
• 第4章 基于MapReduce模型的并行影響最大化算法51-64
• 4.1 背景理論51-54
• 4.1.1 影響最大化問題的并行性51-52
• 4.1.2 MapReduce模型和相關框架52-54
• 4.2 算法設計54-60
• 4.2.1 問題定義54-56
• 4.2.2 MP-IM算法56-60
• 4.3 實驗與分析60-63
• 4.3.1 實驗設置60-61
• 4.3.2 算法精度分析61-62
• 4.3.3 算法時間分析62-63
• 4.4 本章小結63-64
• 第5章 并行的多因素組合影響最大化算法64-71
• 5.1 引言64-65
• 5.2 算法設計65-67
• 5.2.1 問題定義65
• 5.2.2 MPTG-IM算法65-67
• 5.3 實驗與分析67-70
• 5.3.1 實驗設置67
• 5.3.2 實驗結果67-70
• 5.4 本章小結70-71
• 結論71-72
• 參考文獻72-79
• 致謝79

【相似文獻】

中國碩士學位論文全文數(shù)據(jù)庫 前7條

1 張巍;基于社會網(wǎng)的影響傳播技術研究[D];黑龍江大學;2015年

2 陳雪峰;網(wǎng)絡中影響力傳播的最大化[D];電子科技大學;2015年

3 耿靈;基于EPC網(wǎng)絡的社會影響力最大化問題[D];上海交通大學;2015年

4 尚興;社會網(wǎng)絡中影響力最大化問題的研究[D];南京大學;2013年

5 呂文淵;面向主題耦合的影響力最大化研究[D];云南大學;2016年

6 楊智博;社會網(wǎng)絡中影響最大化問題的研究[D];黑龍江大學;2016年

7 楊鴻超;社會網(wǎng)絡營銷中基于成本控制的影響最大化問題研究[D];南京大學;2013年

  本文關鍵詞：社會網(wǎng)絡中影響最大化問題的研究，由筆耕文化傳播整理發(fā)布。

，

本文編號：471707