周中月,張海軍,潘偉民

(新疆師范大學計算機科學技術(shù)學院,新疆 烏魯木齊 830054)

0 引 言

社交網(wǎng)絡平臺(Social Network Platform)通常是人們分享信息、意見，進行推薦和交流的載體，同時社交網(wǎng)絡也是一個典型的復雜網(wǎng)絡[1]。社交媒體渠道允許用戶建立各種顯性或隱性的社交關(guān)系，利用網(wǎng)絡作為溝通世界的平臺，無論是知名人士、媒體官方賬號還是普通用戶都能以自己的觀點去發(fā)表評價和意見，在這些開放性的評論、轉(zhuǎn)發(fā)平臺上，評估信息的真實性比在傳統(tǒng)媒體中更具有挑戰(zhàn)性。

目前，謠言源的研究工作多基于部署觀察點進行展示，相對于傳播子圖快照的方法，部署觀察點的方法不用獲取整個網(wǎng)絡狀態(tài)，只需要部署少量的觀測點來統(tǒng)計鄰居節(jié)點狀態(tài)，然后進行謠言源的估計，在實際應用中的可行性更高。通常，觀測點位置和數(shù)量的選取往往影響到檢測結(jié)果。

以往的研究工作中選取原則多是基于謠言中心性特征，并沒有考慮到網(wǎng)絡邊節(jié)點權(quán)值屬性。少數(shù)考慮邊節(jié)點權(quán)值的方法是隨機賦權(quán)法，該方法雖然考慮到節(jié)點權(quán)值這項重要參數(shù)，但隨機賦權(quán)并不能很好地表示出網(wǎng)絡結(jié)構(gòu)的真實性。

本文將權(quán)值作為一項重要參數(shù)引入謠言源識別工作中，并且使用4個真實網(wǎng)絡數(shù)據(jù)集基于SIR傳染病模型進行仿真實驗，分析比較本文所提出的基于SIR模型的客觀賦權(quán)算法與其他算法在謠言源估計準確率、平均誤差距離等方面的優(yōu)越性。實驗結(jié)果表明，本文提出的改進算法檢測謠言源的準確率更高，且誤差距離大部分都控制在幾跳之內(nèi)。

1 相關(guān)工作

近年來，隨著社交網(wǎng)絡的廣泛應用，謠言源識別工作引起了人們廣泛的關(guān)注和研究。對謠言傳播建模的研究工作始于20世紀60年代[2]，Sudbury等人[3]根據(jù)謠言傳播的特征，引入基于數(shù)學統(tǒng)計的宏觀模型即傳染病模型用于謠言的檢測工作的研究。

Shah等人[4]基于計算機病毒來源的問題，提出了謠言中心性理論，根據(jù)網(wǎng)絡中觀察到的感染節(jié)點所組成的傳播子圖來計算感染路徑條數(shù)，并建立似然函數(shù)。最后，計算最大似然函數(shù)估計值，估計值最高的為信息源點。并且通過仿真實驗表明了相對于距離中心，該方法表現(xiàn)更好。

謠言中心性可以網(wǎng)絡表示為G(V，E)，其中G表示整個網(wǎng)絡，V表示網(wǎng)絡中的節(jié)點集，E則表示網(wǎng)絡中的邊集。文獻[5]構(gòu)建了一個最大后驗(MAP)估計器，并提出了局部謠言中心性(Local Rumor Centrality)的概念，針對SI模型進行單謠言源的檢測問題，通過實驗分析了謠言傳播過程。謠言中心性公式如式(1):

(1)

謠言中心性的提出奠定了后續(xù)謠言溯源工作的研究基礎(chǔ)。Zhu等人[6]提出了一種基于SIR模型的樣本路徑算法，并且利用反向傳播算法(RI)計算圖中傳染源的估計量。后期的研究，多數(shù)是通過部署觀察點的方法獲得網(wǎng)絡節(jié)點傳播狀態(tài)，該方法可以避免獲取所有的網(wǎng)絡節(jié)點的信息，適用于大型網(wǎng)絡。Pinto等人[7]提出了一個定位傳播源的總體框架，在這個框架中，選擇網(wǎng)絡中一部分的節(jié)點作為觀察者，基于高斯定位法計算概率最大的節(jié)點并視為謠言源。

總的來說，部署觀察點的方法減少了計算復雜度，通過統(tǒng)計觀察點的反饋信息，進行謠言源的估計在實際應用中的可行性更高。但是，在實際網(wǎng)絡中如何更合理地選擇觀察點提升算法的準確性和有效性具有一定的研究難度。部署觀測點算法的樣例圖如圖1所示。在謠言傳播網(wǎng)絡圖G中，在時間t(t∈t*)時圖中存在O1、O2、O3、O4這4個觀察點，其觀察點的主要作用是統(tǒng)計傳播情況，根據(jù)觀察點反饋情況進行預測信息源點。

