劉 棟，趙 婧，聶 豪

(1. 河南師范大學(xué) 計(jì)算機(jī)與信息工程學(xué)院，河南 新鄉(xiāng) 453007; 2. 教學(xué)資源與教育質(zhì)量評(píng)估大數(shù)據(jù)河南省工程實(shí)驗(yàn)室，河南 新鄉(xiāng) 453007)

0 引言

伴隨著Facebook、微信等在線社交網(wǎng)絡(luò)服務(wù)的出現(xiàn)，社交網(wǎng)絡(luò)已經(jīng)成為當(dāng)今社會(huì)人們信息交流的重要渠道和載體，且這些社交網(wǎng)絡(luò)允許用戶建立自己的“媒體”，對(duì)外發(fā)布、傳播信息?？煽康男畔⒛軌蚪o人們的生活帶來(lái)便捷，但謠言在互聯(lián)網(wǎng)上的傳播所帶來(lái)的負(fù)面影響也不可估量。傳染病的傳播也可看作網(wǎng)絡(luò)上的傳播現(xiàn)象，如2009年由流感病毒新型變體甲型H1N1流感所引發(fā)的全球性流行病疫情[1]，在很短時(shí)間內(nèi)便蔓延全球。

謠言或疾病的傳播都是依賴于具體網(wǎng)絡(luò)而存在的。例如，謠言傳播依賴于社交網(wǎng)絡(luò)，疾病傳播則依賴于人際交互網(wǎng)絡(luò)。這些網(wǎng)絡(luò)一般具有規(guī)模大，節(jié)點(diǎn)之間的聯(lián)系復(fù)雜等特征。在此類網(wǎng)絡(luò)上，如何快速準(zhǔn)確地確定疾病的傳染源、謠言的源頭就顯得十分重要。如果在短時(shí)間內(nèi)確定出疾病的傳染源，就能夠更好地控制整個(gè)疾病的傳播，縮小其傳播范圍，減少傳染病對(duì)人們生命安全的威脅。如果能在散布謠言后的關(guān)鍵時(shí)期迅速定位謠言來(lái)源，就能減少謠言對(duì)政治、人類切身利益和社會(huì)穩(wěn)定的負(fù)面影響。因此，在這個(gè)背景下，如何在一個(gè)網(wǎng)絡(luò)上定位一個(gè)傳染源或者謠言的源頭就成為一件非常有意義且十分具有挑戰(zhàn)性的事情。

對(duì)于網(wǎng)絡(luò)上的源點(diǎn)定位問(wèn)題，一種較為樸素的方法是通過(guò)獲取網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)在網(wǎng)絡(luò)傳播中的狀態(tài)，根據(jù)其相關(guān)記錄，確定信息傳播的源點(diǎn)。雖然這種方法能夠準(zhǔn)確定位信息源，但成本極高，可行性差，對(duì)于大規(guī)模網(wǎng)絡(luò)來(lái)說(shuō)幾乎無(wú)法實(shí)施。因此，需要一種有效可行的方法來(lái)估計(jì)和預(yù)測(cè)信息源的準(zhǔn)確位置。最新的研究趨勢(shì)是通過(guò)在網(wǎng)絡(luò)中部署少量觀察點(diǎn)，根據(jù)其接收的節(jié)點(diǎn)信息，推斷出信息源點(diǎn)在網(wǎng)絡(luò)中的位置。在該任務(wù)下，如何有效地部署觀察點(diǎn)，從而提高傳播源定位精度，成為了亟待解決的關(guān)鍵問(wèn)題。本工作針對(duì)上述問(wèn)題展開研究，力圖揭示網(wǎng)絡(luò)中觀察點(diǎn)部署策略與源點(diǎn)估算精度的關(guān)系。

本工作提出了幾種觀察點(diǎn)部署策略，包括隨機(jī)、度、聚類系數(shù)、特征向量、緊密度和介數(shù)。并且采用SI傳播模型和反向貪心溯源算法在合成網(wǎng)絡(luò)和真實(shí)網(wǎng)絡(luò)中進(jìn)行模擬仿真。通過(guò)分析不同觀察點(diǎn)部署策略對(duì)于傳播源定位精度的影響，期望尋找到有效的觀察點(diǎn)部署策略。

1 相關(guān)研究

