基于多中心性分析的網(wǎng)絡(luò)輿情信息源點(diǎn)追溯研究*

于 凱 白西柯 郭煜婕

(1.新疆財(cái)經(jīng)大學(xué)公共管理學(xué)院 烏魯木齊 830012；2.新疆財(cái)經(jīng)大學(xué)信息管理學(xué)院 烏魯木齊 830012)

0 引 言

識(shí)別負(fù)面輿情信息源點(diǎn)是一項(xiàng)重要且具有挑戰(zhàn)性的任務(wù)。近年來(lái)，關(guān)于輿情傳播[1]、計(jì)算機(jī)病毒傳播[2]、謠言傳播[3]等問(wèn)題已嚴(yán)重?cái)_亂社會(huì)秩序，由于輿情信息的快速傳播和社交網(wǎng)絡(luò)的動(dòng)態(tài)演變，如何快速、準(zhǔn)確追溯負(fù)面信息來(lái)源并對(duì)傳播源進(jìn)行引導(dǎo)和控制是抑制負(fù)面輿情傳播、精準(zhǔn)治理負(fù)面輿情的最有效方法之一。

當(dāng)前，輿情信息大多依賴于社交網(wǎng)絡(luò)的傳播，首先，社交網(wǎng)絡(luò)上的個(gè)體接收到輿情信息的表現(xiàn)不同，個(gè)體狀態(tài)的不斷轉(zhuǎn)化形成的復(fù)雜關(guān)系對(duì)輿情信息源點(diǎn)追溯問(wèn)題帶來(lái)了新的挑戰(zhàn)。其次，在輿情信息傳播過(guò)程中，通常無(wú)法對(duì)個(gè)體狀態(tài)集進(jìn)行完整的觀察，只能觀察到網(wǎng)絡(luò)中被輿情信息所傳播感染的有限節(jié)點(diǎn)狀態(tài)。最后，輿情傳播的線上網(wǎng)絡(luò)構(gòu)建是一項(xiàng)艱難的工作，輿情信息傳播源點(diǎn)追溯與治理是當(dāng)前研究的熱點(diǎn)亦是需要亟待解決的問(wèn)題。將輿情治理于源頭對(duì)推進(jìn)國(guó)家治理體系和治理能力現(xiàn)代化的實(shí)現(xiàn)具有重要的理論意義，對(duì)深入認(rèn)識(shí)上述問(wèn)題并得到相應(yīng)的管理啟示具有重要的現(xiàn)實(shí)意義。

1 輿情信息溯源問(wèn)題

圖1 輿情信息溯源問(wèn)題示意圖

當(dāng)前關(guān)于源點(diǎn)追溯的研究主要基于以下三種觀測(cè)類型[9]展開：完全觀測(cè)、局部觀測(cè)(快照觀測(cè))和監(jiān)測(cè)器觀測(cè)。完全觀測(cè)和監(jiān)測(cè)器觀測(cè)由于存在諸多缺陷，當(dāng)前研究多采用快照觀測(cè)——從快照信息出發(fā)，利用部分節(jié)點(diǎn)的信息，結(jié)合相關(guān)的技術(shù)和算法進(jìn)行源點(diǎn)追溯，本文亦采取快照觀測(cè)。。

2 研究現(xiàn)狀

目前，源點(diǎn)追溯問(wèn)題已在多個(gè)研究領(lǐng)域展開，但在溯源準(zhǔn)確率、溯源錯(cuò)誤距離上有進(jìn)一步改進(jìn)的空間。因此，本文在已有研究基礎(chǔ)之上引入多中心性算法，旨在提升溯源準(zhǔn)確率，降低溯源錯(cuò)誤距離，這也是研究該問(wèn)題的主要出發(fā)點(diǎn)。

