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

關鍵詞：社交網(wǎng)絡；獨立級聯(lián)傳播模型；影響力傳播；感染時間；傳播源定位

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

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

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

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

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

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

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

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

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

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

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

1 影響力源定位問題

1.1 獨立級聯(lián)模型

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

1.2 傳播源定位問題的定義

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

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

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

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

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

2 基于時效性的影響力源定位方法

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

2.1 后驗概率的計算

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

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

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

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

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

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

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

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

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

對于頂點u本身，定義

Ru（u）=1（8）

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

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

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

Ru=γQRu+Iu（10）

其中：Iu為n維單位向量，u所對應的元素為1，其余元素為0。

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

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

進行計算。即對于每個頂點v：

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

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

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

算法1 Candidate-source（u）

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

輸出：頂點u的候選源集合S（u）。

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

2.3 基于感染時間的謠言傳播源定位

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

設o′1，o′2，…，o′g被感染的時間分別為t′1，t′2，…，t′g，vi到o′1，o′2，…，o′g的距離分別為d1，d2，…，dg。設信息由頂點vi發(fā)出的時間為t（tgt;0），感染o′1，o′2，…，o′g的時間應該為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的值對于所有的o′j（j=1，2，…，g）都應該相同，即皆等于t且大于0。因此，以此來判別v可能是O中哪些頂點的源。

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

算法2 Timeliness-SD

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

輸出：源節(jié)點集合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)絡頂點的最大度。 因此，第5～11行的循環(huán)復雜度為O（|Scand|×（Dmax+M））。第20～29的循環(huán)復雜度為（|Scand|×k）。因此，算法2的復雜度為O（|Scand|×（Dmax+M+k））。由于Dmax、k和m都可以看成常數(shù)，而|Scand|lt;|V|，所以算法2的時間復雜度為O（|V|）。由于集合Scand、C、S的大小都不超過|V|，算法2的空間復雜度為O（|V|）。

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

3 實驗結果分析

為了驗證本文算法的有效性，在真實網(wǎng)絡和合成網(wǎng)絡上對其進行了測試，并將其性能與對比算法進行比較。

3.1 實驗數(shù)據(jù)集和實驗設置

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

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

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

USAair是一個美國航班路線網(wǎng)絡。在該網(wǎng)絡中，每個節(jié)點代表一個機場，邊表示兩個機場之間的航班路線。

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

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

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

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

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

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

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

由上述定義可知，精確度越高，表示找到的真實源的準確程度就越高。

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

3.2 對比算法

使用的對比算法如下：

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

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

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

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

3.3 實驗結果對比

3.4 平均誤差距離測試

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

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

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

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

3.5 精確度測試

本文還對算法的準確度進行了測試，并且在真實網(wǎng)絡上與其余對比算法進行了比較，其結果如圖6所示。

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

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

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

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

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

4 結束語

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

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

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

參考文獻：

［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］熊才權， 古小惠， 吳歆韻. 基于K-shell位置和兩階鄰居的復雜網(wǎng)絡節(jié)點重要性評估方法 ［J］. 計算機應用研究， 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］邵玉， 陳崚， 劉維. 獨立級聯(lián)模型下基于最大似然的負影響力源定位方法 ［J］. 計算機科學， 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.