獨(dú)立級(jí)聯(lián)模型下基于時(shí)效性的負(fù)影響力源定位方法

摘 要：在當(dāng)今快速發(fā)展的社交網(wǎng)絡(luò)中，有害信息的傳播對(duì)社會(huì)穩(wěn)定構(gòu)成威脅，識(shí)別和定位有害消息源對(duì)于控制輿論至關(guān)重要。在社交網(wǎng)絡(luò)的實(shí)際傳播中，有害信息的可信度在傳播中會(huì)隨著時(shí)間的推移而衰減，不考慮這一因素會(huì)導(dǎo)致傳播源定位的準(zhǔn)確性降低。針對(duì)該問題，提出了一種獨(dú)立級(jí)聯(lián)模型下基于時(shí)效性的傳播源定位方法。在定義了節(jié)點(diǎn)激活概率衰減系數(shù)的基礎(chǔ)上，通過Bayes模型計(jì)算出節(jié)點(diǎn)被感染的后驗(yàn)概率；然后通過隨機(jī)游走計(jì)算所有節(jié)點(diǎn)影響力，選取影響力大于閾值的節(jié)點(diǎn)加入候選源集合。最后，比較候選源集合節(jié)點(diǎn)的感染時(shí)間與其到觀測(cè)節(jié)點(diǎn)的距離來選取k個(gè)源節(jié)點(diǎn)集合。在真實(shí)和合成網(wǎng)絡(luò)上的實(shí)驗(yàn)結(jié)果表明，該方法能夠準(zhǔn)確識(shí)別多個(gè)傳播源，源定位結(jié)果的精確度高于其他類似算法。

關(guān)鍵詞：社交網(wǎng)絡(luò)；獨(dú)立級(jí)聯(lián)傳播模型；影響力傳播；感染時(shí)間；傳播源定位

中圖分類號(hào)：TP391"" 文獻(xiàn)標(biāo)志碼：A"" 文章編號(hào)：1001-3695（2025）01-008-0056-09

doi： 10.19734/j.issn.1001-3695.2024.06.0201

Timeliness-based method for locating sources of negative influence under independent cascade model

Abstract： In today’s rapidly developing social networks， the spread of harmful information poses a threat to social stability. Identifying and locating harmful message sources is crucial for controlling public opinion. In the actual dissemination of social networks， the credibility of harmful information will decay over time. Ignoring this factor will reduce the accuracy of locating the source of the dissemination. To address this problem， this paper proposed a time-based source localization method under an independent cascade model. This paper defined the attenuation coefficient of the node activation probability and calculated the posterior probability of the node being infected through the Bayes model. Then it calculated the influence of all nodes through random walks， and nodes with influence greater than the threshold were selected to join the candidate source set. Finally， it compared the infection time of the nodes in the candidate source set with the distance between the observed node and the candidate source to select a set of k source nodes. Experimental results on real and synthetic networks show that this method can accurately identify multiple dissemination sources， and the accuracy of the source location result is higher than those of other similar algorithms.

Key words：social network; independent cascade propagation model; influence spread; infection time; source location

0 引言

隨著現(xiàn)代互聯(lián)網(wǎng)技術(shù)的高速發(fā)展，各種社交平臺(tái)應(yīng)運(yùn)而生。每天，數(shù)以億計(jì)的用戶通過文字、視頻、圖片等在線社交網(wǎng)絡(luò)進(jìn)行交流、獲取信息、分享觀點(diǎn)。與此同時(shí)，謠言、計(jì)算機(jī)病毒、假新聞等也會(huì)在網(wǎng)絡(luò)上快速傳播［1，2］。例如，在Facebook和Twitter等社交網(wǎng)絡(luò)中，謠言的傳播速度非?？欤?］。計(jì)算機(jī)病毒在互聯(lián)網(wǎng)上傳播，能夠感染數(shù)以百萬的計(jì)算機(jī)［4］。因此，為了有效地從源頭上阻斷負(fù)面信息的傳播，需要在社交網(wǎng)絡(luò)中準(zhǔn)確識(shí)別負(fù)面信息的來源。然而，在實(shí)踐中，由于網(wǎng)絡(luò)空間用戶的隱私性，往往不知道負(fù)面信息從何而來。所以可以在網(wǎng)絡(luò)中選擇幾個(gè)觀測(cè)節(jié)點(diǎn)，利用它們受負(fù)面信息影響的狀態(tài)和時(shí)間來精確定位負(fù)面信息的來源。通常，在社交網(wǎng)絡(luò)中，錯(cuò)誤信息是沿著不同的路徑傳播的，這些路徑與多個(gè)來源相連，有必要研究有效的定位多影響源的方法。

社交網(wǎng)絡(luò)中的源定位問題就是從給出的一些觀察者節(jié)點(diǎn)的信息來推測(cè)傳播源。當(dāng)前識(shí)別傳播源的方法大體分為對(duì)單源的識(shí)別以及對(duì)多源的識(shí)別［5，6］。Shah等人［7，8］提出了謠言中心性方法用于單源識(shí)別。Dong等人［9］假設(shè)謠言來自于單一源頭，提出了一種基于局部謠言中心性的方法來識(shí)別謠言傳播源。Prakash等人［10］提出了一種最小描述長(zhǎng)度（MDL）方法用于源識(shí)別，他們計(jì)算頂點(diǎn)激活概率的上界，通過上界的最大化來尋找傳播源。 具體地，他們找到感染圖的拉普拉斯矩陣的最小特征值和相應(yīng)的特征向量，取該特征向量中最大分量對(duì)應(yīng)的節(jié)點(diǎn)為傳播源。在與前者相同假設(shè)下，F(xiàn)ioriti等人［11］提出一種基于動(dòng)態(tài)年齡的方法來進(jìn)行源識(shí)別。他們定義節(jié)點(diǎn)動(dòng)態(tài)年齡為DAi=|λm－λim|/λm，其中λm為鄰接矩陣的最大特征值，λim為移除節(jié)點(diǎn)i后鄰接矩陣的最大特征值，動(dòng)態(tài)年齡最大的節(jié)點(diǎn)被選為源。該方法與MDL方法類似，都不適用于大規(guī)模網(wǎng)絡(luò)中的源識(shí)別。Zhu等人［12］提出了一種基于樣本路徑的方法，在SIR（susceptible-infectious-recovered）模型下識(shí)別傳播源。他們定義最佳樣本路徑為最有可能導(dǎo)致觀察節(jié)點(diǎn)給定狀態(tài)的傳播路徑，并論證了與最佳樣本路徑相關(guān)的源即為感染圖的Jordan中心。他們［13］又進(jìn)一步將該方法擴(kuò)展到SIR模型，也得到了相同的結(jié)論。Lokhov等人［14］還提出了動(dòng)態(tài)消息傳遞的方法識(shí)別傳播源。該方法對(duì)每一個(gè)節(jié)點(diǎn)設(shè)為信息傳播的源頭，估計(jì)在某一時(shí)刻t，其他節(jié)點(diǎn)處于不同狀態(tài)的概率。然后將觀察節(jié)點(diǎn)集合處于不同狀態(tài)的概率相乘，取獲得最大乘積的節(jié)點(diǎn)為傳播源。該方法顯著優(yōu)于基于中心性的方法，但對(duì)于強(qiáng)連接的網(wǎng)絡(luò)計(jì)算成本非常高。Pinto等人［15］提出了一種高斯方法用于單源識(shí)別。該方法分為兩個(gè)步驟：a）根據(jù)信息傳播到觀測(cè)節(jié)點(diǎn)的方向，確定一個(gè)唯一的子樹Ta來縮小傳播源的范圍，傳播源就包含在其中；b）通過高斯方法來尋找子樹Ta中的傳播源。對(duì)每一個(gè)觀測(cè)節(jié)點(diǎn)計(jì)算與其余觀測(cè)節(jié)點(diǎn)的“觀測(cè)延遲”，以及每個(gè)觀測(cè)節(jié)點(diǎn)“確定性延遲”，通過最小化“觀測(cè)延遲”和觀測(cè)節(jié)點(diǎn)的“確定性延遲”之間的距離來確定傳播源。

