社交網(wǎng)絡(luò)中的影響最大化問題研究.pdf

1、近年來，隨著互聯(lián)網(wǎng)和 Web2.0技術(shù)的不斷完善，各種社交網(wǎng)絡(luò)服務(wù)層出不窮，人們越來越習(xí)慣于在在線社交網(wǎng)絡(luò)平臺上進行互動交流和信息發(fā)布。社交網(wǎng)絡(luò)因此成為人類知識共享、交互溝通和信息傳播的重要媒介和平臺。影響最大化問題是社交網(wǎng)絡(luò)領(lǐng)域的關(guān)鍵問題之一，輿情監(jiān)測中的源頭尋找，市場營銷中代理商的選擇以及水質(zhì)監(jiān)測中的定位等都是影響最大化問題實際應(yīng)用的展現(xiàn)。影響最大化問題旨在尋找最具影響力的種子節(jié)點集合，如何尋找這個集合已被證明是 NP-Hard。目

2、前已有的用來解決影響最大化問題的方法主要集中于貪心算法、啟發(fā)式算法和社區(qū)算法。但在大規(guī)模網(wǎng)絡(luò)的求解背景中，其存在時間復(fù)雜度高、影響精度低以及魯棒性差的問題。因此尋求一種高效的方法來解決大規(guī)模網(wǎng)絡(luò)中的影響最大化問題是目前很有意義的研究課題。
　　針對以上問題，本文在研究網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)、影響傳播模型、影響最大化算法以及節(jié)點影響力評估方法等關(guān)鍵問題的基礎(chǔ)上，主要取得了以下成果：
　　(1)本文基于線性閾值模型能夠?qū)⒂绊懥鄯e的特性

3、，提出一種以度和影響力作為啟發(fā)策略的混合啟發(fā)式算法—DIH算法。該算法將影響最大化問題的求解過程分為度折啟發(fā)和影響力啟發(fā)這兩個階段進行處理。第一階段進行度折啟發(fā)，快速的找到網(wǎng)絡(luò)中處于中心地位的節(jié)點并將其影響力傳播開來，為第二階段積累影響力；第二階段進行影響力啟發(fā)，在尋找影響力最大的節(jié)點過程中將第一階段積累的影響力收集并爆發(fā)，從而激活更多的節(jié)點。
　　(2)為了提高算法的效率，本文根據(jù)節(jié)點之間的影響力隨著距離增大而減小的理論以及三度