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

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

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

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