除此之外，學(xué)者們對(duì)多源定位的方法也展開了研究，并提出了一些有效的方法。一些方法將多源問題轉(zhuǎn)換為單源問題進(jìn)行研究。例如，Luo等人［16］將單一謠言中心性方法擴(kuò)展應(yīng)用到識(shí)別多個(gè)消息源，提出了一個(gè)雙源估計(jì)的方法來計(jì)算只有兩個(gè)傳播源時(shí)的謠言中心性。該方法首先采用Voronoi分區(qū)算法［17］將所有感染節(jié)點(diǎn)劃分為不同的分區(qū)，再采用單一謠言中心性方法在每個(gè)分區(qū)中識(shí)別候選源。最后，將候選源通過任意兩個(gè)相鄰分區(qū)之間的雙源估計(jì)進(jìn)行精確化。Zang等人［18］通過引入一種反向傳播模型來檢測(cè)已恢復(fù)和未觀察到的受感染節(jié)點(diǎn)，形成擴(kuò)展的感染節(jié)點(diǎn)集合。然后使用一種社區(qū)檢測(cè)方法，將擴(kuò)展的感染節(jié)點(diǎn)進(jìn)行聚類，最后在每個(gè)社區(qū)中使用最大似然估計(jì)來識(shí)別傳播源。Ding等人［19］提出了一種在SIR模型下的多源定位PRIA算法。該方法首先用一種基于有效距離的方法對(duì)節(jié)點(diǎn)進(jìn)行分區(qū)，然后利用反向感染算法進(jìn)行源定位。也有一些方法不將多源問題轉(zhuǎn)換為多個(gè)單源問題，而是直接對(duì)多源問題整體進(jìn)行研究。例如，熊才權(quán)等人［20］通過K-shell方法和兩階鄰居來考慮全局信息。Wang等人［21］提出了基于標(biāo)簽傳播的源識(shí)別方法，將感染區(qū)域最中心的節(jié)點(diǎn)作為源。類似地，Cheng等人［22］在該基礎(chǔ)上提出了基于路徑的多源定位。Zhang等人［23］提出了Bayes模型來計(jì)算節(jié)點(diǎn)的后驗(yàn)概率，然后使用基于隨機(jī)游走的方法對(duì)部分觀測(cè)節(jié)點(diǎn)進(jìn)行回溯，每次將最有可能的節(jié)點(diǎn)加入候選源中，最后通過候選源中節(jié)點(diǎn)的訪問頻率來確定傳播源。

在上述傳播源定位的算法中，一部分是通過節(jié)點(diǎn)中心性［24］來進(jìn)行研究，但這樣就忽視了節(jié)點(diǎn)之間邊上的傳播概率。另一部分是通過使用BFS［22］樹來模擬傳播過程，但BFS樹無法準(zhǔn)確地描述真實(shí)傳播過程，容易導(dǎo)致信息丟失。

邵玉等人［25］提出了一種基于最大似然的源定位方法。該方法基于傳播圖的概念，根據(jù)節(jié)點(diǎn)的入度和邊的權(quán)重將其劃分成若干層級(jí)，并去除傳播概率最小的邊，形成包含觀測(cè)節(jié)點(diǎn)的傳播圖，然后通過似然法估計(jì)傳播圖中每一層頂點(diǎn)的激活概率，選取相對(duì)于觀測(cè)點(diǎn)似然最大的k個(gè)頂點(diǎn)構(gòu)成源節(jié)點(diǎn)集合。本文方法首先假設(shè)了負(fù)面信息的可信度會(huì)隨時(shí)間衰減，由此假定了一個(gè)衰減系數(shù)，計(jì)算各頂點(diǎn)被感染的后驗(yàn)概率，從被感染的觀測(cè)點(diǎn)出發(fā)，計(jì)算節(jié)點(diǎn)的影響力，得到一個(gè)大于閾值的候選源集，根據(jù)候選源到觀測(cè)節(jié)點(diǎn)的距離和感染時(shí)間是否相同，來選取k個(gè)源節(jié)點(diǎn)集合。兩種方法的區(qū)別在于：前者是基于抽樣的方法構(gòu)造傳播圖，然后使用最大似然來定位源；后者是考慮到了現(xiàn)實(shí)因素，即信息的可信度會(huì)隨著時(shí)間衰減，引入一個(gè)衰減系數(shù)，然后通過節(jié)點(diǎn)的感染時(shí)間來解決該問題。

還有一部分源定位方法是基于貪心的策略，通過最大似然估計(jì)來尋找傳播源，但可能會(huì)導(dǎo)致計(jì)算成本較大，并且，這些方法大多沒有考慮到傳播過程中的現(xiàn)實(shí)因素，即謠言的可信度會(huì)隨時(shí)間的推移而進(jìn)行衰減。在現(xiàn)實(shí)世界的社交網(wǎng)絡(luò)中，謠言是具有一定時(shí)效性的。從該角度出發(fā)，可以推斷出一個(gè)謠言如果能夠在網(wǎng)絡(luò)中非常有效地傳播開來，那么它們最可能是一開始就極具影響力的那幾個(gè)節(jié)點(diǎn)。而現(xiàn)有的大部分信息源定位算法沒有考慮這一事實(shí)，影響了對(duì)謠言等有害信息進(jìn)行定位的準(zhǔn)確性。

