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

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

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

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