圖上影響最大化問題算法分析實(shí)踐.pdf

1、隨著21世紀(jì)互聯(lián)網(wǎng)時(shí)代和大數(shù)據(jù)時(shí)代的到來，信息傳播的速度和廣度達(dá)到了前所未有的高峰。在互聯(lián)網(wǎng)諸多實(shí)例應(yīng)用中，社交網(wǎng)絡(luò)(social network)及如何利用社交網(wǎng)絡(luò)進(jìn)行網(wǎng)絡(luò)營(yíng)銷(social network marketing)成為了學(xué)術(shù)界研究的熱門話題。
　　網(wǎng)絡(luò)營(yíng)銷的常見問題是，如何定義營(yíng)銷影響的范圍，以及如何選取目標(biāo)受眾達(dá)到營(yíng)銷影響的最大化。在一個(gè)聯(lián)系緊密的人群關(guān)系中，社交網(wǎng)絡(luò)可以看作一種用圖關(guān)系表示的結(jié)構(gòu)，其中每個(gè)個(gè)體作

2、為圖上節(jié)點(diǎn)，個(gè)體之間的相互關(guān)系和影響作為圖上邊的權(quán)重。這樣就得到了人群關(guān)系的社交網(wǎng)絡(luò)。
　　利用社交網(wǎng)絡(luò)的圖關(guān)系，可以設(shè)計(jì)相應(yīng)的算法試圖使網(wǎng)絡(luò)營(yíng)銷在圖上影響達(dá)到最大化。經(jīng)典的算法如CELF Greedy，MIA和DegreeDiscount在這一領(lǐng)域中有成熟的發(fā)展，又各自具有自身的特點(diǎn)和優(yōu)勢(shì)。
　　本文對(duì)以上算法及互聯(lián)網(wǎng)網(wǎng)絡(luò)分析的其他常用算法(PageRank，HITS)進(jìn)行了實(shí)現(xiàn)，利用真實(shí)數(shù)據(jù)進(jìn)行模擬，探討在某一特定社交網(wǎng)

3、絡(luò)中達(dá)到影響最大化的最佳策略。通過比較，得出結(jié)論為CELF Greedy算法能夠得到穩(wěn)定的輸出結(jié)果，而MIA，DegreeDiscount等啟發(fā)性算法對(duì)參數(shù)的依賴性較強(qiáng)，需要多次調(diào)整輸入?yún)?shù)才能達(dá)到較優(yōu)良的性能。
　　作者作為某實(shí)際項(xiàng)目的算法設(shè)計(jì)負(fù)責(zé)人，將本文介紹的理論和算法在實(shí)際項(xiàng)目中進(jìn)行了實(shí)踐應(yīng)用。
　　作為本文貢獻(xiàn)的一部分，在文中提出了對(duì)“圖上影響最大化”問題進(jìn)行評(píng)價(jià)的新方法，這種改進(jìn)的方法可以有效縮短現(xiàn)有算法的運(yùn)行時(shí)