針對(duì)上述問題，本文定義了節(jié)點(diǎn)激活概率的衰減系數(shù)，已描述謠言的可信度會(huì)隨時(shí)間衰減，在此基礎(chǔ)上，提出了一種獨(dú)立級(jí)聯(lián)模型下基于時(shí)效性的傳播源定位方法。該方法能夠準(zhǔn)確識(shí)別多個(gè)傳播源，使得源定位的結(jié)果更加精確。所提出的算法步驟如下：首先，使用Bayes模型計(jì)算節(jié)點(diǎn)的后驗(yàn)概率，通過迭代來模擬隨機(jī)游走，從而計(jì)算出節(jié)點(diǎn)的影響力，選出候選源集合；然后根據(jù)觀測(cè)節(jié)點(diǎn)的被感染時(shí)間與候選源之間的時(shí)間步長(zhǎng)計(jì)算出它們的信息發(fā)出時(shí)間；最后，將能夠覆蓋觀測(cè)節(jié)點(diǎn)最多的k個(gè)節(jié)點(diǎn)確定為傳播源集合。

本文主要的貢獻(xiàn)和創(chuàng)新點(diǎn)有：

a）在獨(dú)立級(jí)聯(lián)模型下，通過Bayes模型計(jì)算節(jié)點(diǎn)被感染的后驗(yàn)概率，在此基礎(chǔ)上，提出了一種基于時(shí)效性的方法來計(jì)算節(jié)點(diǎn)的影響力，選取影響力較大的節(jié)點(diǎn)作為候選源集合，縮小了尋找源的范圍，降低了算法復(fù)雜度；

b）提出了一種基于感染時(shí)間的源定位算法來定位多個(gè)傳播源，根據(jù)選取的候選源集合，通過觀測(cè)節(jié)點(diǎn)被感染時(shí)間與候選源的時(shí)間差距，計(jì)算出覆蓋觀測(cè)節(jié)點(diǎn)最多的節(jié)點(diǎn)，構(gòu)成傳播源集合，提高了識(shí)別源的準(zhǔn)確性；

c）對(duì)所提的方法在四個(gè)真實(shí)網(wǎng)絡(luò)和三個(gè)合成網(wǎng)絡(luò)上進(jìn)行了實(shí)驗(yàn)，結(jié)果表明，與其余的對(duì)比算法相比，該方法能夠更有效地識(shí)別傳播源，計(jì)算成本也相對(duì)較小。

1 影響力源定位問題

1.1 獨(dú)立級(jí)聯(lián)模型

本文研究在獨(dú)立級(jí)聯(lián)（independent cascade， IC）模型下信息在社交網(wǎng)絡(luò)中的傳播源定位問題。IC模型是一種經(jīng)典的概率傳播模型。在該模型中，每個(gè)節(jié)點(diǎn)在傳播過程中存在感染和未感染兩種狀態(tài)，分別對(duì)應(yīng)網(wǎng)絡(luò)中用戶受到信息影響和未受到影響的狀態(tài)。節(jié)點(diǎn)在未感染狀態(tài)可以受到被感染的鄰居節(jié)點(diǎn)影響轉(zhuǎn)為感染狀態(tài)，而處于感染狀態(tài)的節(jié)點(diǎn)無法轉(zhuǎn)變?yōu)槲锤腥緺顟B(tài)。當(dāng)傳播過程開始時(shí)，所有的傳播源節(jié)點(diǎn)處于感染狀態(tài)，源節(jié)點(diǎn)對(duì)于每個(gè)鄰居節(jié)點(diǎn)，根據(jù)連邊上的傳播概率決定是否被感染，而各個(gè)鄰居被感染的結(jié)果是相互獨(dú)立的。被感染的節(jié)點(diǎn)在下一輪傳播中繼續(xù)感染其鄰居節(jié)點(diǎn)。每個(gè)被感染的節(jié)點(diǎn)有且僅有一次機(jī)會(huì)去感染未被感染的鄰居節(jié)點(diǎn)。重復(fù)上述傳播過程，直到?jīng)]有新的節(jié)點(diǎn)被感染為止。

1.2 傳播源定位問題的定義

傳播網(wǎng)絡(luò)圖可表示為一個(gè)圖G=（V，E，P），其中V表示節(jié)點(diǎn)集合，E表示有向邊集合，G的每條邊（u，e）∈E上分配一個(gè)概率puv∈（0，1），表示影響力從節(jié)點(diǎn)u到鄰居節(jié)點(diǎn)v的傳播概率。在謠言傳輸中，每個(gè)頂點(diǎn)v有未感染（未接受）和被感染（接受并相信謠言）兩種狀態(tài)。未被感染的頂點(diǎn)v轉(zhuǎn)變?yōu)楸桓腥緺顟B(tài)有兩個(gè)條件：一是它收到入-鄰居（in-neighbor）發(fā)來的謠言信息，二是它要相信并接受這個(gè)謠言。

具備第一個(gè)條件的概率可描述為：設(shè)頂點(diǎn)vi處于被感染狀態(tài)的入-鄰居的集合為Γin（vi），設(shè)每個(gè)入-鄰居向vi發(fā)出謠言的概率是相等且互相獨(dú)立的，則vi收到入-鄰居vj發(fā)來的謠言信息的概率為1/|Γin（vi）|。

具備第二個(gè)條件的概率可描述為：在vi收到入-鄰居vj發(fā)來的謠言以后，它相信并接受這個(gè)謠言的概率等于邊（vj，vi）上的概率pij∈（0，1）。

在一個(gè)謠言發(fā)出后，它在網(wǎng)絡(luò)中的傳播具有一定的時(shí)效性，隨著時(shí)間的推移，社會(huì)對(duì)這個(gè)謠言的興趣度會(huì)逐步減弱。另一方面，人們也會(huì)逐步識(shí)破謠言，對(duì)它接受的概率也會(huì)減弱。因此，設(shè)立一個(gè)時(shí)效性衰減系數(shù)γ∈（0，1） ，每過一個(gè)時(shí)間步，用戶接受謠言的概率會(huì)以γ的比例減弱。

設(shè)網(wǎng)絡(luò)G被觀察到的已被感染的頂點(diǎn)集合為O=（o1，o2，…，om），OV，mlt;n=|V|，它們被感染的時(shí)間分別為t1，t2，…，tm。給定一個(gè)正整數(shù)k，傳播源的定位問題就是要求得具有k個(gè)頂點(diǎn)的傳播源集合S，使得S所影響的范圍I（S）最大限度地包含O中的頂點(diǎn)，并且O中的頂點(diǎn)oi被感染的時(shí)間與ti盡可能吻合。

2 基于時(shí)效性的影響力源定位方法

