基于成本效益的影響最大化算法分析與設(shè)計(jì).pdf

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

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

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