廖 藝，王友國，朱 亮

(1.南京郵電大學(xué) 理學(xué)院，江蘇 南京 210046；2.南京郵電大學(xué) 通信與信息工程學(xué)院，江蘇 南京 210003)

0 引 言

隨著信息技術(shù)的不斷發(fā)展，人類社會已經(jīng)全面步入在線社交網(wǎng)絡(luò)時代。社交網(wǎng)絡(luò)為人與人之間的信息交流提供了絕佳渠道，并成為生活中不可缺少的一部分。社交網(wǎng)絡(luò)的產(chǎn)生使用戶具有雙重角色，既是信息的“消費(fèi)者”，更是信息的“生產(chǎn)者”。在社交網(wǎng)絡(luò)大環(huán)境影響下，信息的來源、傳播速度、傳播范圍以及影響力都大幅增加[1-2]。對社交網(wǎng)絡(luò)上信息擴(kuò)散過程的研究、分析及控制已然成為復(fù)雜網(wǎng)絡(luò)領(lǐng)域的研究熱點之一[3-4]。但是，社交網(wǎng)絡(luò)的飛速發(fā)展也是一把雙刃劍。謠言在社交網(wǎng)絡(luò)上的肆意傳播，會給社會帶來嚴(yán)重的危害，造成社會恐慌，影響社會穩(wěn)定。如何快速及時有效地遏制網(wǎng)絡(luò)上謠言的肆意傳播顯得尤為重要[5]。

謠言溯源便是最為直接有效的方式之一。謠言溯源問題最終目的是通過信息溯源，從根源上及時有效地遏制謠言的傳播，防止其造成社會不良影響。謠言溯源是在獲得某些信息的前提下，如節(jié)點狀態(tài)、網(wǎng)絡(luò)拓?fù)湫畔?、潛在的傳播機(jī)制等，構(gòu)造源節(jié)點估計量，最大化謠言源檢測概率[6]。但是，這類問題的精確解已被證明是N-P難題。除此之外，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的復(fù)雜性、傳播過程的動態(tài)性、計算的可行性都給謠言溯源問題帶來了巨大的挑戰(zhàn)[7]。

針對單信源溯源問題，Shah和Zaman[8]在謠言傳播服從正則樹上的SI模型時，提出了謠言中心性，基于可能的傳播路徑數(shù)構(gòu)造出極大似然估計量，并證明在一般樹圖下正確檢測概率大于零，在幾何樹圖中且傳播時間t→∞時，算法準(zhǔn)確率趨于1；Zhu等人[9]提出Jordan中心，即距離所有感染節(jié)點距離最大值是最小的節(jié)點，用于解決SIR模型下單信源溯源問題。實驗證實，在樹型網(wǎng)絡(luò)下，Jordan感染中心與真實源節(jié)點的距離以高概率小于一個常數(shù)；Comin等人[10]對比感染圖與原始網(wǎng)絡(luò)，在中介中心性的基礎(chǔ)上，去除節(jié)點度的偏差，提出了無偏中介中心性，實驗表明在雪崩傳播模型下，無偏中介中心性表現(xiàn)最好。

針對多信源溯源問題，F(xiàn)ioriti等人[11]根據(jù)謠言源是加入感染網(wǎng)絡(luò)時間最早的節(jié)點提出動態(tài)年齡算法(DA算法)，該算法通過計算去除每個節(jié)點后，網(wǎng)絡(luò)鄰接矩陣最大特征值的下降量，下降量與該節(jié)點年齡成正比，經(jīng)過真實網(wǎng)絡(luò)的模擬實驗，DA算法表現(xiàn)優(yōu)異；Luo等人[12]借鑒Shah等人的思路，提出MSEP(multiple sources estimation and partitioning)算法，用于識別網(wǎng)絡(luò)中的感染源和感染區(qū)域，此外，Luo[13]對于SI模型中節(jié)點的顯式狀態(tài)和隱式狀態(tài)的多源問題，提出了多Jordan中心(multiple Jordan center estimation，MJC)算法對其求解；Zang等人[14]將無偏中介中心性推廣到只包含部分節(jié)點快照的SIR傳播模型的多源問題，提出了AUB(advanced unbiased betweenness)算法，該算法通過模塊度將多源問題轉(zhuǎn)化為多個單源問題，并以無偏中介中心性尋找謠言源。

該文在已有研究的基礎(chǔ)上，考慮基于譜優(yōu)化的模塊度社區(qū)劃分算法，將雙信源感染子圖劃分為兩個社區(qū)，并在各個社區(qū)內(nèi)進(jìn)行基于謠言中心的單信源估計，最后在不同網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)上進(jìn)行仿真與分析，同時與基于接近中心性、距離中心性和Jordan中心的啟發(fā)式估計器進(jìn)行對比。