根據(jù)1.2節(jié)中的源定位問題定義，提出了一種基于時(shí)效性的源定位Timeliness-SD算法。該算法首先根據(jù)Bayes模型計(jì)算出節(jié)點(diǎn)被感染的后驗(yàn)概率，通過隨機(jī)游走計(jì)算出節(jié)點(diǎn)的影響力，選出影響力較大的節(jié)點(diǎn)作為候選源集合。然后根據(jù)候選源到觀測(cè)節(jié)點(diǎn)的距離和感染時(shí)間的一致性，選取k個(gè)源節(jié)點(diǎn)集合。

2.1 后驗(yàn)概率的計(jì)算

記vi收到入-鄰居vj發(fā)來的謠言信息的事件為Rj→i，則其概率為

設(shè)立變量Si 表示vi的狀態(tài)：

記p（Si=1|Rj→i）為vi在收到入-鄰居vj發(fā)來的謠言信息后，它被謠言感染的先驗(yàn)概率，顯然p（Si=1|Rj→i）=pji，即邊（vj，vi）上的概率。

為了進(jìn)行謠言源的定位，計(jì)算vi接受入-鄰居vj發(fā)來的謠言的后驗(yàn)概率p（Rj→i|Si=1），即在觀察到vi為感染狀態(tài)時(shí)，vi是因?yàn)榻邮芰巳?鄰居vj發(fā)來的謠言的概率。根據(jù)Bayes模型，有

用圖1所示的網(wǎng)絡(luò)作為示例來說明后驗(yàn)概率的計(jì)算過程。

圖1中s為傳播源，紅色代表被感染節(jié)點(diǎn)，藍(lán)色代表未被感染節(jié)點(diǎn)（見電子版）。以節(jié)點(diǎn)d為例，計(jì)算節(jié)點(diǎn)d被s感染的后驗(yàn)概率。節(jié)點(diǎn)d有兩個(gè)感染節(jié)點(diǎn)的入鄰居，在圖中d被s感染的概率即為（0.23）/（0.75+0.23）=0.234。因此節(jié)點(diǎn)后驗(yàn)概率qsd為0.234。

2.2 基于謠言時(shí)效性的候選傳播源確定

本文的謠言源定位算法分兩步：a）通過考慮謠言時(shí)效性確定候選傳播源；b）通過考慮感染時(shí)間精確地確定謠言傳播源。

首先，通過考慮謠言時(shí)效性確定候選傳播源。設(shè)v∈V為一個(gè)傳播源，u∈O為一個(gè)觀察節(jié)點(diǎn)，u已經(jīng)被感染。記u以v為謠言源被感染的概率為Ru（v）， 選取Ru（v）值大于閾值δ的那些頂點(diǎn)作為u的候選源。記u被v發(fā)出的謠言在t時(shí)刻感染的概率為P（tu=t|s0=v），這里s0=v表示v為感染u的傳播源，則有

對(duì)于頂點(diǎn)u本身，定義

Ru（u）=1（8）

在上式中，γ∈（0，1）為時(shí)效性衰減系數(shù)，每過一個(gè)時(shí)間步，用戶接受謠言的概率會(huì)以γ的比例減弱。記矩陣Q=［qvw］，

Ru=（Ru（v1），Ru（v2），…，Ru（vn））T（9）

為一個(gè)n×1向量，即有式（5）（6）的矩陣表示形式：

Ru=γQRu+Iu（10）

其中：Iu為n維單位向量，u所對(duì)應(yīng)的元素為1，其余元素為0。

然后使用迭代的方法計(jì)算Ru。首先取R（0）u=Iu，然后使用如下的迭代公式：

R（k+1）u= γQR（k）u+Iu（11）

進(jìn)行計(jì)算。即對(duì)于每個(gè)頂點(diǎn)v：

對(duì)于式（12）的迭代涉及到矩陣-向量相乘，需要較大的計(jì)算量。

式（11）和（12）實(shí)際上是通過一個(gè)隨機(jī)游走過程來模擬影響力傳播的過程。在用隨機(jī)游走選擇候選源集合時(shí)，通過被感染的觀測(cè)節(jié)點(diǎn)，計(jì)算出其余節(jié)點(diǎn)的感染后驗(yàn)概率，然后通過反向的隨機(jī)游走，求得觀測(cè)節(jié)點(diǎn)是其余節(jié)點(diǎn)感染的概率，從而將大于閾值的加入集合中。

隨著時(shí)效性的減弱和路徑概率的減小，源節(jié)點(diǎn)通過較長(zhǎng)路徑能夠感染u的概率會(huì)變得很小。因?yàn)閭鞑ヂ窂绞菬o環(huán)的，設(shè)隨機(jī)游走的路徑上沒有重復(fù)的頂點(diǎn)，即路徑的長(zhǎng)度小于n。因此，設(shè)立最大路徑長(zhǎng)度為L(zhǎng)lt;n，即式（12）中的迭代只進(jìn)行L次。此外，考慮到謠言傳播的時(shí)效性，可以僅在u的某一個(gè)鄰域中進(jìn)行對(duì)于式（12）的迭代，而不必在所有的頂點(diǎn)中進(jìn)行。為此，定義m為u的鄰域大小，Γ（u）為所要找的u的鄰域頂點(diǎn)集合，從u的直接入鄰居集合開始，用廣先搜索的方法，不斷擴(kuò)大Γ（u）的范圍。如果Γ（u）中的一個(gè)頂點(diǎn)v的入-鄰居中至少存在一個(gè)頂點(diǎn)不屬于Γ（u），稱v為可擴(kuò)展的，定義可擴(kuò)展集E（u）={v|v∈Γ（u），w∈Γin（v），wΓ（u）}， 用一個(gè)隊(duì)列結(jié)構(gòu)存儲(chǔ)E（u）的元素，逐次由E（u）中的頂點(diǎn)擴(kuò)大Γ（u）的范圍，直到|Γ（u）|=m為止。在確定了Γ（u）以后，只要在Γ（u）中迭代計(jì)算R（u）就可以。對(duì)于每個(gè)頂點(diǎn)v，取初值R（0）u（v）=Iu（v），通過式（12）迭代來計(jì)算R（u）。在通過L次迭代得到各個(gè)頂點(diǎn)的R（L）u（v）值以后，取R（L）u（v）值大于閾值δ的那些頂點(diǎn)作為候選源。具體算法框架如下：

算法1 Candidate-source（u）

輸入：傳播網(wǎng)絡(luò)G=（V，E）；u的鄰域大小m；搜索路徑的最大長(zhǎng)度L；候選源選擇的閾值δ。

輸出：頂點(diǎn)u的候選源集合S（u）。

算法1第2～10行的while循環(huán)執(zhí)行了m次，這里m為u的鄰域大小。設(shè)Dmax為網(wǎng)絡(luò)頂點(diǎn)最大的度，則while循環(huán)的復(fù)雜度為O（Dmax）。算法第11～13行的循環(huán)執(zhí)行O（|V|）次，第14～17行的循環(huán)執(zhí)行O（L）次。因此，算法1的復(fù)雜度為O（Dmax+L+|V|）。由于Dmax和L都小于|V|，所以算法1的時(shí)間復(fù)雜度為O（|V|）。由于隊(duì)列E（u）的長(zhǎng)度小于|V|，算法1的空間復(fù)雜度為O（|V|）。

