社交網(wǎng)絡(luò)中的信息傳播算法研究.pdf

1、隨著網(wǎng)絡(luò)以及社交網(wǎng)站的快速發(fā)展，例如Facebook和Twitter，社交網(wǎng)絡(luò)已經(jīng)成為人們獲取信息和擴(kuò)散信息的主要平臺(tái)之一。在社交網(wǎng)絡(luò)中，利用社交網(wǎng)絡(luò)的信息擴(kuò)散的特性（如快捷，范圍廣，影響力大等），可以有效的幫助企業(yè)進(jìn)行產(chǎn)品推銷，幫助政府進(jìn)行謠言阻塞等等。在企業(yè)的產(chǎn)品宣傳中，選擇盡量少的關(guān)鍵性用戶去擴(kuò)散消息，不僅可以有效快捷的宣傳產(chǎn)品，還能降低企業(yè)成本，提高產(chǎn)品最終帶來的利潤?；诖它c(diǎn)，本文綜合考慮消息擴(kuò)散所需要的代價(jià)以及消息擴(kuò)散范圍問

2、題。
　　本文主要考慮解決兩個(gè)問題：影響力最大化問題和最小代價(jià)的信息傳播問題。其中最小代價(jià)的信息傳播問題是在影響力最大化問題的基礎(chǔ)上結(jié)合現(xiàn)實(shí)情況進(jìn)行調(diào)研后提出的。在最小代價(jià)的信息傳播問題中，本文提出代價(jià)函數(shù)的概念，代價(jià)具體包含以下兩個(gè)方面的內(nèi)涵：一方面代價(jià)指種子結(jié)點(diǎn)集合中結(jié)點(diǎn)的個(gè)數(shù)，即給定相同的信息擴(kuò)散范圍，選擇作為種子結(jié)點(diǎn)的結(jié)點(diǎn)個(gè)數(shù)最少；另一方面代價(jià)指種子結(jié)點(diǎn)集合所需要的花費(fèi)成本，即給定相同的消息擴(kuò)散范圍的前提下，總的代價(jià)最小，

3、即種子結(jié)點(diǎn)集合需要花費(fèi)的成本最少。針對(duì)代價(jià)的不同內(nèi)涵，本文中考慮了兩種不同代價(jià)函數(shù)的情況。
　　針對(duì)影響力最大化問題，本文歸納總結(jié)了現(xiàn)有的影響力最大化算法，提出基于HISS方法的影響力最大化算法（HISS-IM），其特征在于種子結(jié)點(diǎn)集合中的每個(gè)結(jié)點(diǎn)與其他結(jié)點(diǎn)的最短距離至少是h+1跳，這樣可以避免種子結(jié)點(diǎn)間的影響力重疊，從而使得在相同的信息擴(kuò)散范圍下，需要的種子結(jié)點(diǎn)個(gè)數(shù)更少。
　　針對(duì)最小代價(jià)的信息傳播問題，本文首先提出基于H

4、ISS的最小代價(jià)的結(jié)點(diǎn)選擇算法（HISS-MCID），結(jié)合結(jié)點(diǎn)的權(quán)重和代價(jià)信息選取出候選種子結(jié)點(diǎn)集合，然后提出一個(gè)評(píng)估函數(shù)預(yù)估種子結(jié)點(diǎn)集合的影響范圍選取出種子結(jié)點(diǎn)集合。本文接著設(shè)計(jì)基于信息傳播模型的結(jié)點(diǎn)選擇算法（IPMA），在選取結(jié)點(diǎn)的過程中，考慮結(jié)點(diǎn)的代價(jià)，并且基于信息傳播模型來選取種子結(jié)點(diǎn)。本文還利用社交網(wǎng)絡(luò)中的中心性指標(biāo)思想，提出性價(jià)比的概念，設(shè)計(jì)基于性價(jià)比排序的結(jié)點(diǎn)選擇算法（HRA），即在選取結(jié)點(diǎn)的過程中，優(yōu)先選擇性價(jià)比高的結(jié)點(diǎn)

5、。
　　最后，本文利用現(xiàn)實(shí)中的公開數(shù)據(jù)集，分別在數(shù)據(jù)集上采用獨(dú)立級(jí)聯(lián)模型和權(quán)重級(jí)聯(lián)模型來模擬整個(gè)信息傳播過程，對(duì)本文提出的算法進(jìn)行實(shí)驗(yàn)分析和論證。針對(duì)影響力最大化問題，在結(jié)點(diǎn)相互影響概率不同時(shí)，在同樣數(shù)目的種子結(jié)點(diǎn)的情況下，本文提出的HISS-IM方法其影響的結(jié)點(diǎn)數(shù)目比經(jīng)典算法要更多，尤其是在要求影響范圍越大的情況下，效果更加明顯。針對(duì)最小代價(jià)的信息傳播問題，采用線性代價(jià)函數(shù)的情況下，三種算法的效果相差不是很明顯，在同等影響范圍的