目前，估計(jì)傳播源在傳染病控制、輿情控制等方面的應(yīng)用越來(lái)越廣泛，國(guó)內(nèi)外研究人員對(duì)于估計(jì)傳播源相關(guān)問(wèn)題的研究也越來(lái)越深入。根據(jù)快照信息范圍可以分為完整節(jié)點(diǎn)信息定位和部分節(jié)點(diǎn)信息定位。其中有的是關(guān)于定位傳染病的源頭、有的是關(guān)于定位謠言的源頭等等，但根據(jù)快照信息范圍大致可以歸為以上兩類。

Shah等人[2]針對(duì)正則樹上的SI模型提出一個(gè)基于傳播中心性的極大似然估計(jì)算法來(lái)確定傳播源。Fioriti等人[3]提出了計(jì)算感染圖中每個(gè)節(jié)點(diǎn)的動(dòng)態(tài)年齡的溯源算法DA。Comin等人[4]在雪崩傳播模型下提出了無(wú)偏中介算法。Prakash等人[5]提出了基于最小描述長(zhǎng)度的NetSleuth算法解決溯源問(wèn)題。還有Nino Antulov-Fantulin 等人[6]提出了基于蒙特卡洛模擬的定位算法。

以上工作都需要明確所有節(jié)點(diǎn)的傳播狀態(tài)，在大型網(wǎng)絡(luò)中這將要消耗很大的成本。為了克服這些困難，Pinto[7]設(shè)計(jì)了一個(gè)基于少量觀察點(diǎn)的精細(xì)極大似然估計(jì)算法來(lái)定位傳播源。Shen等人[8]開發(fā)了基于壓縮感知的構(gòu)建方法并提出了一種基于觀察點(diǎn)反向傳播的一種定位條件[9]。Luo等人[10]提出了一種適用于一般網(wǎng)絡(luò)的反向貪心算法。這些方法的基本思想都是基于選擇的部分節(jié)點(diǎn)進(jìn)行傳播源的估計(jì)。定位傳播源的精度在很大程度上取決于觀察點(diǎn)的選擇。

近幾年來(lái)國(guó)內(nèi)外研究人員在觀察點(diǎn)部署策略上也取得了一定的進(jìn)展。Brunella Spinelli等人[11]提出了一種在線迭代的部署最佳觀察點(diǎn)的方法來(lái)定位傳播源。Brunella Spinelli等人[12]還提出了基于傳播延遲方差的最大值和最小值來(lái)部署觀察點(diǎn)的方法。Celis等人[13]提出基于雙重解決集的部署觀察點(diǎn)策略。張錫哲等人[14-17]基于Pinto的極大似然估計(jì)溯源算法提出的一系列觀察點(diǎn)部署策略。上述研究均未基于反向貪心溯源算法提出觀察點(diǎn)部署策略。

其中，張錫哲等人[17]分析了基于節(jié)點(diǎn)中心性的觀察點(diǎn)部署策略對(duì)定位傳播源的精度的影響，他們的研究結(jié)果表明基于節(jié)點(diǎn)中心性的觀察點(diǎn)部署策略對(duì)于估計(jì)傳播源的精度并無(wú)顯著影響。與他們的研究結(jié)果不同的是，本工作同樣采用基于節(jié)點(diǎn)中心性的觀察點(diǎn)部署策略，但仿真結(jié)果表明采用特征向量的觀察點(diǎn)部署策略更有利于提高傳播源估計(jì)的精度。

分析與張錫哲等人研究的不同之處，主要在于他們的工作采用了基于少量觀測(cè)節(jié)點(diǎn)的極大似然估計(jì)算法定位傳播源，而本工作采用了基于傳播路徑的反向貪心算法。因此，估計(jì)傳播源的溯源算法也是關(guān)系到基于節(jié)點(diǎn)中心性觀察點(diǎn)部署策略適用性的重要因素。

本工作中，首先利用SI傳播模型模擬傳播。然后，根據(jù)傳播信息利用反向貪心算法定位傳播源，本文將在第二節(jié)中介紹所采用的傳播模型和定位方法。我們的主要工作是在模擬傳播完成后，提出了基于節(jié)點(diǎn)中心性的觀察點(diǎn)部署策略，根據(jù)各種策略選擇的部分觀察點(diǎn)進(jìn)行傳播源定位，本文將在第三節(jié)介紹基于節(jié)點(diǎn)中心性的觀察點(diǎn)部署策略。第四節(jié)介紹實(shí)驗(yàn)部分，最后在第五節(jié)做出結(jié)論。

2 所采用的傳播模型與定位方法

2.1 SI傳播模型