2.3 基于感染時(shí)間的謠言傳播源定位

O（vi）={o′1，o′2，…，o′m}={o|o∈O，v∈S（o）}（13）

設(shè)o′1，o′2，…，o′g被感染的時(shí)間分別為t′1，t′2，…，t′g，vi到o′1，o′2，…，o′g的距離分別為d1，d2，…，dg。設(shè)信息由頂點(diǎn)vi發(fā)出的時(shí)間為t（tgt;0），感染o′1，o′2，…，o′g的時(shí)間應(yīng)該為d1+t，d2+t，…，dg+t。這里，雖然不知道t的值，但可以知道：

dj+t=t′j" （j=1，2，…，g）（14）

t=t′j－dj" j=1，2，…，g（15）

這說明，若v為o′1，o′2，…，o′g的源，則t′j－dj的值對(duì)于所有的o′j（j=1，2，…，g）都應(yīng)該相同，即皆等于t且大于0。因此，以此來判別v可能是O中哪些頂點(diǎn)的源。

首先，對(duì)O（vi）中的頂點(diǎn)o′1，o′2，…，o′g計(jì)算 Δj=t′j－dj（j=1，2，…，g），去除其中Δj小于0的頂點(diǎn)，再根據(jù)Δj的值將O（vi）中的頂點(diǎn)分為若干類，使得每一類的Δj值都相同。設(shè)得到h個(gè)子集 Ci1，Ci2，…，Cih。記Cj={Ci1，Ci2，…，Cih}。對(duì)于子集Cij，其對(duì)應(yīng)的Δj=t′j－dj即為vi發(fā)出信息的時(shí)間。設(shè)C*i=argmax1≤j≤g|Cij|，然后使用貪心法選擇Scand中使得C*i最大的頂點(diǎn)vi加入到源節(jié)點(diǎn)集合之中。由于vi加入源節(jié)點(diǎn)集合之后，C*i中的觀察節(jié)點(diǎn)已經(jīng)被源頂點(diǎn)vi所覆蓋，所以需要對(duì)其他候選源節(jié)點(diǎn)vj的C*j集合進(jìn)行更新。再在更新后的C*j集中選取新的源節(jié)點(diǎn)。重復(fù)這樣的選擇過程，直到選擇出最大的k個(gè)節(jié)點(diǎn)。算法具體框架如算法2所示。

算法2 Timeliness-SD

輸入：傳播網(wǎng)絡(luò)G=（V，E）；觀察節(jié)點(diǎn)的集合O=（o1，o2，…，om）；觀察節(jié)點(diǎn)t1，t2，…，tm；被感染的時(shí)間o1，o2，…，om。

輸出：源節(jié)點(diǎn)集合S。

算法2第1～3行的while循環(huán)執(zhí)行了m次，這里m為觀察集的大小。算法第5～11行的循環(huán)執(zhí)行O（|Scand|）次，其中第7～11行的子循環(huán)執(zhí)行m次，12～14 行的子循環(huán)最多執(zhí)行Dmax次，這里Dmax為網(wǎng)絡(luò)頂點(diǎn)的最大度。 因此，第5～11行的循環(huán)復(fù)雜度為O（|Scand|×（Dmax+M））。第20～29的循環(huán)復(fù)雜度為（|Scand|×k）。因此，算法2的復(fù)雜度為O（|Scand|×（Dmax+M+k））。由于Dmax、k和m都可以看成常數(shù)，而|Scand|lt;|V|，所以算法2的時(shí)間復(fù)雜度為O（|V|）。由于集合Scand、C、S的大小都不超過|V|，算法2的空間復(fù)雜度為O（|V|）。

在實(shí)時(shí)網(wǎng)絡(luò)檢測(cè)中，若發(fā)現(xiàn)了負(fù)面信息的傳播，可以通過知道感染時(shí)間的節(jié)點(diǎn)，對(duì)其周圍鄰居進(jìn)行分析，構(gòu)建一個(gè)傳播網(wǎng)絡(luò)，對(duì)該網(wǎng)絡(luò)進(jìn)行應(yīng)用。但要注意的是，由于在現(xiàn)實(shí)生活中節(jié)點(diǎn)信息比較復(fù)雜，可以設(shè)置一個(gè)時(shí)間區(qū)間，在一定區(qū)間內(nèi)能干擾到觀測(cè)點(diǎn)的可以視為傳播源集合。

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

為了驗(yàn)證本文算法的有效性，在真實(shí)網(wǎng)絡(luò)和合成網(wǎng)絡(luò)上對(duì)其進(jìn)行了測(cè)試，并將其性能與對(duì)比算法進(jìn)行比較。

3.1 實(shí)驗(yàn)數(shù)據(jù)集和實(shí)驗(yàn)設(shè)置

本文選擇了四個(gè)真實(shí)網(wǎng)絡(luò)（dolphins，football，USAair，F(xiàn)acebook）和三種合成網(wǎng)絡(luò)（ER，WS，BA）進(jìn)行模擬實(shí)驗(yàn)，以驗(yàn)證算法的有效性。

dolphins是一個(gè)描述海豚家族關(guān)系的網(wǎng)絡(luò)。是由Lusseau等人對(duì)棲息在新西蘭Doubtful Sound峽灣的一個(gè)寬吻海豚群體進(jìn)行了長(zhǎng)達(dá)7年的觀察，而構(gòu)造出的海豚關(guān)系網(wǎng)。網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)代表一個(gè)海豚，邊表示兩個(gè)海豚之間接觸頻繁。

football是一個(gè)美國(guó)橄欖球網(wǎng)絡(luò)。在該網(wǎng)絡(luò)中， 每個(gè)節(jié)點(diǎn)代表了參加美國(guó)2000年橄欖球賽季的高校代表隊(duì)，連接兩個(gè)節(jié)點(diǎn)之間的邊則表示相應(yīng)的兩支球隊(duì)之間至少進(jìn)行過一場(chǎng)比賽。

USAair是一個(gè)美國(guó)航班路線網(wǎng)絡(luò)。在該網(wǎng)絡(luò)中，每個(gè)節(jié)點(diǎn)代表一個(gè)機(jī)場(chǎng)，邊表示兩個(gè)機(jī)場(chǎng)之間的航班路線。

Facebook數(shù)據(jù)集由Facebook上的朋友列表組成。網(wǎng)絡(luò)的節(jié)點(diǎn)為用戶，數(shù)據(jù)集將每個(gè)用戶的Facebook內(nèi)部ID替換為一個(gè)新值并將其匿名化。數(shù)據(jù)集包括節(jié)點(diǎn)的特征、社交圈子等。

