信息傳播網絡中信息源推斷問題的研究.pdf

1、伴隨著科技的進步、Internet網絡的發(fā)展，以及智能終端的快速普及，4G、WIFI等高速無線接入技術的迅猛發(fā)展，現代網絡（如社會網絡、無線通信網絡、交通網絡和在線社交網絡等等）在網絡規(guī)模和復雜性都得到大幅的增加，使得信息的傳播更加便捷。于是，帶領我們來到了信息爆炸的大數據的時代。網絡中紛繁的信息傳播現象無處不在，同時也使我們更容易受到來自于網絡的風險。網絡中比如流行性疾病，計算機病毒，社交網絡謠言等惡意信息的傳播，嚴重的妨害了社會秩序

2、，帶給社會在人力和經濟上的巨大損失。因此快速而準確的推斷出網絡中信息傳播的源節(jié)點，可以幫助控制和防止這些網絡風險的發(fā)生，從而使網絡風險給社會帶來的損失降到最低。
　　針對信息源推斷問題，本文的主要貢獻如下:
　　1)研究了基于SI模型的多樣本觀測下的信息源推斷問題?？紤]網絡中同一個源節(jié)點可能發(fā)出多條信息/謠言，提出了一個基于聯合謠言向心性的信息源推斷框架，并對于規(guī)則樹網絡，給出了明確的正確檢測概率的性能表現。結果表明，即使僅

3、僅是兩個樣本觀察，正確檢測概率隨著網絡節(jié)點度的增加而單調遞增，至少兩倍于單樣本檢測，并且當度足夠大時，正確檢測概率趨于1。進一步，我們證明了對于度大于2的規(guī)則樹圖，正確檢測概率隨著樣本數k的增加而單調遞增，當k足夠大時，檢測概率也趨于1。這表明豐富的多樣性和豐富的連通性都可以提高檢測性能。最后我們又將我們提出的算法推廣到一般樹圖以及實際網絡中，如小世界網絡和無標度網絡等，來分析多樣本下的信息源檢測性能，都可以得到多樣本檢測可以顯著地提高

4、檢測性能。
　　2)研究了基于SI模型的帶有時序信息的信息源推斷問題。考慮了部分感染節(jié)點可以提供感染順序的信息，我們把這些感染節(jié)點叫做“錨節(jié)點”。提出了一個基于受限謠言向心性的最大似然估計器和與之對應的信息源推斷算法。受限謠言向心性是一個考慮了錨節(jié)點的感染順序的網絡拓撲量。此外，設計了一個次優(yōu)的RC啟發(fā)式快速算法。次優(yōu)的RC算法比最優(yōu)的RRC算法的正確檢測概率低，但其計算復雜度低，計算更快速。結果表明，當隨機選取的m個錨節(jié)點中只已

5、知最先被感染的節(jié)點的情況下，我們發(fā)現當錨節(jié)點占總感染節(jié)點數目的比例比較小時，已知錨節(jié)點的感染順序對于信息源的檢測性能影響很大;而互相連通的m個錨節(jié)點會幫助正確檢測信息源的概率得到大幅提高，即使對于線性網絡。最后我們將提出的算法推廣到一般樹圖以及實際網絡中，如紐曼科學合作網絡和推特轉發(fā)關系網絡等，得到帶有時序信息的信息源推斷可以有效地提高檢測性能。
　　3)研究了其他場景下的信息源推斷問題，具體為3小部分。首先，我們研究了SIS模型

6、下的信息源推斷。我們研究SI與SIS模型的關系，設計算法還原出SIS模型中一些曾經被感染，但已經恢復的感染節(jié)點。并將單樣本拓展到多樣本下的信息源推斷，提出了一個基于聯合謠言中心的SIS模型下的啟發(fā)式算法。最后我們將提出的算法應用在一般樹圖以及實際網絡中，進行SIS模型下的檢測性能分析。結果顯示我們提出的啟發(fā)式算法提供了良好的檢測性能，而且多樣本觀測相比單樣本，可以顯著的提高檢測性能。其次，我們研究了基于SI模型的多信息源推斷問題。我們通

7、過構造互相連通的多信息源最大似然檢測器，利用數理統(tǒng)計的方法分析規(guī)則樹圖下的正確檢測概率。然后設計算法在規(guī)則樹圖，一般圖以及實際圖中進行多信息源檢測的性能分析，并將單樣本下多信息源推斷拓展到多樣本。結果顯示我們提出的算法提供了良好的檢測性能，而且多樣本觀測相比單樣本，可以顯著的提高檢測性能。最后，我們研究了基于SI模型的多樣本序貫檢測下的信息源推斷。不同于研究點一的多樣本觀測下的信息源推斷，這里研究的多樣本序貫觀測考慮的網絡中只有一個信息