網(wǎng)絡(luò)可建模為一個(gè)無(wú)向圖G=(V,E)。其中V是頂點(diǎn)或節(jié)點(diǎn)的集合，E是邊的集合，代表兩節(jié)點(diǎn)之間有聯(lián)系。在本工作中，假設(shè)在圖G中最開始只有一個(gè)節(jié)點(diǎn)被“感染”，這個(gè)節(jié)點(diǎn)開始向它的鄰居節(jié)點(diǎn)傳播。本工作就是利用網(wǎng)絡(luò)中部分感染節(jié)點(diǎn)信息來(lái)確定這個(gè)傳播源。

在人群中的疾病傳播模型已經(jīng)在文獻(xiàn)[18-20]中得到廣泛的研究，這些模型也被用來(lái)模擬在線社交網(wǎng)絡(luò)中信息的傳播[21-24]。SI模型是作為模擬疾病傳播的一種自然現(xiàn)象出現(xiàn)的。在SI模型中，節(jié)點(diǎn)有三種狀態(tài)： 已感染狀態(tài)、易感染狀態(tài)和不易感染狀態(tài)。已感染節(jié)點(diǎn)將會(huì)感染其他節(jié)點(diǎn)并且一直保持被感染的狀態(tài)；易感染節(jié)點(diǎn)表示目前未被感染，但至少有一個(gè)鄰居節(jié)點(diǎn)被感染；不易感染的節(jié)點(diǎn)也是未被感染的節(jié)點(diǎn)但是它的鄰居都未被感染。類似于傳染性疾病的傳播，該模型也能描述謠言的傳播，在模型中的單個(gè)人可分為兩種類型： 第一類人是不知情者，他們對(duì)謠言是渾然不知的；第二類人是傳播者，他們是謠言的知情者，并且喜歡對(duì)謠言進(jìn)行傳播。

本工作中,采用的SI模型的時(shí)間是被劃分了的離散時(shí)間段，在時(shí)間段t內(nèi)節(jié)點(diǎn)u的狀態(tài)用隨機(jī)變量X(u,t)表示。在時(shí)間t=0時(shí)，假設(shè)只有一個(gè)節(jié)點(diǎn)v*∈V被感染，稱這個(gè)節(jié)點(diǎn)為傳播源。假設(shè)感染過(guò)程是一個(gè)在離散時(shí)間內(nèi)概率測(cè)度為P的馬爾可夫過(guò)程，且假設(shè)在下一個(gè)時(shí)間段開始。一個(gè)易感染節(jié)點(diǎn)被感染的概率為p,其中p∈(0,1)。 假設(shè)每個(gè)易感染節(jié)點(diǎn)是否會(huì)被感染都是相互獨(dú)立的，且不易感染節(jié)點(diǎn)始終都不會(huì)被感染。

在這個(gè)SI模型中，任何與被感染節(jié)點(diǎn)相鄰的健康節(jié)點(diǎn)被感染的概率都相同，與被感染的鄰居數(shù)量無(wú)關(guān)。傳播一段時(shí)間后，在所有節(jié)點(diǎn)的狀態(tài)信息中，健康節(jié)點(diǎn)的狀態(tài)都能正確地顯示出來(lái)，但是被感染節(jié)點(diǎn)的狀態(tài)只有一部分能正確顯示，稱為顯式狀態(tài)，另一部分將與健康狀態(tài)混淆，稱為隱式狀態(tài)。當(dāng)易感染節(jié)點(diǎn)u被感染并且為顯式狀態(tài)時(shí)用X(u,t)=e表示，并且被感染后為顯示狀態(tài)的節(jié)點(diǎn)集用Ve表示；當(dāng)易感染節(jié)點(diǎn)u被感染并且為隱式狀態(tài)時(shí)用X(u,t)=i表示。

用qu表示節(jié)點(diǎn)u被感染后為顯式狀態(tài)的概率，假設(shè)節(jié)點(diǎn)被感染后是否為顯式狀態(tài)與其他節(jié)點(diǎn)是相互獨(dú)立的。對(duì)于所有節(jié)點(diǎn)u∈V,如果qu=1，那么該模型本質(zhì)上會(huì)和文獻(xiàn)[25-26]中的一致；然而對(duì)于所有節(jié)點(diǎn)u∈V如果qu趨近于0，則大多數(shù)節(jié)點(diǎn)將會(huì)表現(xiàn)為未感染狀態(tài)。在這種情況下，估計(jì)傳播源將會(huì)變的十分困難，并且在實(shí)際中估計(jì)傳播源的精度將很低。直觀地說(shuō)，對(duì)于所有節(jié)點(diǎn)u如果qu≥p，則將會(huì)在這個(gè)SI模型中觀察到更多的被感染后為顯式狀態(tài)的節(jié)點(diǎn)，有利于提高估計(jì)傳播源的精度。在本工作中提出一個(gè)較弱的假設(shè)，對(duì)于所有節(jié)點(diǎn)u∈V，假設(shè)qu滿足

