社交網絡信息源檢測算法研究.pdf

1、互聯(lián)網技術的發(fā)展，給人們的社交方式帶來了巨大的改變，尤其是大批移動社交平臺的出現(xiàn)例如微博、微信、QQ等，吸引了大量用戶參與其中。這些用戶來自社會的各個領域，通過這些社交平臺參與社交，形成了各種各樣規(guī)模宏大的社交網絡。這些社交網絡的出現(xiàn)為大量信息傳播提供了更快速和范圍更廣的途徑。社交網絡信息源檢測一直是非常熱門的話題，檢測出信息源，我們可以從源頭上管理信息的分發(fā)以及保障社交網絡健康發(fā)展。目前，基于現(xiàn)有社交網絡拓撲來檢測信息源成為社交網絡研

2、究中非常熱門的方向。
　　本文提出一種自適應觀察點部署策略，使觀察點的部署方案能根據網絡拓撲的改變動態(tài)調整。然后，通過這些部署的觀察點，記錄消息在網絡中的傳播信息，計算肯德爾相關系數，實現(xiàn)單信息源檢測。本論文的主要工作如下：
　　(1)觀察點部署策略研究。觀察點部署問題的研究是基于r覆蓋率最優(yōu)化策略。其關鍵是提出一種方案，使得觀察點集的r覆蓋率達到最大。具體是建立數學模型將觀察點集選取問題轉換成集合覆蓋問題，目前解決集合覆蓋

3、問題常用的一種方法是貪婪算法，但考慮到網絡中節(jié)點的重要性，為了降低計算時間成本，優(yōu)先考慮那些重要性較高的節(jié)點，它們對觀察點集合的覆蓋率影響遠大于重要性低的節(jié)點，根據這種思想提出基于啟發(fā)策略的貪婪算法。評價節(jié)點的重要性指標有很多，本文中使用度中心性來，先定義一個閾值，度小于這個閾值的節(jié)點不予考慮，相比較貪婪算法，基于啟發(fā)策略的貪婪算法可以加快收斂，提高時間效率。
　　(2)社交網絡中單信息源的檢測研究。在單信息源網絡中，由于信息的發(fā)

4、布者是唯一的，因此觀察點收到信息的時間和觀察點到信息源的距離有關。在大部分的社交網絡中，節(jié)點之間的距離越短，信息在節(jié)點之間的傳播時間越短。基于這種思想，對觀察點收到消息的實際時間和觀察點到候選信息源的距離之間的關系進行量化，計算出肯德爾相關系數，實現(xiàn)單信息源檢測。另外，本文也提出基于時間差的單信息源檢測算法。
　　(3)實驗驗證本文提出的信息源檢測算法。分別用模擬網絡和實際網絡驗證本文提出的信息源檢測算法。結果表明提出的算法既降低