社交網絡中的信息傳播算法研究.pdf

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

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

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

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

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