當(dāng)p>1/2時(shí)，對(duì)于任意節(jié)點(diǎn)u，假設(shè)中的qu需要滿足足夠大。這是因?yàn)樵谧銐蜷L(zhǎng)的一段時(shí)間內(nèi)，大部分節(jié)點(diǎn)將會(huì)被感染，若被感染的節(jié)點(diǎn)大都為隱式狀態(tài)，那么將很難估計(jì)傳播源；另一方面，如果p≤1/2，那么假設(shè)將微不足道。此時(shí)，對(duì)于任意節(jié)點(diǎn)u，該模型允許qu=0或者1，當(dāng)qu=1時(shí)，意味著將要觀察所有被感染的節(jié)點(diǎn)，這種情況類似于文獻(xiàn)[27]中的情況。故總結(jié)一個(gè)易感染節(jié)點(diǎn)的概率轉(zhuǎn)換圖如圖1 所示。

圖1 易感染節(jié)點(diǎn)的概率轉(zhuǎn)換圖

2.2 反向貪心溯源算法

本工作采用Luo等人[10]提出的方法估計(jì)傳播源。首先尋找與被感染節(jié)點(diǎn)集合一致的感染樹，然后計(jì)算可生成該感染樹的最可能傳播路徑，最后估計(jì)該樹的Jordan感染中心[28]作為網(wǎng)絡(luò)的傳播源。

在網(wǎng)絡(luò)G中，假設(shè)一個(gè)易感染節(jié)點(diǎn)只能隨機(jī)地被已感染鄰居節(jié)點(diǎn)中的一個(gè)節(jié)點(diǎn)感染，則在傳播源傳播結(jié)束后，被感染的節(jié)點(diǎn)組成的所有路徑將會(huì)是一個(gè)樹。經(jīng)過(guò)傳播t時(shí)間后，任意一條感染路徑用Xt=X(u,τ):u∈V,1≤τ≤t表示，則由Xt形成的T(Xt)為G的一棵子樹。Tv表示以節(jié)點(diǎn)v為根節(jié)點(diǎn)的樹，則在G的所有子樹中肯定存在一個(gè)與被感染節(jié)點(diǎn)集合組成的感染樹一致的樹。Tv表示由已感染且為顯式狀態(tài)的節(jié)點(diǎn)Ve組成的感染樹的集合。假設(shè)節(jié)點(diǎn)v為源點(diǎn)，該傳播源的最可能感染路徑，如式(2)所示。

假設(shè)G為一般網(wǎng)絡(luò)，且v∈V是傳播源。那么，對(duì)于任意一個(gè)以v為根節(jié)點(diǎn)且由節(jié)點(diǎn)集合Ve組成的感染樹T有：

其中pa(u)表示節(jié)點(diǎn)u的父母節(jié)點(diǎn)，令

3 基于節(jié)點(diǎn)中心性的觀察點(diǎn)部署策略

在網(wǎng)絡(luò)G中，當(dāng)傳播源利用SI傳播模型感染結(jié)束后，將得到為顯式狀態(tài)的節(jié)點(diǎn)集合Ve。在文獻(xiàn)[17]中，Luo等人是在隨機(jī)選擇部分節(jié)點(diǎn)上部署觀察點(diǎn)來(lái)收集信息。而本工作中，提出了基于節(jié)點(diǎn)中心性的觀察點(diǎn)部署策略，含節(jié)點(diǎn)的度、聚類系數(shù)、特征向量、緊密度、介數(shù)。下面介紹這五種指標(biāo)信息。

(1) 度

用于描述在靜態(tài)網(wǎng)絡(luò)中節(jié)點(diǎn)產(chǎn)生的直接影響力，其值為與該節(jié)點(diǎn)直接相連的節(jié)點(diǎn)數(shù)。則度定義為式(7)。

其中，d(i)表示與節(jié)點(diǎn)i直接相連的節(jié)點(diǎn)數(shù)。

(2) 緊密度