1 基于譜優(yōu)化的社區(qū)劃分算法

1.1 模塊度

在真實的社交網(wǎng)絡(luò)中，普遍存在著一個共同的性質(zhì)：同組的組內(nèi)節(jié)點間相似性較大，異組的節(jié)點相似性較小，即社區(qū)結(jié)構(gòu)[15]。2004年，Newman[16]提出了模塊度(modularity)的概念，用來度量網(wǎng)絡(luò)中社區(qū)劃分精度和優(yōu)劣。這種效益函數(shù)等價于社區(qū)內(nèi)的實際邊數(shù)與其期望數(shù)之差，模塊度越大表示越強(qiáng)的社區(qū)結(jié)構(gòu)，即社區(qū)劃分算法效果越好。由于存在太多的劃分，各種近似優(yōu)化算法被證明是有效的[17-18]。如圖1所示，通過感染快照和網(wǎng)絡(luò)結(jié)構(gòu)，對雙信源感染圖進(jìn)行社區(qū)劃分。

圖1 雙信源社區(qū)劃分示意圖

(1)

1.2 基于譜優(yōu)化的模塊度矩陣

Newman[19]對模塊度做了進(jìn)一步研究，結(jié)合譜分析法來優(yōu)化社區(qū)劃分算法。譜分析法[20]是利用拉普拉斯矩陣的特征向量將連接緊密的節(jié)點劃分到一個社區(qū)，實對稱矩陣的非退化特征值所對應(yīng)的特征向量總是正交的，所以非零特征值對應(yīng)的特征向量中總是包含正負(fù)兩種元素，正負(fù)元素所對相應(yīng)的節(jié)點可劃分到不同的社區(qū)。對比傳統(tǒng)社區(qū)劃分算法，譜分析法不易陷入局部最優(yōu)解，當(dāng)網(wǎng)絡(luò)被劃分成兩個社區(qū)時，社區(qū)劃分效果好，運(yùn)算速度快[21]。

定義1：s是一個含有n個元素的索引向量，則有

(2)

通過索引向量s，將模塊度Q改寫為矩陣形式：

(3)

Bij=Aij-Pij

(4)

(5)

(6)

綜上所述，得到基于譜分析的模塊度社區(qū)劃分算法：通過計算模塊度矩陣B主特征向量來獲得最優(yōu)s，根據(jù)元素s的正負(fù)得到劃分的兩個社區(qū)。

2 謠言溯源

2.1 謠言傳播模型

在SI模型中，每個節(jié)點可能處于兩種狀態(tài)之一：易感染(S)和已感染(I)。在任意時刻，一旦一個節(jié)點被感染，則在整個傳播過程中一直維持已感染狀態(tài)且具備傳染能力，周圍有聯(lián)系的鄰居節(jié)點將會處于易感染狀態(tài)，而每個易感染節(jié)點在下一時刻會被概率性感染。

2.2 源估計量和謠言中心

假設(shè)在無向網(wǎng)絡(luò)G=(V,E)中初始謠言源v*∈V，在某個時間點觀察到N個被感染節(jié)點的感染子圖，記為GN。假設(shè)源節(jié)點在感染子圖GN的所有節(jié)點之間具有統(tǒng)一的先驗概率。根據(jù)感染子圖GN和網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，為了使正確檢測概率最大化，得到如下的極大似然估計量。

(7)

其中，PG(GN|v)是以v為謠言源觀測到感染子圖為GN的概率。

在正則樹中，節(jié)點v是謠言源的概率與該節(jié)點所有可能的傳播路徑數(shù)成正比，那么，

(8)

其中，R(v,GN)表示在傳播過程中感染圖GN中所有節(jié)點的所有可能被感染順序的計數(shù)，即謠言中心性(rumor centrality)。網(wǎng)絡(luò)的謠言中心是具有最大謠言中心性的節(jié)點。

在正則樹上，網(wǎng)絡(luò)的謠言中心是謠言源的極大似然估計，即使在一般樹上，謠言中心與極大似然估計量沒有顯著差別[8]。因此，在樹形網(wǎng)絡(luò)中，節(jié)點v的謠言中心性表達(dá)式為：

(9)

(10)

其中，TBFS(v)是GN中以節(jié)點v為根節(jié)點按照寬度優(yōu)先搜索的排列。

2.3 基于譜優(yōu)化社區(qū)劃分的雙信源溯源算法

算法的整體流程如圖2所示。

3 仿真與分析

通過分析不同估計量在不同網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)下的正確檢測概率和平均錯誤距離來評估該算法的檢測性能和優(yōu)劣。正確檢測概率表示實驗中正確識別謠言源的比例，平均誤差距離表示估計謠言源與實際謠言源之間的平均距離。在仿真實驗之前，對所需估計量和定義進(jìn)行相應(yīng)的描述。