2.1單源追溯Shah等[10]首次系統(tǒng)研究了網(wǎng)絡(luò)中的信息源點(diǎn)追溯問(wèn)題，作為單一來(lái)源的最大似然估計(jì)，假設(shè)每個(gè)節(jié)點(diǎn)只能從它的一個(gè)鄰居那里接收信息，并在樹狀網(wǎng)絡(luò)上研究該問(wèn)題，將正則樹的最大似然估計(jì)定義為新的網(wǎng)絡(luò)中心性——謠言中心性，總結(jié)出信息傳播擴(kuò)散遵循的一般系統(tǒng)集成模型——SI模型。Shen等[11]開發(fā)了一種時(shí)間反向擴(kuò)散算法來(lái)有效追溯擴(kuò)散源，采用輿情傳播動(dòng)力學(xué)過(guò)程對(duì)算法進(jìn)行檢驗(yàn)，將其應(yīng)用于H1N1大流感，并給出源點(diǎn)追溯問(wèn)題的通用條件。

2.2多源追溯Luo等[12]根據(jù)Shah[10]的思想將單源定位擴(kuò)展到多源定位，提出了一種多源估計(jì)和社團(tuán)劃分的算法，通過(guò)將感染圖劃分為幾個(gè)不相交的網(wǎng)絡(luò)區(qū)域，每個(gè)區(qū)域?qū)?yīng)一個(gè)源。Cesar等[9]基于計(jì)算采樣網(wǎng)絡(luò)上的節(jié)點(diǎn)中心性——度中心性、介數(shù)中心性、接近中心性和特征向量中心性，提出并驗(yàn)證了一種基于無(wú)偏介數(shù)中心性的溯源算法，表明源節(jié)點(diǎn)往往具有最高的測(cè)量值，Zang等[13]將該算法推廣到了多源場(chǎng)景。Fioriti等[14]根據(jù)感染子圖中某個(gè)節(jié)點(diǎn)移除前后最大特征值的差值提出動(dòng)態(tài)年齡算法(DA)，表明最大特征值差異越大的節(jié)點(diǎn)越有可能成為源節(jié)點(diǎn)，并以此來(lái)識(shí)別疾病爆發(fā)的多個(gè)來(lái)源。Prakash等[15]以SI模型作為疾病傳播載體模型，提出最小描述長(zhǎng)度算法(MDL)來(lái)識(shí)別傳播源，進(jìn)一步通過(guò)貪婪算法優(yōu)化傳播源的描述長(zhǎng)度來(lái)精準(zhǔn)識(shí)別傳播源。

2.3中心性指標(biāo)中心性指標(biāo)[16]是社交網(wǎng)絡(luò)中衡量網(wǎng)絡(luò)節(jié)點(diǎn)重要性的首要方法。Freeman[17]基于Sabidussi[18]的工作對(duì)經(jīng)典的中心性指標(biāo)——度中心性，介數(shù)中心性、接近中心性和特征向量中心性進(jìn)行了廣泛的討論。近年來(lái)，越來(lái)越多的學(xué)者[19]將中心性指標(biāo)引入源點(diǎn)追溯問(wèn)題中，通過(guò)啟發(fā)式算法更加準(zhǔn)確的對(duì)輿情、謠言、疾病等信息源進(jìn)行追溯定位。

基于以上分析，我們不難發(fā)現(xiàn)，當(dāng)前已有學(xué)者從不同的角度出發(fā)，對(duì)輿情、謠言、疾病等源點(diǎn)追溯問(wèn)題展開了深入研究。但現(xiàn)有算法在溯源準(zhǔn)確率、誤差距離等方面存在較大的改進(jìn)空間。鑒于此，本文提出一種基于兩階段的多中心性輿情信息傳播源點(diǎn)追溯算法，旨在提高輿情信息源點(diǎn)追溯的準(zhǔn)確率，以期更加準(zhǔn)確的追溯目標(biāo)源節(jié)點(diǎn)，為政府等公共管理部門提供關(guān)于輿情信息源點(diǎn)追溯問(wèn)題的依據(jù)。