用于描述網(wǎng)絡(luò)中的節(jié)點(diǎn)通過(guò)網(wǎng)絡(luò)到達(dá)其他節(jié)點(diǎn)的難易度，其值為該節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的距離之 和的倒數(shù)。則緊密度定義為式(8)。

其中，dij表示節(jié)點(diǎn)i到節(jié)點(diǎn)j的最短距離。

(3) 介數(shù)

節(jié)點(diǎn)的介數(shù)反映了其在整個(gè)網(wǎng)絡(luò)中的作用和影響力，具有比較強(qiáng)的實(shí)際意義。則介數(shù)定義為式(9)。

其中，ljk表示節(jié)點(diǎn)j到節(jié)點(diǎn)k的最短路徑條數(shù)，ljk(i) 表示節(jié)點(diǎn)j與節(jié)點(diǎn)k之間經(jīng)過(guò)點(diǎn)i的最短路徑條數(shù)。

(4) 聚類系數(shù)

在復(fù)雜網(wǎng)絡(luò)中，假設(shè)網(wǎng)絡(luò)中的一個(gè)節(jié)點(diǎn)i有ki條邊將它和其他節(jié)點(diǎn)相連，這ki個(gè)節(jié)點(diǎn)就稱為節(jié)點(diǎn)i的鄰居。由于在這ki個(gè)節(jié)點(diǎn)之間最多可能有ki(ki-1)/2條邊，而這ki個(gè)節(jié)點(diǎn)之間實(shí)際存在的邊數(shù)Ei和總的可能的邊數(shù)ki(ki-1)/2之比就定義為節(jié)點(diǎn)i的聚類系數(shù)Ccl(i)，Ei為這ki個(gè)節(jié)點(diǎn)之間實(shí)際存在的邊數(shù)總和即

聚類系數(shù)用于描述節(jié)點(diǎn)鄰居之間連接的緊密程度。整個(gè)網(wǎng)絡(luò)的聚類系數(shù)Ccl就是所有節(jié)點(diǎn)i的聚類系數(shù)Ccl(i)的平均值。顯然0≤Ccl≤1，當(dāng)且僅當(dāng)所有節(jié)點(diǎn)都為孤立節(jié)點(diǎn)，即沒(méi)有任何連接邊的情況下Ccl=0；當(dāng)網(wǎng)絡(luò)是全局耦合時(shí)，即網(wǎng)絡(luò)中任意兩個(gè)節(jié)點(diǎn)都直接相連此時(shí)Ccl=1。

(5) 特征向量

用于描述節(jié)點(diǎn)周圍鄰居節(jié)點(diǎn)的重要性對(duì)該節(jié)點(diǎn)產(chǎn)生的影響。若λ為網(wǎng)絡(luò)鄰接矩陣A的主特征值，e=(e1,e2,...,en)為矩陣A對(duì)應(yīng)于主特征值λ的特征向量，則特征向量定義，如式(11)所示。

從上面可以看出度、聚類系數(shù)、特征向量、緊密度以及介數(shù)這些指標(biāo)信息，在網(wǎng)絡(luò)結(jié)構(gòu)中的意義差別還是很大的。有的指標(biāo)信息反映節(jié)點(diǎn)在整個(gè)網(wǎng)絡(luò)中的地位，有的指標(biāo)信息揭示周圍鄰居對(duì)中心節(jié)點(diǎn)的影響等。這些差別在信息擴(kuò)散的過(guò)程中都有所體現(xiàn)，在傳播過(guò)程都發(fā)揮了各自不同的作用，這也使得這幾類節(jié)點(diǎn)成為網(wǎng)絡(luò)中的重點(diǎn)研究對(duì)象。同時(shí)，正是這種在傳播時(shí)所表現(xiàn)出來(lái)的差異，顯得有必要按照這幾種指標(biāo)信息選擇觀察點(diǎn)。因它們能從各自不同的方面揭示網(wǎng)絡(luò)中的信息傳播過(guò)程，能夠更全面地感知信息在網(wǎng)中的擴(kuò)散，而這些對(duì)于準(zhǔn)確定位網(wǎng)絡(luò)中的信息源來(lái)說(shuō)是十分必要的。所以可利用以上指標(biāo)信息作為選擇觀察點(diǎn)的標(biāo)準(zhǔn)。下面的工作通過(guò)實(shí)驗(yàn)來(lái)分析這些部署策略對(duì)合成網(wǎng)絡(luò)和實(shí)際網(wǎng)絡(luò)的定位傳播源精度的影響。