圖1 部署觀察點的網(wǎng)絡關(guān)系圖

綜上，謠言中心性理論的提出，對后續(xù)的謠言源識別研究起到了推動的作用，且研究中所提出的許多論斷對后續(xù)的謠言溯源工作具有重要的參考價值。但是，在現(xiàn)實情況中，很難一次觀察到整個網(wǎng)絡的結(jié)構(gòu)狀態(tài)，且可能存在部分感染點未被表達出來，或者表達出來的一些感染節(jié)點并不一定是真實的感染節(jié)點，對于大型網(wǎng)絡來說，具有一定的局限性。

因此，本文著重考慮網(wǎng)絡節(jié)點的重要程度，并使用熵權(quán)算法進行節(jié)點權(quán)值的計算。相對于已有的研究方法，該策略可以通過節(jié)點權(quán)值的不同，優(yōu)化觀察點數(shù)量，最后使用似然估計算法進行源點預測，相對于傳統(tǒng)的謠言源檢測算法，該方法減少了時間復雜度，提升了預測謠言源的準確性。

2 一種融入客觀賦權(quán)法的謠言源檢測算法

基于已有的研究工作，本文將網(wǎng)絡形式化表示為G=(V，E，Wij)，其中節(jié)點v∈V表示網(wǎng)絡中的用戶節(jié)點，邊e∈E表示是網(wǎng)絡節(jié)點之間的關(guān)系，且i,j∈V，w∈W表示所求的權(quán)重。每個節(jié)點代表社會網(wǎng)絡中的某一個用戶，每條邊對應2個用戶之間的社會聯(lián)系。信息在s(s∈V)所表示的未知源從G中以異步的方式進行傳播。

通常，在現(xiàn)實網(wǎng)絡中，用戶之間的影響力往往是不同的，如微博中某明星、網(wǎng)絡紅人、直播達人等。相比較而言，他們的權(quán)重指標是高于普通用戶的，所以隨機賦予權(quán)重的方法并不能很好地表示出節(jié)點之間的強度關(guān)系。

因此，本文采用一種改進的網(wǎng)絡節(jié)點權(quán)值算法，首先將整個網(wǎng)絡數(shù)據(jù)矩陣化，表示為0、1矩陣，0表示2個節(jié)點沒有聯(lián)系，1則表示2個加點存在某種聯(lián)系，并求出網(wǎng)絡節(jié)點的4個代表屬性值，即度數(shù)、介數(shù)、緊密度及特征向量，將其4個屬性表示為一個特征集合，然后使用經(jīng)典的客觀賦權(quán)算法熵權(quán)法來計算節(jié)點權(quán)值。最后，將改進的網(wǎng)絡節(jié)點權(quán)值作為一項重要特征用于謠言源預測，提高謠言源檢測效果。其算法整體流程如圖2所示。

圖2 融入客觀賦權(quán)算法模型的謠言源識別流程

2.1 熵權(quán)法確定客觀權(quán)值

為了避免對于網(wǎng)絡節(jié)點進行隨機賦權(quán)所出現(xiàn)的偏差等現(xiàn)象，本文采用的客觀賦權(quán)算法熵權(quán)法的基本思想是根據(jù)數(shù)值之間不同的指標變化來確定，計算過程及分析完全依靠數(shù)值參數(shù)，并沒有人的主觀意識，所以熵權(quán)法屬于一種客觀賦值的方法。其計算過程如下：

根據(jù)信息論中的信息熵定義，一組數(shù)據(jù)的信息熵可表示為：

(2)

(3)

其中，x是指標值，min(x)是x的最小值，max(x)是x的最大值。

2.2 融入客觀賦權(quán)算法謠言源識別模型

在現(xiàn)實網(wǎng)絡中，用戶與用戶之間的影響力是不同的，隨機賦權(quán)算法[8]并不能充分地體現(xiàn)網(wǎng)絡中的真實情況，限制了算法的性能。為了避免這個問題的發(fā)生，本文選取基于謠言中心性的4個代表屬性，利用熵權(quán)算法為網(wǎng)絡邊節(jié)點分配更合理的權(quán)值，從而提升謠言源檢測算法的準確性。

2.2.1 基于熵權(quán)算法的網(wǎng)絡節(jié)點權(quán)值計算

考慮到節(jié)點權(quán)重對于謠言源檢測結(jié)果準確性可能帶來的影響，本文使用客觀賦權(quán)算法熵權(quán)法策略來計算節(jié)點權(quán)值，避免了隨機賦權(quán)帶來的不確定性，以便于更加真實地體現(xiàn)網(wǎng)絡結(jié)構(gòu)屬性。具體操作步驟如下:

Step1特征屬性提取。

在謠言源的研究工作中，通常認為網(wǎng)絡中影響力越大的節(jié)點在信息傳播過程中接受謠言信息的可能性越大。中心性則是度量網(wǎng)絡節(jié)點重要程度的一個有效指標[2,9]，主要包括：

1)度中心性[10](Degree Centrality)。節(jié)點之間發(fā)生直接聯(lián)系，那么這個節(jié)點就處于中心地位。節(jié)點i的計算公式為:

(4)

2)介數(shù)中心性[11](Betweenness Centrality)。又稱為間接中心性，表示節(jié)點之間的接近程度。其公式為:

(5)

3)緊密中心性[12](Closeness Centrality)。主要關(guān)注網(wǎng)絡中平均距離的變化，與其它中心性不同的是，緊密中心性中，若一個節(jié)點的平均距離(di)越小，那么該節(jié)點的緊密中心性則越大,因此計算中取其倒數(shù)。距離計算公式為:

(6)

其中,n表示從節(jié)點v出發(fā)在網(wǎng)絡中連通部分V的大小。

4)特征向量中心性[13](eigenvector centrality, EC)。網(wǎng)絡節(jié)點的重要既取決于鄰居節(jié)點的數(shù)量，也取決于鄰居節(jié)點的重要程度。將單個節(jié)點的聲望看成是所有其鄰居節(jié)點聲望的線性組合，從而得到一個線性方程組。記Ei為節(jié)點vi的特征向量，其公式表示為:

(7)

其中，c為比例常數(shù)，記E=[E1,E2,E3,…,En],經(jīng)過多次迭代到穩(wěn)定狀態(tài)時可以寫成E=cAE，表示E是矩陣A的特征值對應的特征向量。

綜上，首先對數(shù)據(jù)集建立關(guān)系矩陣，即節(jié)點之間存在聯(lián)系記為1，不存在聯(lián)系則為0，然后使用UCINET工具統(tǒng)計計算出網(wǎng)絡節(jié)點所對應的4個屬性特征值，并將其組合成為一個新的集合定義為Xi,i∈N。

Step2屬性歸一化。

將各個指標數(shù)據(jù)進行歸一化處理，令Xi={x1，x2，x3，x4},指標標準化之后表示為Y1、Y2、Y3、Y4，其公式表示為：

(8)

Step3信息熵的表示。

基于2.1節(jié)中信息熵的定義，將4個屬性指標的信息熵分別表示為E1、E2、E3、E4。

Step4權(quán)值計算。

經(jīng)過上述步驟處理，使用公式(9)計算出最終權(quán)值結(jié)果為：

(9)

其中，m表示特征屬性的個數(shù)。

2.2.2 源點預測

(10)

其中，ρ(GI|v)是在傳播模型SIR下所觀察到GI的概率，假設(shè)v∈v*,因此，只要求出所有的v∈GI中ρ(GI|v)的似然函數(shù)值，然后選擇其中值最大的一個判定其為謠言源點。

3 實驗和分析

本實驗基于Python3.6和Pycharm平臺進行仿真實現(xiàn)，權(quán)值矩陣化部分使用UCINET工具。為保證實驗的準確性和真實性，本文將實驗獨立運行50次，統(tǒng)計預測的值C與真實的源之間重合的次數(shù)，之后除以總數(shù)N，即得到正確預測的概率R。為了更好地表述，接下來將融入客觀賦權(quán)法的謠言源檢測算法，簡稱為BEW(Betweenness Weight)，同時，為保證實驗的可行性，本文與以下模型進行對比：

1)隨機賦權(quán)(Random Weight，Random-W)[8]算法模型。該方法主要是基于SI傳染病模型，其邊緣權(quán)值隨機變化，該算法利用社會網(wǎng)絡的模塊化特性，以較少的傳感器節(jié)點來定位謠言的來源，并通過仿真實驗驗證了算法的可行性，且誤差距離在2跳以內(nèi)的占比80%左右。

2)緊密中心性(Closeness Centrality, CC)算法模型。該方法是采用緊密中心性特征作為主要特征，緊密中心性反應網(wǎng)絡中某一個點與其他節(jié)點的接近程度，該方法屬于中心性啟發(fā)式算法，常被用于謠言源檢測任務。

為了更好地驗證算法可行性，對于源點預測任務，本文采用在研究中普遍使用的估計器和源點之間的誤差距離(Error Distances)以及平均誤差2個指標，其中誤差距離表示被檢測源與實際源之間的跳數(shù)(跳數(shù)形容節(jié)點之間是否存在直接聯(lián)系)。