3 多中心性算法

3.1算法描述在2.3的啟發(fā)下，借鑒文獻(xiàn)[20]中的基本思想，引入基于多中心性的輿情信息源點(diǎn)追溯算法，該算法分兩個(gè)階段進(jìn)行：第一階段，以SI模型為輿情傳播載體模型在不同數(shù)據(jù)集上模擬輿情信息傳播過(guò)程，并設(shè)置輿情傳播感染規(guī)模，當(dāng)傳播規(guī)模達(dá)到預(yù)設(shè)閾值時(shí)，輿情傳播停止，以此生成對(duì)應(yīng)的輿情感染子圖，結(jié)合表1中的5種中心性指標(biāo)篩選出目標(biāo)源節(jié)點(diǎn)的候選節(jié)點(diǎn)；第二階段，利用5種中心性指標(biāo)對(duì)目標(biāo)源節(jié)點(diǎn)的候選節(jié)點(diǎn)進(jìn)行二次篩選，即有效組合5種中心性指標(biāo)來(lái)構(gòu)建多中心性算法，進(jìn)一步通過(guò)大量實(shí)驗(yàn)找出溯源效果最好的多中心性算法以此來(lái)精準(zhǔn)追溯輿情信息傳播源點(diǎn)，并針對(duì)性的對(duì)輿情傳播源點(diǎn)進(jìn)行引導(dǎo)和控制，真正實(shí)現(xiàn)將輿情治理于源頭之處。5種中心性指標(biāo)如表1所示。

表1 5種中心性指標(biāo)

3.2多中心性算法公式性表達(dá)多中心性算法(Multicentricity Algorithm，MCA)就是適當(dāng)選取目標(biāo)網(wǎng)絡(luò)中的單一中心性指標(biāo)，將中心性指標(biāo)進(jìn)行有效組合，具體的表達(dá)式如式(1)所示：

(1)

MCA(DC)=f[D(i),C(i)]=f[C(i)|D(i)]

(2)

MCA(EC)=f[E(i),C(i)]=f[C(i)|E(i)]

(3)

其中，MCA(DC) 是度中心性和接近中心性的混合函數(shù)，即首先根據(jù)度中心性篩選出目標(biāo)源點(diǎn)的候選節(jié)點(diǎn)，再根據(jù)接近中心性在目標(biāo)源點(diǎn)的候選節(jié)點(diǎn)中進(jìn)行二次篩選，對(duì)兩種中心性指標(biāo)進(jìn)行有效組合，以此更加準(zhǔn)確的定位目標(biāo)源點(diǎn)。MCA(EC)具體含義同上。

3.3多中心性算法的性能利用R軟件分別以隨機(jī)圖(Random)、正則圖(Regular)為基礎(chǔ)網(wǎng)絡(luò)構(gòu)建輿情傳播網(wǎng)絡(luò)，兩個(gè)網(wǎng)絡(luò)均包含5 000個(gè)節(jié)點(diǎn)。首先，以SI模型為輿情信息傳播載體模型，在隨機(jī)圖與正則圖上隨機(jī)選擇一個(gè)節(jié)點(diǎn)作為輿情傳播源點(diǎn)，初步設(shè)定輿情傳播感染規(guī)模為20%～30%，當(dāng)輿情傳播感染規(guī)模達(dá)到預(yù)設(shè)值時(shí)輿情傳播停止，并生成對(duì)應(yīng)的輿情傳播感染子圖；其次，選擇式(2)和式(3)的多中心性算法，分別為DC、EC，在輿情傳播感染子圖中進(jìn)行100次輿情信息源點(diǎn)追溯實(shí)驗(yàn)；最后，給出多中心性算法與單一中心性算法的溯源錯(cuò)誤距離(目標(biāo)源節(jié)點(diǎn)與各算法追溯源節(jié)點(diǎn)之間的距離)、溯源平均錯(cuò)誤距離、溯源準(zhǔn)確率，具體結(jié)果如圖2所示。