4 實(shí)驗(yàn)

4.1 實(shí)驗(yàn)設(shè)置

本工作選取兩類網(wǎng)絡(luò)進(jìn)行實(shí)驗(yàn)。第一類是合成網(wǎng)絡(luò)，分別為從BA模型構(gòu)造的無(wú)標(biāo)度網(wǎng)絡(luò)、從WS模型構(gòu)造的小世界網(wǎng)絡(luò)和從ER模型構(gòu)造的隨機(jī)網(wǎng)絡(luò)；第二類為真實(shí)網(wǎng)絡(luò)，分別為屬于社會(huì)網(wǎng)絡(luò)的倉(cāng)鼠網(wǎng)絡(luò)[29]，即在倉(cāng)鼠網(wǎng)站中用戶的友誼與家庭之間的聯(lián)系網(wǎng)絡(luò)；屬于技術(shù)網(wǎng)絡(luò)的美國(guó)電力網(wǎng)絡(luò)[30]；屬于信息網(wǎng)絡(luò)的合著關(guān)系網(wǎng)絡(luò)[31]，選擇了其中最大連通子圖379個(gè)作者的關(guān)系網(wǎng)絡(luò)；屬于生物網(wǎng)絡(luò)的線蟲代謝網(wǎng)絡(luò)[32]。表1列出了這些網(wǎng)絡(luò)的規(guī)模。

本工作根據(jù)度、介數(shù)、緊密度、聚類系數(shù)以及特征向量五種網(wǎng)絡(luò)節(jié)點(diǎn)指標(biāo)信息就可以產(chǎn)生五種觀察點(diǎn)部署策略。即在選擇觀察點(diǎn)之前，根據(jù)網(wǎng)絡(luò)節(jié)點(diǎn)指標(biāo)信息的定義，計(jì)算網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的指標(biāo)信息。之后將該指標(biāo)進(jìn)行從大到小排序，最后根據(jù)所需要的觀察點(diǎn)數(shù)量按照指標(biāo)從大到小選擇節(jié)點(diǎn)作為觀察點(diǎn)。除此五種觀察點(diǎn)部署策略之外，還有一種就是隨機(jī)選擇節(jié)點(diǎn)作為觀察點(diǎn)，將此種部署策略作為與其他部署策略的對(duì)比。之后提到的觀察點(diǎn)部署策略也就是指的以上六種。

本工作中，設(shè)置選擇節(jié)點(diǎn)集Ve中50%的節(jié)點(diǎn)作為觀察點(diǎn)。如根據(jù)節(jié)點(diǎn)度大小來(lái)選擇50%的節(jié)點(diǎn)作為觀察點(diǎn)，則對(duì)網(wǎng)絡(luò)中所有節(jié)點(diǎn)按照度的大小排序，最后選擇排在前50%的節(jié)點(diǎn)作為觀察點(diǎn)。如果是在隨機(jī)選擇觀察點(diǎn)的情況下，就不需要排序，直接根據(jù)觀察點(diǎn)的數(shù)量在網(wǎng)絡(luò)中隨機(jī)選擇即可。

表1 實(shí)驗(yàn)網(wǎng)絡(luò)的規(guī)模

在每種網(wǎng)絡(luò)上，仿真模擬運(yùn)行1 000次。在每次模擬運(yùn)行中，先隨機(jī)選擇一個(gè)節(jié)點(diǎn)作為傳播源，再使用SI模型模擬傳播。對(duì)于任意節(jié)點(diǎn)v，p和qv分別是在(0,1)和[max(0,2-1/p),1]中均勻選擇的。

4.2 實(shí)驗(yàn)結(jié)果和分析

通過(guò)研究在合成網(wǎng)絡(luò)和真實(shí)網(wǎng)絡(luò)上估計(jì)傳播源精度的結(jié)果，探索了觀察點(diǎn)部署策略與估計(jì)傳播源精度的關(guān)系。從而發(fā)現(xiàn)觀察點(diǎn)部署策略對(duì)于估計(jì)傳播源精度產(chǎn)生的具體影響。

圖2是小世界網(wǎng)絡(luò)在各種觀察點(diǎn)部署策略下溯源算法的錯(cuò)誤距離分布圖，錯(cuò)誤距離是估計(jì)的傳播源與真實(shí)的傳播源之間的跳數(shù)。在觀察點(diǎn)部署策略隨機(jī)、度、聚類系數(shù)、介數(shù)、緊密度以及特征向量下估計(jì)傳播源的精度分別為0.23、0.12、0.24、0.21、0.25以及0.27。實(shí)驗(yàn)結(jié)果表明采用特征向量觀察點(diǎn)部署策略估計(jì)傳播源的精度高于其他策略。