表1列出了上述4個(gè)真實(shí)網(wǎng)絡(luò)的一些具體信息，如頂點(diǎn)的個(gè)數(shù)（N）、邊的條數(shù)（|E|）和頂點(diǎn)的平均度數(shù)（〈d〉）等。

此外，還用不同的方法生成三種合成網(wǎng)絡(luò)ER、WS和BA。表2列出了三種合成網(wǎng)絡(luò)合成方法的描述。

在實(shí)驗(yàn)中，采用了獨(dú)立級(jí)聯(lián)模型作為影響力傳播模型［26，27］，隨機(jī)選擇一個(gè)或多個(gè)節(jié)點(diǎn)作為傳播源，在該模型下進(jìn)行100次傳播，并在被激活頂點(diǎn)中隨機(jī)選取N個(gè)觀察節(jié)點(diǎn)，記錄它們的激活時(shí)間，然后使用本文算法找到k個(gè)源節(jié)點(diǎn)的集合。算法中的鄰域m設(shè)為20，L設(shè)置為最大的Dijkstra路徑。根據(jù)對(duì)上述數(shù)據(jù)集上多次測(cè)試結(jié)果的分析，將時(shí)間衰減系數(shù)γ設(shè)為0.9，候選源閾值δ設(shè)為0.4。通過如下兩個(gè)指標(biāo)來衡量所提算法的有效性，并與其他一些算法進(jìn)行比較。

a）距離誤差。設(shè) k表示源的個(gè)數(shù)，dk表示所找的源與真實(shí)源之間的最短距離。距離誤差定義為

由上述定義可知，預(yù)測(cè)的源越接近真實(shí)的源，其距離誤差就越短，最理想的情況是如果距離誤差為零，則表示找到了真實(shí)的源。

b）精確度。設(shè)n表示實(shí)驗(yàn)次數(shù)，Nc表示每次實(shí)驗(yàn)時(shí)正確找到真實(shí)源的個(gè)數(shù)，Ns為真實(shí)源的個(gè)數(shù)。精確度的定義如下：

由上述定義可知，精確度越高，表示找到的真實(shí)源的準(zhǔn)確程度就越高。

實(shí)驗(yàn)中的所有算法均使用Python編碼，在CPU為2.90 GHz（6CPUs），內(nèi)存為8 GB，Windows 10操作系統(tǒng)上運(yùn)行。

3.2 對(duì)比算法

使用的對(duì)比算法如下：

a）MLISD［25］算法，通過構(gòu)造傳播圖，再使用最大似然的方法，利用少量觀測(cè)節(jié)點(diǎn)來定位傳播源。

b）RWBA［21］算法，利用Bayes模型，通過有限的觀測(cè)節(jié)點(diǎn)來定位傳播源。

c）Degree算法，根據(jù)網(wǎng)絡(luò)中的節(jié)點(diǎn)度來定位傳播源。

d）MaxLikely［18］算法，利用最大似然來估計(jì)每個(gè)節(jié)點(diǎn)的概率，再通過貪心算法定位傳播源。

3.3 實(shí)驗(yàn)結(jié)果對(duì)比

3.4 平均誤差距離測(cè)試

首先使用真實(shí)源和估計(jì)源之間的平均距離誤差來證明本文方法的準(zhǔn)確性，當(dāng)源節(jié)點(diǎn)為1時(shí)，直接計(jì)算它與估計(jì)源的距離。當(dāng)源節(jié)點(diǎn)個(gè)數(shù)大于1時(shí)，則將每個(gè)真實(shí)源與估計(jì)源之間求最短距離，然后計(jì)算出多源的平均誤差距離。

圖2給出了本文算法在四個(gè)真實(shí)網(wǎng)絡(luò)上的平均誤差距離分布。其中k表示傳播源節(jié)點(diǎn)的數(shù)量；P表示觀測(cè)節(jié)點(diǎn)的占比；frequency表示分布占比，表示在n次實(shí)驗(yàn)過程中，估計(jì)源和真實(shí)源的誤差距離在0～6跳之間的分布情況在總實(shí)驗(yàn)次數(shù)內(nèi)的占比。從圖中可以看出，在dolphins、USAair和Facebook網(wǎng)絡(luò)中，當(dāng)k=5和k=9時(shí)，平均誤差距離都主要分布在0跳和1跳之間，這說明其得到的源與真實(shí)源十分接近。當(dāng)k=1時(shí)，四個(gè)網(wǎng)絡(luò)都在0跳和1跳之間的分布占比都是最大的，其中football網(wǎng)絡(luò)在觀測(cè)節(jié)點(diǎn)占比30%以上時(shí)，誤差距離都基本為0，這說明它的準(zhǔn)確率也相對(duì)較高。當(dāng)源節(jié)點(diǎn)個(gè)數(shù)超過1時(shí)，即當(dāng)k=5和k=9時(shí)，四個(gè)網(wǎng)絡(luò)也基本都分布在0跳和1跳之間，并且隨著觀測(cè)節(jié)點(diǎn)占比的增大，平均誤差距離都在逐漸減小。這也反映了隨著觀察節(jié)點(diǎn)的增加，得到的信息越多，準(zhǔn)確率也會(huì)相對(duì)提高。

圖3給出了本文算法在三個(gè)合成網(wǎng)絡(luò)上的平均誤差距離分布。當(dāng)源節(jié)點(diǎn)為1時(shí)，三個(gè)合成網(wǎng)絡(luò)的誤差距離都為0，這說明相對(duì)應(yīng)的準(zhǔn)確度也相對(duì)較好。當(dāng)k=5和k=9時(shí)，3個(gè)網(wǎng)絡(luò)的平均誤差距離都主要部分在0跳和1跳之間，并且在0跳的分占比是最大的?？梢钥闯?，在ER和WS兩個(gè)網(wǎng)絡(luò)中，誤差距離相對(duì)更小?？偟膩砜矗S著源節(jié)點(diǎn)的增加，三個(gè)網(wǎng)絡(luò)的平均誤差距離都開始出現(xiàn)了誤差距離在1附近的情況，這說明隨著源節(jié)點(diǎn)數(shù)量的增加，導(dǎo)致網(wǎng)絡(luò)中的傳播環(huán)境更復(fù)雜，因此也影響到了尋源的效果。此外，還將平均誤差距離與其余算法進(jìn)行了對(duì)比。