圖2 多中心性與單一中心性算法的溯源錯(cuò)誤距離、平均錯(cuò)誤距離及準(zhǔn)確率對(duì)比

由圖2(a)、2(c)、2(e)可知，100次實(shí)驗(yàn)中不同中心性算法在隨機(jī)圖上的溯源錯(cuò)誤距離存在較大差距，其中EC算法表現(xiàn)最好，溯源錯(cuò)誤距離為0(即準(zhǔn)確溯源)的頻數(shù)高達(dá)98次，離心率中心性表現(xiàn)次之(95次)，特征向量中心性溯源錯(cuò)誤距離為1步時(shí)的頻數(shù)為41次；在溯源平均錯(cuò)誤距離上，EC的溯源平均錯(cuò)誤距離為0.02步，表現(xiàn)最佳，離心率中心性的溯源平均錯(cuò)誤距離為0.05步，度中心性、接近中心性、介數(shù)中心性和DC算法表現(xiàn)相當(dāng)，溯源平均錯(cuò)誤距離在2步左右，表現(xiàn)較差；此外，在溯源準(zhǔn)確率上EC算法的表現(xiàn)也是最佳。

由圖2(b)、2(d)、2(f)可知，離心率中心性與EC算法在正則圖上的溯源表現(xiàn)較好，溯源平均錯(cuò)誤距離均小于1步，分別為0.41步，0.50步，且溯源準(zhǔn)確率分別高達(dá)65%，61%，顯著優(yōu)于其他中心性算法。而度中心性表現(xiàn)最差，溯源準(zhǔn)確率僅有2%，介數(shù)中心性溯源準(zhǔn)確率為11%，接近中心性與DC算法溯源準(zhǔn)確率在20%左右，效果不太理想。

綜合來(lái)看，EC算法在輿情信息溯源問(wèn)題上的表現(xiàn)最佳。

3.4多中心性算法與經(jīng)典算法的溯源表現(xiàn)對(duì)比為了將EC算法與經(jīng)典溯源算法的溯源表現(xiàn)進(jìn)行對(duì)比，分別將EC算法、DA算法、MDL算法在隨機(jī)圖和正則圖上的表現(xiàn)作出如下對(duì)比實(shí)驗(yàn)，實(shí)驗(yàn)過(guò)程與3.3相同，輿情傳播感染規(guī)模為20%～30%，3種算法在隨機(jī)圖與正則圖上的溯源準(zhǔn)確率、溯源錯(cuò)誤距離對(duì)比情況如圖3所示。

圖3 3種算法在隨機(jī)圖與正則圖上的溯源準(zhǔn)確率、錯(cuò)誤距離對(duì)比

由圖3(a)可知，在隨機(jī)圖和正則圖上，EC算法在溯源準(zhǔn)確率、溯源錯(cuò)誤距離上均優(yōu)于MDL算法與DA算法。3種算法在隨機(jī)圖上的溯源準(zhǔn)確率分別為98%、0%、59%，在正則圖上的溯源準(zhǔn)確率分別為61%、32%、21%。由圖3(b)、3(c)可知，3種算法在隨機(jī)圖和正則圖上的溯源錯(cuò)誤距離分布情況存在較大差異，在隨機(jī)圖上，100次實(shí)驗(yàn)中EC算法的溯源錯(cuò)誤距離在0步的頻次高達(dá)98次，而DA算法的溯源錯(cuò)誤距離在1—2步時(shí)仍有較多頻次，MDL表現(xiàn)最差，錯(cuò)誤距離在4步的頻次高達(dá)50次；在正則圖上，EC算法的溯源錯(cuò)誤距離分布情況仍優(yōu)于其他兩種算法。

