基于成本效益的影響最大化算法分析與設計.pdf

1、隨著近些年互聯(lián)網(wǎng)的飛速發(fā)展，社交網(wǎng)絡應運而生，例如國外的Facebook、Twitter以及國內的人人網(wǎng)和新浪微博等等，這些在線社交網(wǎng)絡給人們提供了一種全新的社交模式，并且真實的反映了人們現(xiàn)實生活中的社會關系。同時依托社交網(wǎng)絡產生了一種全新的營銷模式——“病毒營銷”，它依靠人與人之間的口碑效應使信息在網(wǎng)絡中擴散，達到產品推廣的目的。針對這種特定的營銷模式，學術界也進行了許多研究，關注點在如何選擇最初的用戶作為信息源，通過口碑傳播使得被影

2、響的受眾最多，Domingos和Richardson首次把該問題形式化為一個算法問題引入到社會網(wǎng)絡領域進行研究，也即影響最大化問題。
　　然而對傳統(tǒng)影響最大化問題的研究在選擇初始信息源時忽略了用戶之間的差異性，沒有考慮到選擇用戶作為信息源所要花費的成本，而實際營銷中的推廣活動都有預算的約束，選擇不同的用戶需要不同的花費，如何在這樣的條件下獲得最好的推廣效果需要對問題重新考慮和定義?；谝陨峡紤]，本文給出了對用戶成本的定義方法，并提

3、出了基于成本效益的影響最大化問題。
　　針對這個問題，本文綜合考慮網(wǎng)絡拓撲和傳播模型的特點，提出了基于概率覆蓋范圍的啟發(fā)式算法(ProbCover Algorithm)，并在此基礎上利用子模函數(shù)特性和惰性計算技術提出基于概率覆蓋范圍的惰性節(jié)點選擇算法（ProbCoverLF Algorithm）。在本文研究成果的基礎上，設計實現(xiàn)了基于成本效益的影響最大化原型系統(tǒng)。
　　本文在三個數(shù)據(jù)集和獨立級聯(lián)模型上進行了實驗，并且分別采用