本文關鍵詞：基于成本效益的影響最大化算法分析與設計

  更多相關文章： 社交網絡 影響最大化 成本效益 概率覆蓋范圍 子模函數特性

【摘要】：隨著近些年互聯網的飛速發(fā)展,社交網絡應運而生,例如國外的Facebook、Twitter以及國內的人人網和新浪微博等等,這些在線社交網絡給人們提供了一種全新的社交模式,并且真實的反映了人們現實生活中的社會關系。同時依托社交網絡產生了一種全新的營銷模式——“病毒營銷”,它依靠人與人之間的口碑效應使信息在網絡中擴散,達到產品推廣的目的。針對這種特定的營銷模式,學術界也進行了許多研究,關注點在如何選擇最初的用戶作為信息源,通過口碑傳播使得被影響的受眾最多,Domingos和Richardson首次把該問題形式化為一個算法問題引入到社會網絡領域進行研究,也即影響最大化問題。然而對傳統(tǒng)影響最大化問題的研究在選擇初始信息源時忽略了用戶之間的差異性,沒有考慮到選擇用戶作為信息源所要花費的成本,而實際營銷中的推廣活動都有預算的約束,選擇不同的用戶需要不同的花費,如何在這樣的條件下獲得最好的推廣效果需要對問題重新考慮和定義�；谝陨峡紤],本文給出了對用戶成本的定義方法,并提出了基于成本效益的影響最大化問題。針對這個問題,本文綜合考慮網絡拓撲和傳播模型的特點,提出了基于概率覆蓋范圍的啟發(fā)式算法(ProbCover Algorithm),并在此基礎上利用子模函數特性和惰性計算技術提出基于概率覆蓋范圍的惰性節(jié)點選擇算法(ProbCoverLF Algorithm)。在本文研究成果的基礎上,設計實現了基于成本效益的影響最大化原型系統(tǒng)。本文在三個數據集和獨立級聯模型上進行了實驗,并且分別采用了固定概率和變概率兩種方式的獨立級聯模型,實驗結果表明：(a)在影響范圍方面,本文所提出的算法優(yōu)于傳統(tǒng)的啟發(fā)式算法,并且在變概率條件下的獨立級聯模型中優(yōu)勢尤其明顯；(b)在時間效率方面,本文所提出的算法雖然運行時間比傳統(tǒng)的啟發(fā)式算法要長,但仍在可以接受的范圍之內。綜合影響范圍和時間效率兩方面,證明了本文算法的有效性。
【關鍵詞】：社交網絡 影響最大化 成本效益 概率覆蓋范圍 子模函數特性
【學位授予單位】：東南大學
【學位級別】：碩士
【學位授予年份】：2015
【分類號】：TP301.6;TP393.09
【目錄】：

• 摘要4-5
• ABSTRACT5-8
• 第一章 緒論8-17
• 1.1 研究背景與意義8-9
• 1.2 國內外研究現狀9-14
• 1.2.1 原始影響最大化問題研究現狀10-12
• 1.2.2 基于成本效益的影響最大化問題研究現狀12-13
• 1.2.3 現狀總結13-14
• 1.3 研究目標及內容14-15
• 1.4 論文組織結構15-17
• 第二章 相關理論知識17-23
• 2.1 社會網絡17-18
• 2.2 影響力傳播模型18-20
• 2.2.1 獨立級聯模型18-19
• 2.2.2 線性閾值模型19-20
• 2.2.3 其他傳播模型20
• 2.3 基于成本效益的影響最大化問題20-22
• 2.3.1 形式化定義20-21
• 2.3.2 評價指標21
• 2.3.3 問題難度21-22
• 2.4 本章小結22-23
• 第三章 概率覆蓋算法23-31
• 3.1 節(jié)點成本建模23-26
• 3.1.1 成本的意義23-24
• 3.1.2 成本的定義24-26
• 3.2 節(jié)點概率覆蓋范圍26-29
• 3.2.1 節(jié)點影響力分析26-27
• 3.2.2 算法思想27
• 3.2.3 算法描述27-29
• 3.3 選擇初始節(jié)點集合29-30
• 3.4 本章小結30-31
• 第四章 利用子模函數特性的惰性節(jié)點選擇算法31-36
• 4.1 子模函數特性31-32
• 4.2 惰性節(jié)點選擇算法32-35
• 4.3 本章小結35-36
• 第五章 實驗設計與分析36-48
• 5.1 實驗環(huán)境36
• 5.2 實驗數據集36-38
• 5.3 實驗設計38-39
• 5.4 實驗結果及分析39-47
• 5.4.1 固定概率的IC模型實驗結果與分析40-45
• 5.4.2 變概率下的IC模型實驗結果與分析45-47
• 5.4.3 實驗結果小結47
• 5.5 本章小結47-48
• 第六章 系統(tǒng)實現48-54
• 6.1 原型系統(tǒng)整體架構48-49
• 6.2 原型系統(tǒng)實現49-53
• 6.2.1 開發(fā)環(huán)境49
• 6.2.2 系統(tǒng)實現49-53
• 6.3 本章小結53-54
• 第七章 總結與展望54-56
• 7.1 工作總結54
• 7.2 研究展望54-56
• 致謝56-57
• 參考文獻57-60
• 作者簡介60

【相似文獻】

中國碩士學位論文全文數據庫 前1條

1 趙釗;基于成本效益的影響最大化算法分析與設計[D];東南大學;2015年

，

本文編號：740016