面向網(wǎng)絡(luò)擴(kuò)散源點(diǎn)定位的觀察點(diǎn)部署策略研究及定位算法優(yōu)化.pdf

1、現(xiàn)實(shí)生活中很多問題都可以建模為復(fù)雜網(wǎng)絡(luò)上的源點(diǎn)定位問題，如確定流行病的傳染源，找出謠言的源頭等等，這些現(xiàn)象往往會(huì)在網(wǎng)絡(luò)中產(chǎn)生級(jí)聯(lián)效應(yīng)，因此如何能夠準(zhǔn)確快速的定位網(wǎng)絡(luò)上的信息源，對(duì)于傳染病控制、輿論控制等具有重要的意義。
　　在源點(diǎn)定位問題上，一種典型的方法是通過在網(wǎng)絡(luò)上部署觀察點(diǎn)，根據(jù)觀察點(diǎn)記錄的傳播信息來估計(jì)網(wǎng)絡(luò)中的信息源點(diǎn)，但是該方法的定位準(zhǔn)確率受觀察點(diǎn)的部署影響較大，而且對(duì)于大規(guī)模網(wǎng)絡(luò)其定位效率較低。針對(duì)以上問題，本文基于復(fù)

2、雜網(wǎng)絡(luò)相關(guān)理論，完成了以下兩方面的工作。
　　首先，研究了不同觀察點(diǎn)部署策略對(duì)于源點(diǎn)定位準(zhǔn)確率的影響。根據(jù)網(wǎng)絡(luò)中節(jié)點(diǎn)的中心性指標(biāo)選用了六種觀察點(diǎn)部署策略，分別在模型網(wǎng)絡(luò)和實(shí)際網(wǎng)絡(luò)中進(jìn)行信息源定位實(shí)驗(yàn)，結(jié)果發(fā)現(xiàn)，隨觀察點(diǎn)比例升高，定位準(zhǔn)確率顯著提升;在網(wǎng)絡(luò)平均度較高時(shí)，定位準(zhǔn)確率較低。進(jìn)一步實(shí)驗(yàn)表明，信息源點(diǎn)到觀察點(diǎn)距離的方差與定位準(zhǔn)確率具有直接關(guān)系，在信息源點(diǎn)到觀察點(diǎn)距離的方差較大時(shí)，定位準(zhǔn)確率可以維持在較高水平，這為觀察點(diǎn)部署策

3、略的優(yōu)化提供了實(shí)驗(yàn)依據(jù)。
　　其次，現(xiàn)有源點(diǎn)定位算法時(shí)間復(fù)雜度為O(n3)，在大規(guī)模網(wǎng)絡(luò)上其定位效率難以接受。針對(duì)源點(diǎn)定位算法時(shí)間復(fù)雜度高的問題，提出了一種信息源點(diǎn)快速定位算法，算法依據(jù)候選源點(diǎn)估計(jì)值在網(wǎng)絡(luò)中的分布規(guī)律，采用局部搜索策略，減少了候選源點(diǎn)的遍歷個(gè)數(shù)，降低了算法的復(fù)雜度。通過實(shí)驗(yàn)證明，與現(xiàn)有算法相比，改進(jìn)后的算法在大規(guī)模網(wǎng)絡(luò)中其快速定位的優(yōu)勢(shì)更加明顯。
　　定位準(zhǔn)確率和定位效率對(duì)于任何定位算法都是十分重要的，本文