3.5算法有效性驗(yàn)證此外，為了驗(yàn)證EC算法的有效性，將3種算法在真實(shí)網(wǎng)絡(luò)—美國(guó)電網(wǎng)[22]上的溯源表現(xiàn)作出如下對(duì)比實(shí)驗(yàn)，該網(wǎng)絡(luò)是一個(gè)無(wú)向、無(wú)權(quán)的網(wǎng)絡(luò)，網(wǎng)絡(luò)數(shù)據(jù)由4941個(gè)節(jié)點(diǎn)和6594條邊組成。實(shí)驗(yàn)中生成3組大小不同的輿情感染規(guī)模，具體過(guò)程同上，3種算法在美國(guó)電網(wǎng)上的溯源平均錯(cuò)誤距離和溯源錯(cuò)誤距離分布情況如圖4所示。

圖4 3種算法在美國(guó)電力網(wǎng)上的溯源平均錯(cuò)誤距離及溯源錯(cuò)誤距離分布對(duì)比

由圖4(a)可知，當(dāng)輿情傳播規(guī)模為5%～10%時(shí)，EC算法、DA算法、MDL算法的溯源平均錯(cuò)誤距離分別為4.48步、5.92步、6.15步；當(dāng)輿情傳播規(guī)模為30%～40%時(shí)，3種算法的溯源平均錯(cuò)誤距離分別為7.2步、13.06步、10.38步；當(dāng)輿情傳播規(guī)模為40%～60%時(shí)，3種算法的溯源平均錯(cuò)誤距離分別為8步、14.82步、10.11步，可以發(fā)現(xiàn)無(wú)論輿情感染規(guī)模大小如何，EC算法的溯源平均錯(cuò)誤距離都低于其他兩種算法。由圖4(b)可知，在輿情傳播規(guī)模為5%～10%的時(shí)候，3種算法在100次實(shí)驗(yàn)中溯源錯(cuò)誤距離出現(xiàn)在4～7步的頻次最多，但EC算法溯源錯(cuò)誤距離主要集中在0～3步和4～7步，其他兩種算法卻有較大頻次出現(xiàn)在8～11步。此外，由圖4(b)、4(c)、4(d)可知，隨著輿情感染規(guī)模的增加，3種算法的溯源錯(cuò)誤距離分布情況均逐漸后移，但EC算法的錯(cuò)誤距離分布情況仍優(yōu)于其他兩種算法。

綜上所述，EC算法在輿情信息源點(diǎn)追溯問(wèn)題上有著較好的表現(xiàn)，溯源平均錯(cuò)誤距離較低且溯源準(zhǔn)確率高，在溯源性能上優(yōu)于單一中心性算法、MDL算法和DA算法，輿情信息傳播網(wǎng)絡(luò)無(wú)論是合成網(wǎng)絡(luò)(隨機(jī)圖、正則圖)還是真實(shí)網(wǎng)絡(luò)(美國(guó)電網(wǎng))，該算法均可以很好地利用網(wǎng)絡(luò)數(shù)據(jù)集的結(jié)構(gòu)特征，溯源準(zhǔn)確率較高，且溯源錯(cuò)誤距離較低。

4 輿情溯源準(zhǔn)確率影響因素

此外，網(wǎng)絡(luò)結(jié)構(gòu)、輿情傳播規(guī)?？赡苁怯绊懰菰礈?zhǔn)確率的潛在因素。為了探究影響輿情溯源準(zhǔn)確率的因素，首先在隨機(jī)圖和正則圖上生成3組不同規(guī)模大小的輿情傳播感染子圖，當(dāng)輿情傳播感染規(guī)模達(dá)到預(yù)設(shè)規(guī)模時(shí)，輿情傳播停止并標(biāo)記對(duì)應(yīng)規(guī)模，如表2所示。其次，將EC算法與經(jīng)典算法在不同網(wǎng)絡(luò)結(jié)構(gòu)、不同輿情傳播規(guī)模上進(jìn)行溯源實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如圖5、圖6、圖7所示(橫向?qū)Ρ扰c縱向?qū)Ρ?。最后，通過(guò)實(shí)驗(yàn)結(jié)果分析影響輿情溯源準(zhǔn)確率、溯源錯(cuò)誤距離的因素。