圖4是在真實(shí)網(wǎng)絡(luò)上的平均誤差距離對(duì)比及其置信區(qū)間?？梢钥闯觯疚乃惴ㄔ谌稚系恼`差距離要優(yōu)于其余算法。當(dāng)源節(jié)點(diǎn)k為1時(shí)，在football網(wǎng)絡(luò)中，誤差距離基本為0。隨著觀測(cè)節(jié)點(diǎn)的增加，誤差距離會(huì)趨于減小。圖5是在合成網(wǎng)絡(luò)上的平均誤差距離對(duì)比。明顯可以看出，當(dāng)源節(jié)點(diǎn)k為1時(shí)，3種合成網(wǎng)絡(luò)上的誤差距離都基本為0。當(dāng)k=5和k=9時(shí)，誤差距離也要比其余算法小。

3.5 精確度測(cè)試

本文還對(duì)算法的準(zhǔn)確度進(jìn)行了測(cè)試，并且在真實(shí)網(wǎng)絡(luò)上與其余對(duì)比算法進(jìn)行了比較，其結(jié)果如圖6所示。

從圖6中可以看出，在dolphins、football和USAair網(wǎng)絡(luò)中，當(dāng)源節(jié)點(diǎn)為1時(shí)，TLSD算法全局優(yōu)于其余算法。當(dāng)k=5和k=9時(shí)，在觀測(cè)節(jié)點(diǎn)占比超過0.5后，該算法能夠優(yōu)于其余4種算法。由于本文算法主要與觀測(cè)節(jié)點(diǎn)的信息相關(guān)，所以在觀測(cè)節(jié)點(diǎn)信息少時(shí)，會(huì)導(dǎo)致效果不明顯，但隨著觀測(cè)節(jié)點(diǎn)的占比不斷提高，該算法的準(zhǔn)確度也隨之提高，且優(yōu)于其余四種算法。在相同觀測(cè)節(jié)點(diǎn)的占比情況下可以看出，隨著源節(jié)點(diǎn)數(shù)量k的增加，算法的精確度也會(huì)逐漸降低，但最終都會(huì)優(yōu)于其余算法。

此外，還在三種合成網(wǎng)絡(luò)上進(jìn)行了精確度的對(duì)比測(cè)試，其結(jié)果如圖7所示。TLSD算法在三種合成網(wǎng)絡(luò)上的效果都優(yōu)于其余四種算法，特別是在WS網(wǎng)絡(luò)中，能夠明顯看出精確度優(yōu)于其余算法。隨著觀測(cè)節(jié)點(diǎn)占比增多，TLSD、MLISD和RWBA這三種算法的精確度都會(huì)隨之提高。與其他方法一樣，隨著源節(jié)點(diǎn)的數(shù)量增多，TLSD算法的精確度也會(huì)隨之下降。特別地，當(dāng)源節(jié)點(diǎn)為1時(shí)，TLSD算法與MLISD的精確度基本持平。但從整體上來看，TLSD還是要比其余四種算法效果更好。

3.6 不同衰減系數(shù)下的精確度比較

本文還在football數(shù)據(jù)集上對(duì)不同衰減系數(shù)下的精確度進(jìn)行了測(cè)試和比較。在測(cè)試中，設(shè)k=5和k=9，其結(jié)果如圖8所示。

由圖8可以看出，當(dāng)時(shí)效性衰減系數(shù)增大時(shí)，所取得的源定位結(jié)果的精確度會(huì)提高，這說明了時(shí)效性衰減系數(shù)對(duì)優(yōu)化源定位結(jié)果的重要性。

4 結(jié)束語

在網(wǎng)絡(luò)上會(huì)充斥著各種各樣的謠言，這些謠言可能會(huì)造成公眾恐慌、社會(huì)不穩(wěn)定等，因此要對(duì)這些負(fù)面信息進(jìn)行抑制和堵塞。首先要對(duì)它的源頭進(jìn)行準(zhǔn)確的定位。因此，影響力源定位問題有著重要的現(xiàn)實(shí)意義和應(yīng)用背景。本文針對(duì)該問題提出了基于時(shí)效性的影響力源定位算法TLSD，通過一部分的觀察者信息來推測(cè)出謠言傳播的來源。本文定義了一個(gè)衰減系數(shù)來反映節(jié)點(diǎn)的激活概率隨時(shí)間的衰減速度，通過Bayes模型計(jì)算出頂點(diǎn)被感染的后驗(yàn)概率；然后從被感染的觀測(cè)點(diǎn)出發(fā)，通過隨機(jī)游走計(jì)算所有節(jié)點(diǎn)影響力，選取影響力較大的節(jié)點(diǎn)作為候選源集合；再根據(jù)候選源到觀測(cè)節(jié)點(diǎn)的距離和感染時(shí)間的一致性選取k個(gè)源節(jié)點(diǎn)集合。在真實(shí)和合成網(wǎng)絡(luò)上的實(shí)驗(yàn)結(jié)果表明，該方法能夠準(zhǔn)確識(shí)別多個(gè)傳播源，源定位的結(jié)果在精確度上高于其他類似算法。本文對(duì)有害信息傳播源的定位新方法，可以應(yīng)用到社交網(wǎng)絡(luò)謠言源定位、謠言抑制等問題中，有益于對(duì)社交網(wǎng)絡(luò)中謠言、虛假信息、負(fù)面新聞等的監(jiān)控、抑制。通過找出網(wǎng)絡(luò)中的假消息和謠言的源頭，實(shí)現(xiàn)對(duì)不良信息的精準(zhǔn)打擊，凈化網(wǎng)絡(luò)空間。

雖然本文的研究是基于網(wǎng)絡(luò)SI傳播模型，但所提出的方法也可以應(yīng)用于SIR或SEIR等其他模型。在這些傳播模型上應(yīng)用時(shí)，要考慮到節(jié)點(diǎn)狀態(tài)之間轉(zhuǎn)換的概率，然后要考慮到節(jié)點(diǎn)被首次感染（即轉(zhuǎn)變?yōu)镮狀態(tài)）的時(shí)間。為了反映時(shí)效性的衰減，可以在轉(zhuǎn)換公式中設(shè)置一個(gè)衰減系數(shù)，逐步減少頂點(diǎn)轉(zhuǎn)變?yōu)镮狀態(tài)的概率。此外，還要設(shè)置一個(gè)閾值，信息在經(jīng)過一段時(shí)間后，衰減到閾值下，節(jié)點(diǎn)就不相信該信息，轉(zhuǎn)變?yōu)槠渌麪顟B(tài)。對(duì)于SEIR模型，處于E這種狀態(tài)，可以設(shè)置一個(gè)時(shí)間用于節(jié)點(diǎn)思考，思考過后再?zèng)Q定是否相信。

在實(shí)際的社交網(wǎng)絡(luò)中，存在多種類型謠言在傳播，它們之間有著相互作用，并且人們?cè)诮邮苤{言過程中存在多種狀態(tài)的轉(zhuǎn)變，在該條件下找到其相應(yīng)的源，是一個(gè)具有挑戰(zhàn)性的問題。在未來工作中，將在更為復(fù)雜的傳染病模型下，從時(shí)間因素的角度，對(duì)多類型謠言源的定位問題進(jìn)行研究，找出更符合實(shí)際且精確度高的有效算法。此外，雖然本文研究的問題是考慮到現(xiàn)實(shí)社交網(wǎng)絡(luò)的時(shí)間因素，但現(xiàn)實(shí)生活的謠言傳播更為復(fù)雜，本文所研究的還是在一定的理想情況下，想要應(yīng)用到現(xiàn)實(shí)生活中，還需要考慮更多的節(jié)點(diǎn)屬性信息，這是筆者今后進(jìn)一步研究的方向。

參考文獻(xiàn)：

［1］Zhao Dawei， Wang Lianhai， Wang Zhen， et al. Virus propagation and patch distribution in multiplex networks： modeling， analysis， and optimal allocation ［J］. IEEE Trans on Information Forensics and Security， 2018， 14（7）： 1755-1767.

［2］Feizi S， Médard M， Quon G， et al. Network infusion to infer information sources in networks ［J］. IEEE Trans on Network Science and Engineering， 2018， 6（3）： 402-417.

［3］Doerr B， Fouz M， Friedrich T. Why rumors spread so quickly in social networks ［J］. Communications of the ACM， 2012， 55（6）： 70-75.

［4］Wang Yini， Wen Sheng， Xiang Yang， et al. Modeling the propagation of worms in networks： a survey ［J］. IEEE Communications Surveys amp; Tutorials， 2013， 16（2）： 942-960.

［5］Zhu Peican， Cheng Le， Gao Chao， et al. Locating multi-sources in social networks with a low infection rate ［J］. IEEE Trans on Network Science and Engineering， 2022， 9（3）： 1853-1865.

［6］Wang Zhen， Hou Dongpeng， Gao Chao， et al. A rapid source localization method in the early stage of large-scale network propagation ［C］// Proc of ACM Web Conference 2022. New York： ACM Press， 2022： 1372-1380.

［7］Shah D， Zaman T. Detecting sources of computer viruses in networks： theory and experiment ［C］// Proc of ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems. New York： ACM Press， 2010： 203-214.

［8］Shah D， Zaman T. Rumors in a network： Who’s the culprit？ ［J］. IEEE Trans on Information Theory， 2011， 57（8）： 5163-5181.

［9］Dong Wenxiang， Zhang Wenyi， Tan C W. Rooting out the rumor culprit from suspects ［C］// Proc of IEEE International Symposium on Information Theory. Piscataway， NJ： IEEE Press， 2013： 2671-2675.

［10］Prakash B A， Vreeken J， Faloutsos C. Efficiently spotting the starting points of an epidemic in a large graph ［J］. Knowledge and Information Systems， 2014， 38： 35-59.

［11］Fioriti V， Chinnici M. Predicting the sources of an outbreak with a spectral technique ［EB/OL］. （2012-11-10）.https：//arxiv.org/abs/1211.2333.

［12］Zhu Kai， Ying Lei. Information source detection in the SIR model： a sample-path-based approach ［J］. IEEE/ACM Trans on Networking， 2014， 24（1）： 408-421.

［13］Zhu Kai， Ying Lei. A robust information source estimator with sparse observations ［J］. Computational Social Networks， 2014， 1： 1-21.

［14］Lokhov A Y， Mézard M， Ohta H， et al. Inferring the origin of an epidemic with a dynamic message-passing algorithm ［J］. Physical Review E， 2014， 90（1）： 012801.

［15］Pinto P C， Thiran P， Vetterli M. Locating the source of diffusion in large-scale networks ［J］. Physical Review Letters， 2012， 109（6）： 068702.

［16］Luo Wuqiong， Tay W P， Leng Mei. Identifying infection sources and regions in large networks ［J］. IEEE Trans on Signal Processing， 2013， 61（11）： 2850-2865.

［17］Hakimi S L， Labbé M L， Schmeichel E. The Voronoi partition of a network and its implications in location theory ［J］. ORSA Journal on Computing， 1992， 4（4）： 412-417.

［18］Zang Wenyu， Zhang Peng， Zhou Chuan， et al. Locating multiple sources in social networks under the SIR model： a divide-and-conquer approach ［J］.Journal of Computational Science，2015，10： 278-287.

［19］Ding Yong， Cui Xiaoqing， Wang Huiyong， et al. PRIA： a multi-source recognition method based on partial observation in SIR model ［J］. Mobile Networks and Applications， 2021， 26： 1514-1522.

［20］熊才權(quán)， 古小惠， 吳歆韻. 基于K-shell位置和兩階鄰居的復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)重要性評(píng)估方法 ［J］. 計(jì)算機(jī)應(yīng)用研究， 2023， 40（3）： 738-742. （Xiong Caiquan， Gu Xiaohui， Wu Xinyun. Evaluation method of node importance in complex networks based on K-shell position and neighborhood within two steps ［J］. Application Research of Computers， 2023， 40（3）： 738-742.）

［21］Wang Zheng， Wang Chaokun， Pei Jisheng， et al. Multiple source detection without knowing the underlying propagation model ［C］// Proc of AAAI Conference on Artificial Intelligence.Palo Alto，CA：AAAI Press，2017： 217-223.

［22］Cheng Le， Li Xianghua， Han Zhen， et al. Path-based multi-sources localization in multiplex networks ［J］. Chaos， Solitons amp; Fractals， 2022， 159： 112139.

［23］Zhang Zhijian， Yue Kun， Sun Zhengbao， et al. Locating sources in online social networks via random walk ［C］// Proc of IEEE International Congress on Big Data. Piscataway， NJ：IEEE Press， 2017：337-343.

［24］Ali S S， Anwar T， Rizvi S A M. A revisit to the infection source identification problem under classical graph centrality measures ［J］. Online Social Networks and Media， 2020， 17： 100061.

［25］邵玉， 陳崚， 劉維. 獨(dú)立級(jí)聯(lián)模型下基于最大似然的負(fù)影響力源定位方法 ［J］. 計(jì)算機(jī)科學(xué)， 2022， 49（2）： 204-215. （Shao Yu， Chen Ling， Liu Wei. Maximum likelihood-based method for locating source of negative influence spreading under independent cascade model ［J］. Computer Science， 2022， 49（2）： 204-215.）

［26］Chen Wei， Wang Yajun， Yang Siyu. Efficient influence maximization in social networks ［C］// Proc of the 15th ACM SIGKDD Internatio-nal Conference on Knowledge Discovery and Data Mining. New York： ACM Press， 2009： 199-208.

［27］Tang Youze， Xiao Xiaokui， Shi Yanchen. Influence maximization： near-optimal time complexity meets practical efficiency ［C］// Proc of ACM SIGMOD International Conference on Management of Data. New York： ACM Press， 2014： 75-86.