圖2 小世界網(wǎng)絡(luò)在各種觀察點(diǎn)部署策略下溯源算法的錯(cuò)誤距離分布

圖3是隨機(jī)網(wǎng)絡(luò)在各種觀察點(diǎn)部署策略下溯源算法的錯(cuò)誤距離分布圖。在觀察點(diǎn)部署策略隨機(jī)、度、聚類系數(shù)、介數(shù)、緊密度以及特征向量下估計(jì)傳播源的精度分別為0.03、0.01、0.02、0.01、0.02以及0.08。實(shí)驗(yàn)結(jié)果表明采用特征向量觀察點(diǎn)部署策略估計(jì)傳播源的精度高于其他策略；另外，相比隨機(jī)選擇策略，采用特征向量觀察點(diǎn)部署策略，準(zhǔn)確定位傳播源的精度可以提高到兩倍多。

圖3 隨機(jī)網(wǎng)絡(luò)在各種觀察點(diǎn)部署策略下溯源算法的錯(cuò)誤距離分布

圖4是無(wú)標(biāo)度網(wǎng)絡(luò)在各種觀察點(diǎn)部署策略下溯源算法的錯(cuò)誤距離分布圖。在觀察點(diǎn)部署策略隨機(jī)、度、聚類系數(shù)、介數(shù)、緊密度以及特征向量下估計(jì)傳播源的精度分別為0.10、0.21、0.05、0.15、0.21以及0.27。實(shí)驗(yàn)結(jié)果表明，采用特征向量觀察點(diǎn)部署策略估計(jì)傳播源的精度高于其他策略；另外，相比隨機(jī)選擇策略，采用特征向量觀察點(diǎn)部署策略，準(zhǔn)確定位傳播源的精度可以提高到兩倍多。

圖4 無(wú)標(biāo)度網(wǎng)絡(luò)在各種觀察點(diǎn)部署策略下溯源算法的錯(cuò)誤距離分布

圖5是倉(cāng)鼠網(wǎng)絡(luò)在各種觀察點(diǎn)部署策略下溯源算法的錯(cuò)誤距離分布圖。在觀察點(diǎn)部署策略隨機(jī)、度、聚類系數(shù)、介數(shù)、緊密度以及特征向量下估計(jì)傳播源的精度分別為0.06、0.00、0.11、0.00、0.14以及0.16。實(shí)驗(yàn)結(jié)果表明，采用特征向量觀察點(diǎn)部署策略估計(jì)傳播源的精度高于其他策略；另外，相比隨機(jī)選擇策略，采用特征向量觀察點(diǎn)部署策略，準(zhǔn)確定位傳播源的精度可以提高到兩倍多。

圖5 倉(cāng)鼠網(wǎng)絡(luò)在各種觀察點(diǎn)部署策略下溯源算法的錯(cuò)誤距離分布

圖6是美國(guó)電力網(wǎng)絡(luò)在各種觀察點(diǎn)部署策略下溯源算法的錯(cuò)誤距離分布圖。需要說(shuō)明的是，在文獻(xiàn)[10] 中指出在真實(shí)美國(guó)電力網(wǎng)絡(luò)上采用基于傳播中心性溯源算法的精度只有3%，在實(shí)驗(yàn)中利用這六種觀察點(diǎn)部署策略估計(jì)真實(shí)傳播源的精度最高的也只有1%。因?yàn)榫葮O低再加上錯(cuò)誤距離最大的已經(jīng)達(dá)到20跳，而美國(guó)電力網(wǎng)絡(luò)的精度用的是錯(cuò)誤距離在3跳以內(nèi)的比例。在觀察點(diǎn)部署策略隨機(jī)、度、聚類系數(shù)、介數(shù)、緊密度以及特征向量下估計(jì)傳播源的精度分別為0.23、0.12、0.24、0.21、0.25以及0.27。實(shí)驗(yàn)結(jié)果表明，采用特征向量觀察點(diǎn)部署策略估計(jì)傳播源的精度高于其他策略；另外，相比隨機(jī)選擇策略，采用特征向量觀察點(diǎn)部署策略，準(zhǔn)確定位傳播源的精度可以提高到兩倍多。

