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

1、隨著網(wǎng)絡(luò)以及社交網(wǎng)站的快速發(fā)展，例如Facebook和Twitter，社交網(wǎng)絡(luò)已經(jīng)成為人們獲取信息和擴(kuò)散信息的主要平臺之一。在社交網(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)品最終帶來的利潤。基于此點，本文綜合考慮消息擴(kuò)散所需要的代價以及消息擴(kuò)散范圍問

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

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

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

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