信息傳播網(wǎng)絡(luò)中信息源推斷問題的研究.pdf

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

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

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

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

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

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

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