3.1 數(shù)據(jù)集

為了保證研究更貼近真實性，選取4個不同的真實網(wǎng)絡拓撲數(shù)據(jù)集進行仿真實驗。其數(shù)據(jù)集的詳情如表1所示。

表1 數(shù)據(jù)集

3.2 實驗結(jié)果與分析

在算法實現(xiàn)過程中，將恢復概率設(shè)置得盡可能的小，而傳播時間讓其更長，以便于有更多的感染源進行分析。誤差距離是評價檢測算法準確性的一項重要指標，在判斷謠言源識別算法的可行性方面被廣泛使用，誤差距離越小表示算法的性能越高。0跳代表預測源與實際源相同，表示溯源成功，1跳則表示預測源與實際源存在直接的鄰居關(guān)系，以此類推。并在4種不同規(guī)模的真實網(wǎng)絡進行了仿真實驗，誤差距離圖如圖3～圖6所示。

圖3 Karate誤差距離圖

Karate網(wǎng)絡表示34名成員之間的聯(lián)系，該網(wǎng)絡是由34個節(jié)點和78條邊組成，常用于社交網(wǎng)絡分析研究。根據(jù)圖3所示，本文所提出的融入客觀權(quán)值的BEW算法的準確率接近20%，高于CC算法和Random-W算法，且在BEW算法中近90%的估計器和源點誤差的距離保持在2跳之內(nèi)。

圖4表示的是足球比賽網(wǎng)絡，該網(wǎng)絡是由115個節(jié)點和613條邊所組成，從圖中可以看出，雖然BEW算法在2跳之內(nèi)的占比不是特別高，但是相對于CC算法和Random-W算法，BEW算法的準確率較高，達到14%左右，而另外2種算法中準確率較高的Random-W也只有近8%。且BEW算法中，節(jié)點誤差距離保持在1跳內(nèi)的占比高于Random-W算法和CC算法。

圖4 Football誤差距離圖

圖5表示的是Facebook網(wǎng)絡，該網(wǎng)絡相比較前2種網(wǎng)絡，其網(wǎng)絡規(guī)模更大，結(jié)構(gòu)也相對復雜。從圖5中可以看出，融入客觀權(quán)值的BEW算法的準確率近30%，而其他2種算法中準確率較高的Random-W算法還未達到20%，且本文所提出的BEW算法誤差距離保持在2跳之內(nèi)的概率占到96%，其他2種算法誤差在2跳之內(nèi)的占比是低于該算法的。

圖5 Facebook誤差距離圖

圖6表示的是維基百科投票網(wǎng)絡，該網(wǎng)絡由7115個節(jié)點和103689條邊所組成。從圖6中可以看出BEW算法在準確率方法同樣高于CC和Random-W算法，且BEW算法在誤差距離為1跳內(nèi)的占比高于另外2種算法。

圖6 Wiki誤差距離圖

圖7表示的是3種算法在不同網(wǎng)絡拓撲中的平均誤差表現(xiàn)。為了可以更好地表示算法的可行性，本文將不同網(wǎng)絡的平均誤差進行了分析。從圖7中可以看出，融入客觀賦值算法BEW在4個網(wǎng)絡的表現(xiàn)中都優(yōu)于CC算法和Random-W算法，Karate網(wǎng)絡和Facebook網(wǎng)絡產(chǎn)生的平均誤差距離保持在1.4跳左右，F(xiàn)ootball網(wǎng)絡和Wiki網(wǎng)絡所產(chǎn)生的平均誤差也是低于其他2種算法。

圖7 不同網(wǎng)絡拓撲之間的平均誤差距離

通過仿真實驗可以看出，融入客觀賦權(quán)算法模型在謠言源檢測的準確率方面高于其他2種算法，且誤差距離多數(shù)保持在2跳以內(nèi)。同時，在4個不同的真實數(shù)據(jù)集中，相對另外2種算法，BEW算法預測的準確度整體都是較高的，且平均誤差低于CC算法和Random-W算法。

4 結(jié)束語

本文研究了基于SIR傳染病模型的謠言源檢測方法，提出了一種融合客觀賦權(quán)算法的謠言源檢測模型，與隨機賦權(quán)方法相比，本文對網(wǎng)絡結(jié)構(gòu)的表示更加合理，預測結(jié)果更加有效和精確。目前，隨著社交網(wǎng)絡的不斷發(fā)展，其網(wǎng)絡規(guī)模也變的越來越復雜，因此，下一步的研究工作重點將放在大型動態(tài)網(wǎng)絡方面，從而更好地解決謠言源識別問題。