圖6 美國(guó)電力網(wǎng)絡(luò)在各種觀察點(diǎn)部署策略下溯源算法的錯(cuò)誤距離分布

圖7是合著關(guān)系網(wǎng)絡(luò)在各種觀察點(diǎn)部署策略下溯源算法的錯(cuò)誤距離分布圖。在觀察點(diǎn)部署策略隨機(jī)、度、聚類系數(shù)、介數(shù)、緊密度以及特征向量下估計(jì)傳播源的精度分別為0.02、0.02、0.01、0.00、0.02以及0.05。實(shí)驗(yàn)結(jié)果表明，采用特征向量觀察點(diǎn)部署策略估計(jì)傳播源的精度高于其他策略；另外，相比隨機(jī)選擇策略，采用特征向量觀察點(diǎn)部署策略，準(zhǔn)確定位傳播源的精度可以提高到兩倍多。

圖7 合著關(guān)系網(wǎng)絡(luò)在各種觀察點(diǎn)部署策略下溯源算法的錯(cuò)誤距離分布

圖8是線蟲代謝網(wǎng)絡(luò)在各種觀察點(diǎn)部署策略下溯源算法的錯(cuò)誤距離分布圖。在觀察點(diǎn)部署策略隨機(jī)、度、聚類系數(shù)、介數(shù)、緊密度以及特征向量下估計(jì)傳播源的精度分別為0.06、0.01、0.05、0.00、0.00以及0.08。實(shí)驗(yàn)結(jié)果表明，采用特征向量觀察點(diǎn)部署策略估計(jì)傳播源的精度高于其他策略。

圖8 線蟲代謝網(wǎng)絡(luò)在各種觀察點(diǎn)部署策略下溯源算法的錯(cuò)誤距離分布

本實(shí)驗(yàn)在上述七種網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)上測(cè)試了這六種觀察點(diǎn)部署策略對(duì)采用反向貪心溯源算法定位傳播源精度的影響，將測(cè)試結(jié)果整理在表2中，并在表中將最優(yōu)的性能值加粗表示。從表2可看出，采用特征向量觀察點(diǎn)部署策略更有利于提高估計(jì)傳播源的精度。另外，在無(wú)標(biāo)度網(wǎng)絡(luò)、隨機(jī)網(wǎng)絡(luò)、美國(guó)電力網(wǎng)絡(luò)、倉(cāng)鼠網(wǎng)絡(luò)以及合著關(guān)系網(wǎng)絡(luò)這些網(wǎng)絡(luò)上。相比隨機(jī)選擇策略，采用特征向量部署策略，準(zhǔn)確定位傳播源的精度可以提高到兩倍多。從這些錯(cuò)誤距離分布圖中可以看出每個(gè)網(wǎng)絡(luò)都隨著觀察點(diǎn)部署策略的改變而改變，但是在各個(gè)網(wǎng)絡(luò)中錯(cuò)誤距離分布的趨勢(shì)很相似。

表2 各種網(wǎng)絡(luò)在六種觀察點(diǎn)部署策略下定位傳播源的精度

5 總結(jié)

在網(wǎng)絡(luò)中估計(jì)傳播源是一項(xiàng)重要的研究課題。估計(jì)傳播源的一種可行的方法，即是利用觀察點(diǎn)收集的部分節(jié)點(diǎn)信息來(lái)定位傳播源。故而，估計(jì)傳播源與觀察點(diǎn)的部署策略緊密相關(guān)。本研究評(píng)估了幾種觀察點(diǎn)部署策略，含度數(shù)、介數(shù)、緊密度、聚類系數(shù)、特征向量和隨機(jī)。利用SI傳播模型和反貪心溯源算法，在合成網(wǎng)絡(luò)和真實(shí)網(wǎng)絡(luò)上仿真模擬。實(shí)驗(yàn)結(jié)果表明，采用特征向量觀察點(diǎn)部署策略更有利于提高估計(jì)傳播源的精度，且與隨機(jī)選擇觀察點(diǎn)部署策略相比，在某些網(wǎng)絡(luò)上估計(jì)的傳播源精度可以提高到兩倍多。

基于節(jié)點(diǎn)中心性的觀察點(diǎn)部署策略與采用的估計(jì)傳播源的算法相關(guān)，而這些觀察點(diǎn)部署策略對(duì)于其他溯源算法精度的影響需要進(jìn)一步研究。是否能找到一種策略可以適用各種溯源算法，這些問(wèn)題將會(huì)在以后的工作中做進(jìn)一步的討論。