(1)接近中心性(closeness center，cc)。

(11)

(2)距離中心性(distance center，dc)。

(12)

(3)Jordan中心(Jordan center，jc)。

(13)

圖2 基于譜分析社區(qū)劃分的雙信源溯源算法流程

為減小隨機(jī)誤差，對所有的仿真實驗進(jìn)行10 000次的蒙特卡洛模擬。具體而言，在網(wǎng)絡(luò)規(guī)模為1 000、平均節(jié)點度為3的規(guī)則樹，平均節(jié)點度[1,10]的隨機(jī)樹，平均節(jié)點度為12的BA無標(biāo)度網(wǎng)絡(luò)[22]以及網(wǎng)絡(luò)規(guī)模為400、平均節(jié)點度為6的小世界網(wǎng)絡(luò)[23]上，通過以下三種常見中心度估計量作為基準(zhǔn)與文中的估計量進(jìn)行比較分析，仿真結(jié)果如圖3和圖4所示。

結(jié)合圖3和圖4可知，在樹狀網(wǎng)絡(luò)中，即圖3(a)(b)，基于距離中心性的溯源算法檢測性能最差，平均距離最大，在各個距離所對應(yīng)的累計檢測概率均小于其余三種算法，其他三種溯源算法檢測性能相差不大。距離中心性、Jordan中心性和謠言中心性在平均錯誤距離2.5跳內(nèi)，累計檢測概率均達(dá)到90%以上，其中接近中心性在規(guī)則樹中的檢測性能略強(qiáng)，謠言中心性在隨機(jī)樹中表現(xiàn)略好；由圖3(c)可知，在無標(biāo)度網(wǎng)絡(luò)中，四種算法性能相差不大；小世界網(wǎng)絡(luò)為最接近真實網(wǎng)絡(luò)的人工網(wǎng)絡(luò)，由圖3(d)可以發(fā)現(xiàn)溯源檢測性能由大到小排列為謠言中心性>接近中心性>距離中心性>Jordan中心性，基于謠言中心性的溯源算法在錯誤距離為3跳內(nèi)，累積檢測概率可達(dá)82%。因此，文中所提算法在不同網(wǎng)絡(luò)結(jié)構(gòu)均表現(xiàn)優(yōu)異，平均錯誤距離在2.5以下。

(a)規(guī)則樹

(b)一般樹

(c)BA無標(biāo)度網(wǎng)絡(luò)

(d)WS小世界網(wǎng)絡(luò)

圖4 在不同網(wǎng)絡(luò)結(jié)構(gòu)下不同估計量的平均錯誤距離對比

圖5展示的是規(guī)則樹在不同節(jié)點度和不同網(wǎng)絡(luò)規(guī)模下累計檢測概率隨平均錯誤距離變化曲線。仿真結(jié)果表明，隨著網(wǎng)絡(luò)節(jié)點度的增大，檢測性能越強(qiáng)，平均錯誤距離越小。同時，由于網(wǎng)絡(luò)規(guī)模的增大，減小了感染子圖的邊界效應(yīng)，因此，檢測性能增強(qiáng)，平均錯誤距離減小。如圖5(a)所示，在平均錯誤距離2跳內(nèi)，四種情況的累計檢測概率在50%以上，尤其在平均度為10的規(guī)則樹網(wǎng)絡(luò)中，累計檢測概率接近1。由圖5(b)可知，在平均錯誤距離3跳內(nèi)，累計檢測概率可達(dá)85%以上。

(a)不同節(jié)點度

(b)不同網(wǎng)絡(luò)規(guī)模

綜上所述，從不同角度對文中所提算法進(jìn)行仿真分析，證實了該算法檢測準(zhǔn)確率較高，平均錯誤距離較小，溯源性能優(yōu)異。

4 結(jié)束語

從復(fù)雜網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)出發(fā)，基于譜優(yōu)化的社區(qū)劃分算法，通過模塊化矩陣主特征向量，將雙信源感染子圖劃分成兩個社區(qū)，在各個社區(qū)內(nèi)進(jìn)行基于謠言中心性的單信源估計，從而將復(fù)雜的雙信源溯源分解為兩個單信源溯源問題，最后在不同人工網(wǎng)絡(luò)上進(jìn)行了大量的仿真實驗。實驗結(jié)果表明，該算法綜合性能良好，平均錯誤距離小于2.5，累計檢測概率在55%以上，特別是在樹狀網(wǎng)絡(luò)和無標(biāo)度網(wǎng)絡(luò)中該概率在90%以上。算法的時間復(fù)雜度O(N2)相比傳統(tǒng)的雙信源估計量低，如MSEP算法[12]的時間復(fù)雜度為O(N2d2)，MJC算法[13]的時間復(fù)雜度為O(MaxIter·|V||E|)，有效提高了計算效率。