表2 不同網(wǎng)絡(luò)結(jié)構(gòu)上的輿情傳播規(guī)模設(shè)置

由圖5可知，不同網(wǎng)絡(luò)結(jié)構(gòu)對(duì)輿情溯源準(zhǔn)確率有著顯著的影響，無(wú)論感染規(guī)模大小如何，EC算法在隨機(jī)圖與正則圖上的溯源準(zhǔn)確率顯著優(yōu)于DA算法與MDL算法，進(jìn)一步表明了EC算法的優(yōu)勢(shì)。

由圖6、圖7可知，在兩種網(wǎng)絡(luò)結(jié)構(gòu)中，一般來(lái)講，隨著輿情傳播規(guī)模的增加，100次實(shí)驗(yàn)中溯源錯(cuò)誤距離出現(xiàn)在0步(準(zhǔn)確定位)的頻次逐漸減少，通過(guò)橫向?qū)Ρ?種算法的溯源錯(cuò)誤距離可知，EC算法在溯源錯(cuò)誤距離上的表現(xiàn)優(yōu)于其他兩種算法，DA算法表現(xiàn)次之，MDL算法表現(xiàn)最差。因此，精準(zhǔn)把握輿情傳播網(wǎng)絡(luò)結(jié)構(gòu)，運(yùn)用適當(dāng)?shù)乃菰此惴?zhǔn)確定位輿情傳播源頭，及時(shí)進(jìn)行有效疏導(dǎo)和控制，防止輿情規(guī)模擴(kuò)大，從源頭實(shí)現(xiàn)網(wǎng)絡(luò)輿情高效治理。

圖6 不同算法在隨機(jī)圖上的溯源錯(cuò)誤距離

圖7 不同算法在正則圖上的溯源錯(cuò)誤距離

5 總 結(jié)

本文提出了基于兩階段的多中心性算法(EC)，對(duì)輿情信息源點(diǎn)追溯問(wèn)題進(jìn)行了深度剖析，以SI模型為載體模型模擬輿情信息在隨機(jī)圖與正則圖上的傳播過(guò)程，在生成的感染子圖上分別進(jìn)行溯源實(shí)驗(yàn)，并與經(jīng)典溯源算法進(jìn)行對(duì)比，進(jìn)一步在美國(guó)電網(wǎng)上驗(yàn)證了該算法的有效性，無(wú)論是在溯源準(zhǔn)確率還是錯(cuò)誤距離上，該算法都顯現(xiàn)出較大的優(yōu)勢(shì)。一般來(lái)講，隨著輿情傳播規(guī)模的增加，溯源準(zhǔn)確率會(huì)呈現(xiàn)逐漸下降的趨勢(shì)，且輿情傳播規(guī)模越大，溯源效果越差。此外，算法的溯源準(zhǔn)確率與網(wǎng)絡(luò)結(jié)構(gòu)有著密切的關(guān)系，對(duì)網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行深入分析有助于提高溯源準(zhǔn)確率。綜上，輿情治理的方向應(yīng)以源頭治理為主導(dǎo)，利用相關(guān)技術(shù)和算法準(zhǔn)確定位輿情源點(diǎn)，并對(duì)輿情源點(diǎn)進(jìn)行積極的引導(dǎo)和控制，將源點(diǎn)治理作為網(wǎng)絡(luò)輿情高效治理的重點(diǎn)。

目前研究仍存在一定的不足，如未考慮加權(quán)有向網(wǎng)絡(luò)、網(wǎng)絡(luò)稀疏性、存在多源等問(wèn)題對(duì)于多中心性算法溯源準(zhǔn)確率的影響，以上問(wèn)題還需進(jìn)一步研究和探討。