社交網(wǎng)絡(luò)信息源檢測算法研究.pdf

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

2、究中非常熱門的方向。
　　本文提出一種自適應(yīng)觀察點(diǎn)部署策略，使觀察點(diǎn)的部署方案能根據(jù)網(wǎng)絡(luò)拓?fù)涞母淖儎討B(tài)調(diào)整。然后，通過這些部署的觀察點(diǎn)，記錄消息在網(wǎng)絡(luò)中的傳播信息，計(jì)算肯德爾相關(guān)系數(shù)，實(shí)現(xiàn)單信息源檢測。本論文的主要工作如下：
　　(1)觀察點(diǎn)部署策略研究。觀察點(diǎn)部署問題的研究是基于r覆蓋率最優(yōu)化策略。其關(guān)鍵是提出一種方案，使得觀察點(diǎn)集的r覆蓋率達(dá)到最大。具體是建立數(shù)學(xué)模型將觀察點(diǎn)集選取問題轉(zhuǎn)換成集合覆蓋問題，目前解決集合覆蓋

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

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