融合客觀賦權(quán)法的社交網(wǎng)絡(luò)謠言源檢測(cè)算法

周中月,張海軍,潘偉民

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

0 引 言

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

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

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

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

1 相關(guān)工作

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

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

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

(1)

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

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

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

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

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

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

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

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

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

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

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

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

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

(2)

(3)

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

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

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

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

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

Step1特征屬性提取。

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

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

(4)

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

(5)

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

(6)

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

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

(7)

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

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

Step2屬性歸一化。

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

(8)

Step3信息熵的表示。

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

Step4權(quán)值計(jì)算。

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

(9)

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

2.2.2 源點(diǎn)預(yù)測(cè)

(10)

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

3 實(shí)驗(yàn)和分析

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

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

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

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

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

為了保證研究更貼近真實(shí)性，選取4個(gè)不同的真實(shí)網(wǎng)絡(luò)拓?fù)鋽?shù)據(jù)集進(jìn)行仿真實(shí)驗(yàn)。其數(shù)據(jù)集的詳情如表1所示。

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

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

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

圖3 Karate誤差距離圖

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

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

圖4 Football誤差距離圖

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

圖5 Facebook誤差距離圖

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

圖6 Wiki誤差距離圖

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

圖7 不同網(wǎng)絡(luò)拓?fù)渲g的平均誤差距離

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

4 結(jié)束語(yǔ)

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