社交網(wǎng)絡(luò)信息傳播預(yù)測與特定信息抑制

曹玖新 高慶清 夏蓉清 劉偉佳 朱雪林 劉 波

1(東南大學(xué)網(wǎng)絡(luò)空間安全學(xué)院 南京 211189)

2(東南大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 南京 211189)

近年來，社交網(wǎng)絡(luò)以其多樣化的分享功能，打破了固有的信息傳播形式.隨著社交網(wǎng)絡(luò)平臺(tái)的普及度越來越高，時(shí)間與空間不再成為信息傳播的阻礙，為人們提供了極大的便利.然而，社交網(wǎng)絡(luò)中存在著海量的信息，隱藏其中的謠言、不實(shí)信息、有惡意導(dǎo)向性的輿論等往往也會(huì)被廣為傳播.

目前，微博上的用戶可以對(duì)微博中存在垃圾營銷、不實(shí)信息、詐騙信息等情況進(jìn)行投訴，平臺(tái)驗(yàn)證后會(huì)對(duì)該微博以及該微博的作者進(jìn)行一定的處理，來達(dá)到抑制該信息傳播的目的.微信上，用戶閱讀過或分享過的文章如果被鑒定為謠言，那么用戶將會(huì)收到來自“微信辟謠助手”小程序的提醒.然而，會(huì)對(duì)個(gè)人或企業(yè)造成不良影響的負(fù)向引導(dǎo)性信息往往不會(huì)受到社交網(wǎng)絡(luò)平臺(tái)的關(guān)注.例如，某品牌手機(jī)某一系列的個(gè)別產(chǎn)品曾經(jīng)出現(xiàn)過綠屏的現(xiàn)象，這個(gè)問題不是普遍發(fā)生的，卻引發(fā)大量用戶在社交平臺(tái)上發(fā)布相關(guān)負(fù)向言論，給該品牌造成了較大的負(fù)面影響.社交網(wǎng)絡(luò)平臺(tái)并不會(huì)針對(duì)這種情況提供解決方案，因而會(huì)給個(gè)人或企業(yè)帶來很大的困擾.

1 研究現(xiàn)狀

由于社交網(wǎng)絡(luò)的快速發(fā)展，國內(nèi)外已經(jīng)對(duì)社交網(wǎng)絡(luò)中的信息傳播預(yù)測與抑制進(jìn)行了廣泛研究，主要包括了信息轉(zhuǎn)發(fā)預(yù)測、信息傳播模型以及信息傳播抑制3個(gè)方面.有關(guān)信息傳播預(yù)測與抑制的相關(guān)工作介紹為：

在社交網(wǎng)絡(luò)中，轉(zhuǎn)發(fā)行為是信息傳播的主要形式，不少學(xué)者對(duì)社交網(wǎng)絡(luò)中的轉(zhuǎn)發(fā)行為進(jìn)行了研究.目前轉(zhuǎn)發(fā)預(yù)測相關(guān)研究按照任務(wù)類別可以分為3種：預(yù)測轉(zhuǎn)發(fā)對(duì)象[1]，即預(yù)測用戶最有可能轉(zhuǎn)發(fā)的Top-N條博文；預(yù)測轉(zhuǎn)發(fā)時(shí)間[2]，即預(yù)測用戶轉(zhuǎn)發(fā)給定博文的時(shí)間；預(yù)測轉(zhuǎn)發(fā)行為[3-5]，即預(yù)測用戶是否轉(zhuǎn)發(fā)給定博文或轉(zhuǎn)發(fā)給定博文的概率.本文聚焦于預(yù)測用戶轉(zhuǎn)發(fā)行為，從而為之后的特定信息抑制提供基礎(chǔ).在預(yù)測用戶轉(zhuǎn)發(fā)行為方面，文獻(xiàn)[3]提出了一個(gè)基于影響局部性函數(shù)的邏輯回歸模型，綜合考慮了粉絲數(shù)、相互關(guān)注數(shù)、注冊(cè)時(shí)間等特征；文獻(xiàn)[4]提出了一個(gè)基于注意力的深度神經(jīng)網(wǎng)絡(luò)來整合上下文和社交信息，該模型主要考慮的因素有微博作者特征、微博文本特征、待預(yù)測用戶特征和用戶興趣特征；文獻(xiàn)[5]提出了一種基于上下文感知、聯(lián)合矩陣-張量分解的轉(zhuǎn)發(fā)預(yù)測模型，綜合考慮了用戶、博文和影響力3個(gè)維度信息.

目前已有大量的文獻(xiàn)對(duì)社交網(wǎng)絡(luò)中的信息傳播模型進(jìn)行研究，基于網(wǎng)絡(luò)中傳播的信息數(shù)量可以分為單一信息傳播模型和多信息競爭傳播模型兩大類.現(xiàn)有的單一信息傳播模型主要可以分為3個(gè)方向：基于個(gè)體狀態(tài)的傳播模型、基于網(wǎng)絡(luò)結(jié)構(gòu)的傳播模型以及基于信息特性的傳播模型.其中，基于個(gè)體狀態(tài)的傳播模型主要有傳染病模型，如SI模型[6]、SIR模型[7]等以及它們的改進(jìn)模型：Maki-Thompson模型[8]等；基于網(wǎng)絡(luò)結(jié)構(gòu)的傳播模型主要有線性閾值模型和獨(dú)立級(jí)聯(lián)模型[9]以及基于這2個(gè)模型的各類改進(jìn)模型；基于信息特性的傳播模型主要是根據(jù)特定信息源和信息傳播平臺(tái)建立的模型.同時(shí)，也有一些學(xué)者研究了多信息競爭傳播模型.Tzoumas等人[10]從非合作博弈論的角度研究了2條信息的競爭傳播過程，并通過擴(kuò)展線性閾值模型對(duì)2條信息的競爭傳播過程進(jìn)行建模；Liu等人[11]擴(kuò)展了SIR模型，提出了敏感-遲疑-感染-移除(sensitive-hesitate-infection-remove, SHIR)模型來研究2條信息的競爭傳播過程；曹玖新等人[12]針對(duì)多條相似信息的競爭傳播問題，提出了基于競爭的線性閾值擴(kuò)展模型，模型中考慮到了不同信息的主題分布的不一致性.已有研究針對(duì)不同的競爭傳播應(yīng)用場景對(duì)傳統(tǒng)的傳播模型進(jìn)行了擴(kuò)展,然而現(xiàn)有研究大多沒有同時(shí)考慮到不同信息在網(wǎng)絡(luò)中傳播的起始時(shí)間的不同以及用戶對(duì)于權(quán)威賬戶和普通賬戶發(fā)布的信息的信任程度的差異.

現(xiàn)有的信息傳播抑制相關(guān)研究可分為2個(gè)主要方向：1)通過去除網(wǎng)絡(luò)中的部分邊或節(jié)點(diǎn)來阻斷特定信息的傳播;2)通過選取網(wǎng)絡(luò)部分節(jié)點(diǎn)傳播與特定信息內(nèi)容相反的信息來抑制特定信息的不良影響.文獻(xiàn)[13]提出了一種基于貪心策略的方法來移除網(wǎng)絡(luò)中的部分連邊，從而抑制信息傳播;文獻(xiàn)[14]提出了一種貪心算法來選取網(wǎng)絡(luò)中部分未激活節(jié)點(diǎn)進(jìn)行阻斷以最小化最終被特定信息激活的節(jié)點(diǎn)數(shù)量;Yan等人[15]基于獨(dú)立級(jí)聯(lián)模型，提出了一個(gè)謠言傳播模型，并采用改進(jìn)了的貪心算法來提高選取需阻斷節(jié)點(diǎn)的效率;Nguyen等人[16]通過找到一組具有高度影響力的節(jié)點(diǎn)作為正確信息影響節(jié)點(diǎn)，來限制不良信息在整個(gè)網(wǎng)絡(luò)中的傳播，并給出了幾種選取正確信息影響節(jié)點(diǎn)的貪心算法和啟發(fā)式算法;Tong等人[17]提出了一個(gè)隨機(jī)算法來選取正確信息影響節(jié)點(diǎn)集合以節(jié)約運(yùn)行時(shí)間.

然而，現(xiàn)有研究大多沒有使用真實(shí)社交網(wǎng)絡(luò)上的信息傳播數(shù)據(jù).盡管有些研究是基于真實(shí)的社交網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，但是具體的信息傳播與抑制過程完全使用仿真的方式，缺乏真實(shí)性.

本研究的主要貢獻(xiàn)包括4個(gè)方面：

1) 基于真實(shí)的新浪微博數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，更客觀地證明了本文模型的合理性以及算法的有效性；

2) 提出了不依賴于傳播模型的獨(dú)立信息轉(zhuǎn)發(fā)預(yù)測機(jī)制，并通過實(shí)驗(yàn)篩選出了對(duì)于轉(zhuǎn)發(fā)預(yù)測最有效的特征組合；

3) 考慮到真實(shí)應(yīng)用場景下，用戶的初始狀態(tài)以及狀態(tài)轉(zhuǎn)化方式與傳統(tǒng)的競爭影響力傳播模型的不同，提出了異步信息不平等競爭傳播模型；

4) 為個(gè)人、企業(yè)澄清與自身相關(guān)的不良信息提供了解決的方案.

2 基于機(jī)器學(xué)習(xí)的信息傳播預(yù)測模型

在社交網(wǎng)絡(luò)這一特定場景下，信息傳播的過程是由不同用戶的轉(zhuǎn)發(fā)行為所構(gòu)成的.因此，本節(jié)將宏觀的信息傳播預(yù)測問題轉(zhuǎn)化為微觀的用戶轉(zhuǎn)發(fā)預(yù)測問題.可將問題具體定義為：給定用戶u與微博w，預(yù)測用戶u轉(zhuǎn)發(fā)微博w的概率puw.

基于該問題定義，本文提出了不依賴于傳播模型的獨(dú)立信息轉(zhuǎn)發(fā)預(yù)測(independent information forwarding prediction, IIFP)機(jī)制：首先進(jìn)行多維度特征提取，然后將特征輸入到合適的分類器中訓(xùn)練分類模型以進(jìn)行信息轉(zhuǎn)發(fā)預(yù)測.

在特征提取階段，需要綜合考慮可能對(duì)轉(zhuǎn)發(fā)行為有影響的因素.本研究從4個(gè)維度進(jìn)行特征選?。禾囟ㄐ畔⑽⒉┚S度、用戶維度(包括待預(yù)測用戶和特定信息微博作者用戶)、待預(yù)測用戶與特預(yù)測微博作者的相似程度、待預(yù)測用戶歷史微博與特定信息微博的相似程度.在這4個(gè)維度中選取的具體特征如表1所示，本文將在實(shí)驗(yàn)部分對(duì)不同特征的貢獻(xiàn)進(jìn)行對(duì)比.

特征提取之后，便可訓(xùn)練分類器.本研究采用Lightgbm分類器[18]對(duì)用戶轉(zhuǎn)發(fā)特定信息微博的概率pv進(jìn)行預(yù)測，該分類器是梯度提升決策樹(gradient boosting decision tree, GBDT)的一種優(yōu)化，具有能夠直接處理類別特征、運(yùn)算速度快、分類效果好等優(yōu)點(diǎn)，并且支持并行和大規(guī)模的數(shù)據(jù)處理.Lightgbm是一種集成模型，理論上會(huì)比普通的單一模型效果好，實(shí)驗(yàn)部分也會(huì)對(duì)Lightgbm與其他分類器的綜合性能進(jìn)行對(duì)比.

3 異步信息不平等競爭傳播模型

本節(jié)提出了異步信息不平等競爭傳播模型(asynchronous information unequal competition propagation model, AIUCP)作為特定信息與免疫信息的競爭傳播機(jī)制.

3.1 概念定義

本節(jié)首先明確相關(guān)概念定義：

定義1.社交網(wǎng)絡(luò)

本文中社交網(wǎng)絡(luò)用有向圖G(V,E)表示，其中V為節(jié)點(diǎn)集合，即社交網(wǎng)絡(luò)中的用戶集合，E為有向邊集合，即社交網(wǎng)絡(luò)中的用戶間關(guān)注關(guān)系集合.具體來說，對(duì)用戶u,v∈V，若存在euv∈E，則表示用戶u被用戶v關(guān)注，此時(shí)用戶u為用戶v的內(nèi)鄰居節(jié)點(diǎn)，用戶v為用戶u的外鄰居節(jié)點(diǎn).

定義2.傳播子圖

在獨(dú)立級(jí)聯(lián)模型下，影響力的傳播是一個(gè)隨機(jī)的過程，信息經(jīng)過一次完整傳播后，網(wǎng)絡(luò)G中被該信息影響的節(jié)點(diǎn)構(gòu)成的子圖稱為網(wǎng)絡(luò)G的一個(gè)傳播子圖g.

定義3.特定信息

特定信息為可能對(duì)某些群體造成不利影響的言論，其中包含謠言、不實(shí)信息、有惡意導(dǎo)向性的輿論等，在社交網(wǎng)絡(luò)中被轉(zhuǎn)發(fā)傳播會(huì)對(duì)社會(huì)或者某類用戶產(chǎn)生不利影響.

定義4.免疫信息

免疫信息是與特定信息內(nèi)容語義相反的信息，一般由被認(rèn)證為權(quán)威機(jī)構(gòu)的微博用戶發(fā)布，將其投入社交網(wǎng)絡(luò)中可以抑制特定信息的傳播.

定義5.抑制效果

設(shè)被特定信息激活的節(jié)點(diǎn)的狀態(tài)是狀態(tài)A，被免疫信息激活的節(jié)點(diǎn)的狀態(tài)是狀態(tài)B，初始特定信息傳播節(jié)點(diǎn)集合是IA，選取的免疫信息節(jié)點(diǎn)集合是IB.σ(IA,IB)表示已知初始狀態(tài)A節(jié)點(diǎn)集合為IA的情況下，種子節(jié)點(diǎn)集合IB所能影響的節(jié)點(diǎn)個(gè)數(shù)，即特定信息傳播抑制效果.

3.2 傳播場景特殊性

在本文的研究場景下，特定信息與免疫信息在社交網(wǎng)絡(luò)中共同傳播，與傳統(tǒng)的競爭影響力傳播有一定的相似.然而，該場景下節(jié)點(diǎn)的行為狀態(tài)與轉(zhuǎn)化方式有所不同，具體表現(xiàn)在：

1) 免疫信息在特定信息傳播了一定時(shí)間后才會(huì)被投放.因此，初始狀態(tài)下只有部分節(jié)點(diǎn)處于已被特定信息激活的狀態(tài)，其他節(jié)點(diǎn)均處于未激活狀態(tài)；

2) 免疫信息通常由權(quán)威賬戶發(fā)布，其發(fā)布內(nèi)容具有天然的優(yōu)先可信度.因此，當(dāng)某一節(jié)點(diǎn)同時(shí)接收到特定信息和免疫信息，該節(jié)點(diǎn)更傾向于被免疫信息激活.同時(shí)，被特定信息激活的節(jié)點(diǎn)仍有可能被免疫信息激活，但是被免疫信息激活的節(jié)點(diǎn)狀態(tài)不會(huì)再發(fā)生改變.

3.3 用戶狀態(tài)與用戶間影響概率

在異步信息不平等競爭傳播模型下，用戶分為4種狀態(tài)：1)狀態(tài)A.相信特定信息并轉(zhuǎn)發(fā)，即被特定信息激活；2)狀態(tài)B.相信免疫信息并轉(zhuǎn)發(fā)，即被免疫信息激活；3)狀態(tài)N.尚未看到特定信息或免疫信息；4)狀態(tài)O.對(duì)特定信息和免疫信息都不感興趣無應(yīng)對(duì)行為.其中，狀態(tài)O的用戶可作為無關(guān)節(jié)點(diǎn)直接去除.初始狀態(tài)下，有一部分節(jié)點(diǎn)已處于被特定信息激活的狀態(tài)為狀態(tài)A，其余節(jié)點(diǎn)均為狀態(tài)N.

本文在第2節(jié)中，通過獨(dú)立信息轉(zhuǎn)發(fā)預(yù)測機(jī)制預(yù)測用戶u轉(zhuǎn)發(fā)微博w的概率puw.本節(jié)中，微博w是特定的，因此將用戶u轉(zhuǎn)發(fā)特定微博的概率簡寫為pu.本文第2節(jié)提出的機(jī)制在預(yù)測過程中并不考慮用戶看到信息的途徑，因此進(jìn)一步考慮用戶間相似度，以獲取用戶v轉(zhuǎn)發(fā)特定上游用戶u原創(chuàng)或轉(zhuǎn)發(fā)的信息的概率，即用戶間的影響權(quán)重p(u,v).具體計(jì)算公式為

p(u,v)=pv×simu,v,

(1)

其中，pv為用戶v轉(zhuǎn)發(fā)特定信息微博的概率，simu,v為用戶u與用戶v的相似度，該相似度將采用Jaccard[19]相似度計(jì)算公式從關(guān)注列表的相似程度、粉絲列表的相似程度、標(biāo)簽的相似程度、省份是否相同、城市是否相同以及關(guān)注關(guān)系6個(gè)角度來計(jì)算.

3.4 信息傳播過程

異步信息不平等競爭傳播模型的信息傳播過程描述具體分為4個(gè)步驟:

1) 在t=0步時(shí)，已有部分節(jié)點(diǎn)處于被特定信息激活的狀態(tài)A，此時(shí)，在未激活的節(jié)點(diǎn)集中選取種子集合，為它們賦予狀態(tài)B；

2) 在第t步時(shí)，在時(shí)間步t-1狀態(tài)為激活狀態(tài)的節(jié)點(diǎn)u嘗試以傳播概率p(u,v)激活它的外鄰居節(jié)點(diǎn)v.如果一個(gè)節(jié)點(diǎn)被多個(gè)狀態(tài)的多個(gè)節(jié)點(diǎn)影響時(shí)，分為3種情況進(jìn)行討論：

③ 當(dāng)節(jié)點(diǎn)v的狀態(tài)為狀態(tài)B時(shí)，節(jié)點(diǎn)v的狀態(tài)不會(huì)發(fā)生改變；

3) 若節(jié)點(diǎn)v在第t步被激活，那么它將在第(t+1)步嘗試激活它的鄰居節(jié)點(diǎn)；

4) 當(dāng)沒有節(jié)點(diǎn)可以再被激活時(shí)，傳播結(jié)束.

4 社交網(wǎng)絡(luò)特定信息抑制

4.1 問題定義

已知社交網(wǎng)絡(luò)G(V,E)，節(jié)點(diǎn)u影響節(jié)點(diǎn)v的概率為p(u,v)，特定信息影響的初始節(jié)點(diǎn)集合為IA.要求找到大小為k的免疫信息種子節(jié)點(diǎn)集合IB，使得免疫信息種子節(jié)點(diǎn)集合IB所能影響的節(jié)點(diǎn)個(gè)數(shù)最多.

4.2 特定信息抑制影響最大化目標(biāo)函數(shù)

基于4.1節(jié)中的問題定義，給出特定信息抑制影響最大化目標(biāo)函數(shù)為

(2)

其中，σ(IA,IB)表示已知初始狀態(tài)A節(jié)點(diǎn)集合為IA的情況下，種子節(jié)點(diǎn)集合IB所能影響的節(jié)點(diǎn)個(gè)數(shù)，Pr(g)表示傳播子圖g出現(xiàn)的概率，σg(IA,IB)表示在傳播子圖g中給定集合IA的情況下，種子節(jié)點(diǎn)集合IB所能影響的節(jié)點(diǎn)個(gè)數(shù).

定義傳播子圖g的出現(xiàn)概率[20]Pr(g)為

(3)

其中，e和e′均表示社交網(wǎng)絡(luò)G中的一條有向邊，p(e)和p(e′)分別表示邊e和e′屬于子圖g的概率.

4.3 目標(biāo)函數(shù)的數(shù)學(xué)性質(zhì)證明

本節(jié)對(duì)目標(biāo)函數(shù)的單調(diào)性和子模性進(jìn)行證明.

1) 單調(diào)性證明

首先，根據(jù)單調(diào)性的定義5來證明抑制影響最大化的目標(biāo)函數(shù)具有單調(diào)性.

定義5.如果對(duì)于所有子集S?T?V，有f(S)≤f(T)，則集合函數(shù)f:2V→R是單調(diào)的.

引理1.如果對(duì)于所有子集I1?I2?VB有σ(IA,I1)≤σ(IA,I2)，則抑制影響最大化目標(biāo)函數(shù)σ(IA,IB)是單調(diào)的.其中，VB=VIA為免疫信息種子節(jié)點(diǎn)的可選集合.

證明：

根據(jù)式(3)

其中，δg(IA,u)表示在網(wǎng)絡(luò)中某個(gè)傳播子圖g已有特定信息節(jié)點(diǎn)集合IA傳播的情況下，免疫信息種子節(jié)點(diǎn)u能夠影響激活的節(jié)點(diǎn)集合.

由此可推出

σ(IA,I1)≤σ(IA,I2),

即抑制影響最大化目標(biāo)函數(shù)具有單調(diào)性.

證畢.

2) 子模性證明

定義6.如果對(duì)于所有子集S?T?V和所有節(jié)點(diǎn)v∈VT，有f(S∪{v})-f(S)≥f(T∪{v})-f(T)，則集合函數(shù)f:2V→R是子模的.

引理2.如果對(duì)于所有子集I1?I2?VB和所有節(jié)點(diǎn)v∈VBI2，有：

σ(IA,I1∪{v})-σ(IA,I1)≥
σ(IA,I2∪{v})-σ(IA,I2)，

則抑制影響最大化目標(biāo)函數(shù)σ(IA,IB)是子模的.其中，VB=VIA為免疫信息種子節(jié)點(diǎn)的可選集合.

證明：

根據(jù)式(2)，

由容斥原理，上式等價(jià)于

|δg(IA,I1∩{v})|-|δg(IA,I1)|)=

同理可推出：

σ(IA,I2∪{v})-σ(IA,I2)=

σ(IA,{v})-σ(IA,I2∩{v}).

由I1?I2可推出：

I1∩{v}?I2∩{v}.

由引理2，目標(biāo)函數(shù)的單調(diào)性可得：

σ(IA,I1∩{v})≤σ(IA,I2∩{v}),

故：

σ(IA,{v})-σ(IA,I1∩{v})≥
σ(IA,{v})-σ(IA,I2∩{v}).

即

σ(IA,I1∪{v})-σ(IA,I1)≥
σ(IA,I2∪{v})-σ(IA,I2).

證畢.

由此可得，抑制影響最大化目標(biāo)函數(shù)具有子模性.

4.4 抑制影響最大化貪心算法

根據(jù)Nemhauser等人[21]于1978年提出的理論，若目標(biāo)函數(shù)滿足單調(diào)性和子模性，則采用貪心法每一輪選取邊際影響力最大的節(jié)點(diǎn)，共選取k個(gè)種子節(jié)點(diǎn)集合IB，可以得出該影響傳播問題最優(yōu)解的1-1e近似解.

基礎(chǔ)貪心算法的計(jì)算量大、時(shí)間復(fù)雜度高.因此，本文基于具有成本效益的惰性前向選擇(cost-effective lazy forward selection, CELF)算法的基本思想，改進(jìn)了傳統(tǒng)的貪心算法，提出了在本文模型下的異步信息抑制傳播貪心算法(asynchronous infor-mation suppression propagation greedy algorithm, AISPG)來選取免疫信息種子節(jié)點(diǎn)集合.算法首先計(jì)算每個(gè)沒有被特定信息影響的節(jié)點(diǎn)的邊際影響力，將邊際影響力最大的節(jié)點(diǎn)加入免疫信息種子集合IB，接著進(jìn)行k-1輪循環(huán)，每輪基于CELF思想選取邊際影響力最大的節(jié)點(diǎn)加入免疫信息種子集合.具體算法步驟如算法1所示：

算法1.異步信息抑制傳播貪心算法.

輸入：社交網(wǎng)絡(luò)G(V,E)、信息從用戶u傳播到用戶v的概率p(u,v)、特定信息影響的初始節(jié)點(diǎn)集合IA、種子節(jié)點(diǎn)數(shù)目k；

輸出：免疫信息種子集合IB.

① 初始化IB為空集，大頂堆HB為空堆；

② foru∈VIA

③ 計(jì)算Δ(u)=σG(u|IA,?)；

/*邊際影響力*/

④ 將Δ(u)插入HB；

⑤ end for

⑥ 更新IB←IB∪{HB.peek}；

⑦ while |SB|

⑧ foru∈V(IA∪IB)

⑨u.status=false;

⑩ end for

4.5 抑制影響最大化啟發(fā)式算法

針對(duì)節(jié)點(diǎn)規(guī)模較大的社交網(wǎng)絡(luò)，可以采用啟發(fā)式算法來選取免疫信息種子節(jié)點(diǎn)集合以進(jìn)一步降低計(jì)算量.因此，基于本文提出的傳播模型，提出了異步信息抑制傳播啟發(fā)式算法-簡版(asynchronous information suppression propagation heuristic algorithm _easy, AISPH_E).AISPH_E算法綜合考慮了節(jié)點(diǎn)本身的特性以及其與鄰居節(jié)點(diǎn)的影響關(guān)系，給出了計(jì)算單個(gè)節(jié)點(diǎn)u的影響力公式為

(4)

其中，pu表示節(jié)點(diǎn)u的轉(zhuǎn)發(fā)概率，p(u,v)表示節(jié)點(diǎn)u與節(jié)點(diǎn)v間影響權(quán)重，|Nout(u)|表示u的出度節(jié)點(diǎn)數(shù)量，|N(u)|表示u的鄰居節(jié)點(diǎn)數(shù)量.AISPH_E算法每次選取影響力σ(u)最大的節(jié)點(diǎn)加入免疫信息種子集合，直到選出k個(gè)節(jié)點(diǎn)，具體流程如算法2所示：

算法2.異步信息抑制傳播啟發(fā)式算法-簡版.

輸入：社交網(wǎng)絡(luò)G(V,E)、信息從用戶u傳播到用戶v的概率p(u,v)、特定信息影響的初始節(jié)點(diǎn)集合IA、種子節(jié)點(diǎn)數(shù)目k；

輸出：免疫信息種子集合IB.

① 初始化IB為空集，大頂堆HB為空堆；

② foru∈VIA

③ 計(jì)算u的影響力σ(u)；

④ 將σ(u)插入HB

⑤ end for

⑥sort(HB)

⑦ while |IB≤k|

⑧ ifHB.peek!=NULL

⑨ 更新IB←IB∪{HB.peek}；

⑩HB.pop；

為了避免選取的種子節(jié)點(diǎn)的鄰居節(jié)點(diǎn)重合度過高，本文進(jìn)一步提出異步信息抑制傳播啟發(fā)式算法(asynchronous information suppression propagation heuristic algorithm, AISPH)，對(duì)AISPH_E算法中的節(jié)點(diǎn)影響力計(jì)算方式進(jìn)行改進(jìn)，改進(jìn)后的節(jié)點(diǎn)影響力計(jì)算為

(5)

其中，pu表示該節(jié)點(diǎn)的影響權(quán)重，p(u,v)表示節(jié)點(diǎn)u,v間影響權(quán)重，N(u)表示u的鄰居節(jié)點(diǎn)集合，Nout(u)表示u的出度節(jié)點(diǎn)集合，S表示已選擇的種子節(jié)點(diǎn)集合.

5 實(shí)驗(yàn)與分析

本節(jié)將在實(shí)驗(yàn)室高性能服務(wù)器計(jì)算集群上對(duì)獨(dú)立信息轉(zhuǎn)發(fā)預(yù)測與社交網(wǎng)絡(luò)特定信息傳播抑制進(jìn)行分布式并行實(shí)驗(yàn).單個(gè)計(jì)算節(jié)點(diǎn)的具體參數(shù)為：Inter Xeon Gold 6132.

5.1 數(shù)據(jù)獲取與預(yù)處理

本文主要抓取2018～2019年內(nèi)微博的真實(shí)數(shù)據(jù)以展開實(shí)驗(yàn)，具體步驟為:

首先，從微博社區(qū)管理中心選取經(jīng)過平臺(tái)驗(yàn)證確定為不實(shí)信息的微博，作為我們需要抑制的特定信息；接著，根據(jù)不實(shí)信息微博爬取參與過轉(zhuǎn)發(fā)的用戶，按時(shí)間順序還原不實(shí)信息微博的傳播過程，保留轉(zhuǎn)發(fā)鏈完整的不實(shí)信息微博；然后，將參與過轉(zhuǎn)發(fā)的用戶作為種子節(jié)點(diǎn)，通過爬蟲爬取每個(gè)用戶的各項(xiàng)個(gè)人信息、近期發(fā)布的微博以及其好友關(guān)系；最后，通過每個(gè)節(jié)點(diǎn)的被關(guān)注關(guān)系向外拓展，獲取帶有好友關(guān)系的社交關(guān)系網(wǎng).

經(jīng)過初步篩選，共獲取2 500條原創(chuàng)特定信息微博，涉及861 419名用戶，其中連邊有3 442 626條.對(duì)微博的轉(zhuǎn)發(fā)量情況進(jìn)行統(tǒng)計(jì)，如圖1所示：

Fig. 1 Microblog forwarding histogram圖1 微博轉(zhuǎn)發(fā)量直方圖

從圖1中可以看出，微博的轉(zhuǎn)發(fā)量主要集中20～100之間.因此，進(jìn)一步選擇轉(zhuǎn)發(fā)量在20～100之間的1 180條微博，根據(jù)參與這些微博轉(zhuǎn)發(fā)過程的用戶的相關(guān)信息構(gòu)建數(shù)據(jù)集.

由于微博文本的規(guī)范性較差，獲取的數(shù)據(jù)集需要進(jìn)行文本規(guī)范化處理，即通過正則表達(dá)式過濾微博文本中的標(biāo)點(diǎn)符號(hào)和表情符號(hào).

5.2 獨(dú)立信息轉(zhuǎn)發(fā)預(yù)測實(shí)驗(yàn)

本節(jié)將對(duì)轉(zhuǎn)發(fā)預(yù)測中不同特征的貢獻(xiàn)以及不同分類器的表現(xiàn)進(jìn)行對(duì)比，并在選定特征集與分類器后，與其他文獻(xiàn)中的算法進(jìn)行對(duì)比.

5.2.1 評(píng)價(jià)指標(biāo)

轉(zhuǎn)發(fā)預(yù)測問題實(shí)際上是一個(gè)二分類問題，而評(píng)價(jià)分類器性能的常用指標(biāo)有：準(zhǔn)確率(Accuracy)、精確率(Precision)、召回率(Recall)和F1值(F1-score).

根據(jù)分類器的輸出結(jié)果和真實(shí)標(biāo)簽，可以將預(yù)測結(jié)果分為4種：1)真正例(true positive,TP)，表示正樣本被分為正樣本的數(shù)量；2)假正例(false positive,FP)，表示負(fù)樣本被分為正樣本的數(shù)量； 3)真負(fù)例(true negative,TN)，表示負(fù)樣本被分為負(fù)樣本的數(shù)量;4)假負(fù)例(false negative,FN)，表示正樣本被分為負(fù)樣本的數(shù)量.因此，準(zhǔn)確率(Accuracy)、精確率(Precision)、召回率(Recall)和F1值(F1-score)可以定義為:

(6)

(7)

(8)

(9)

對(duì)于輸出概率的分類器需要定義閾值來確定正負(fù)樣本，在計(jì)算這4個(gè)指標(biāo)時(shí)，閾值選擇的不同會(huì)帶來不同的結(jié)果.因此，本研究將進(jìn)一步使用曲線下面積(area under curve，AUC)來評(píng)價(jià)輸出概率的不同分類器的性能.AUC指的是受試者工作特征(receiver operating characteristic, ROC)曲線下的面積.ROC曲線的橫坐標(biāo)為假正率(false positive rate,FPR)，縱坐標(biāo)為真正率(true positive rate,TPR)，該曲線代表了一個(gè)分類器在不同閾值下的分類效果.其中，F(xiàn)PR與TPR的計(jì)算公式為:

5.2.2 數(shù)據(jù)準(zhǔn)備

進(jìn)行轉(zhuǎn)發(fā)預(yù)測實(shí)驗(yàn)前，需要在5.1節(jié)中獲取的微博數(shù)據(jù)集的基礎(chǔ)上構(gòu)造轉(zhuǎn)發(fā)預(yù)測數(shù)據(jù)集.具體來說，在5.1節(jié)獲取的微博數(shù)據(jù)集中，將每條微博與轉(zhuǎn)發(fā)過該微博用戶標(biāo)注為正樣本，每條微博與未轉(zhuǎn)發(fā)過該微博用戶標(biāo)注為負(fù)樣本.

轉(zhuǎn)發(fā)微博的用戶遠(yuǎn)少于不轉(zhuǎn)發(fā)微博的用戶，因此，為了保證正負(fù)樣本平衡，本研究隨機(jī)采樣10 000條正樣本和10 000條負(fù)樣本構(gòu)成轉(zhuǎn)發(fā)預(yù)測數(shù)據(jù)集.

實(shí)驗(yàn)時(shí)，隨機(jī)將轉(zhuǎn)發(fā)預(yù)測數(shù)據(jù)集按8∶2的比例分成2部分：訓(xùn)練數(shù)據(jù)和測試集.模型在訓(xùn)練數(shù)據(jù)上訓(xùn)練時(shí)，使用5折交叉驗(yàn)證.

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

實(shí)驗(yàn)主要分為3部分：各類特征對(duì)于轉(zhuǎn)發(fā)預(yù)測的效果對(duì)比、不同的分類器在相同特征集上的效果對(duì)比以及選定特征集與分類器后，與其他文獻(xiàn)中的算法進(jìn)行對(duì)比.

1) 各類特征對(duì)于轉(zhuǎn)發(fā)預(yù)測的效果對(duì)比

實(shí)驗(yàn)對(duì)比的特征維度包含4個(gè)：

① 信息微博維度.分別用TF-IDF，word2vec，BERT生成微博文本的向量化特征，與該維度其他特征組成特征集合，分別表示為：I-TF-IDF，I-word2vec，I-BERT;

② 用戶維度(包括待預(yù)測用戶和信息微博作者用戶).將待預(yù)測用戶和微博作者的維度特征集合表示為Ⅱ;

③ 待預(yù)測用戶與信息微博作者的相似程度維度.將待預(yù)測用戶和微博作者的相似度特征集合表示為Ⅲ;

④ 待預(yù)測用戶歷史微博與信息微博的相似程度維度.將分別用TF-IDF，word2vec，BERT這3種方法生成的用戶歷史微博與當(dāng)前微博的相似度特征集合表示為IV-TF-IDF,IV-word2vec,IV-BERT.

為了對(duì)比各組特征的效果以及TF-IDF,word2vec,BERT提取文本向量特征的效果，每次實(shí)驗(yàn)僅僅使用其中一類特征，分類器采用Lightgbm，具體的實(shí)驗(yàn)結(jié)果如表2所示：

Table 2 Comparison of Prediction Results on Variousfeatures表2 各類特征預(yù)測效果對(duì)比

由表2可知，在本文提出的4個(gè)維度的特征中，維度③待預(yù)測用戶與信息微博作者的相似程度維度特征在當(dāng)前數(shù)據(jù)集上的效果最好，準(zhǔn)確率、精確率、召回率和F1值均是最高的；維度①信息微博維度下特征效果次之，平均F1值約為0.767；接著是維度②用戶維度(包括待預(yù)測用戶和信息微博作者用戶)特征和維度④待預(yù)測用戶歷史微博與信息微博的相似程度維度特征.維度①信息微博維度下，采用TF-IDF,word2vec以及BERT提取句子向量用作文本特征時(shí)，表現(xiàn)相差不大；維度④待預(yù)測用戶歷史微博與信息微博的相似程度維度下，采用TF-IDF,word2vec以及BERT生成的用戶歷史微博與當(dāng)前微博的相似度特征時(shí)，TF-IDF表現(xiàn)最好.因此，本文后續(xù)的實(shí)驗(yàn)統(tǒng)一采用TF-IDF，則維度①和維度④可以簡化表示為Ⅰ和Ⅳ.

將各維度特征組合后進(jìn)行實(shí)驗(yàn)，結(jié)果如表3所示.采用第Ⅰ,Ⅲ維度特征組合時(shí)，Precision最高；采用第Ⅰ,Ⅱ,Ⅲ維度特征組合時(shí)，Accuracy最高；采用第Ⅱ,Ⅲ,Ⅳ維度特征組合時(shí)，Recall最高；采用第Ⅰ,Ⅱ,Ⅲ,Ⅳ維度特征組合時(shí)，F(xiàn)1值最高.總體來看，使用第Ⅰ,Ⅲ維度特征組合的效果與同時(shí)使用四維度特征的效果相差不大.因而在實(shí)際應(yīng)用時(shí)，為提升整體效率，選擇使用第Ⅰ,Ⅲ維度特征組合.

Table 3 Comparison of Performance of Multi Class Feature Combinations表3 多類特征組合效果對(duì)比

Lightgbm模型在訓(xùn)練結(jié)束后，會(huì)輸出每個(gè)特征的重要性，反映特征在模型學(xué)習(xí)過程中的貢獻(xiàn)程度.重要性越高，則該特征對(duì)于轉(zhuǎn)發(fā)預(yù)測越有效.圖2展示了使用Ⅰ,Ⅲ類特征組合時(shí)，特征重要性的排名.

Fig. 2 Feature importance ranking when using type Ⅰ and Ⅲ features圖2 使用Ⅰ,Ⅲ類特征時(shí)特征重要性排名

從圖2中可以看到，用戶與作者的城市是否相同、用戶與作者關(guān)注列表的相似度、微博的平均TF-IDF是最為有效的3個(gè)特征.

2) 不同的分類器在相同特征集上的效果對(duì)比

在使用Ⅰ,Ⅲ維度特征組合的前提下，對(duì)單一模型：感知機(jī)(Perceptron)、邏輯回歸(Logistic Reg-ression, LR)、支持向量機(jī)(support vector machine, SVM)；集成模型：AdaBoost、隨機(jī)森林(Random Forest, RF)和Lightgbm共6種分類器進(jìn)行了對(duì)比.實(shí)驗(yàn)結(jié)果如表4所示:

Table 4 Performance Comparison of Each Classification Model表4 各分類器的效果對(duì)比

從表4可以看出，除Perceptron外的5種分類器的分類效果基本相近，這說明使用Ⅰ,Ⅲ維度特征組合，可以很好地區(qū)分正負(fù)樣本.從表4可以進(jìn)一步看出，Lightgbm在Accuracy,Precision和F1值上的表現(xiàn)是最佳的，盡管在Recall上的表現(xiàn)不是最好的，但是由于F1值是對(duì)Precision和Recall的整體評(píng)價(jià)，而Lightgbm取得了最高的F1值，所以綜合來看Lightgbm是性能最佳的分類器.

輸出是概率的4種分類器對(duì)應(yīng)的ROC曲線如圖3所示，對(duì)應(yīng)的AUC值如表5所示.

Fig. 3 ROC value comparison of each classifier圖3 各分類器的ROC曲線對(duì)比

Table 5 AUC Value Comparison of Each Classifier表5 各分類器的AUC值對(duì)比

可以看出Lightgbm的AUC最高，其次是Random Forest和AdaBoost，最后是LR.Lightgbm的表現(xiàn)與預(yù)期相符合，是綜合性能最佳的分類器.

3) 與現(xiàn)有轉(zhuǎn)發(fā)預(yù)測模型的對(duì)比

為了進(jìn)一步說明本文所提出模型的有效性，將該模型與現(xiàn)有研究中的轉(zhuǎn)發(fā)預(yù)測模型進(jìn)行對(duì)比.根據(jù)本文實(shí)驗(yàn)，將基于Ⅰ，Ⅲ類特征組合的Lightgbm分類器與相關(guān)領(lǐng)域現(xiàn)有研究進(jìn)行對(duì)比.

對(duì)比模型如下：

Zhang等人[3]提出的模型：一個(gè)基于影響局部性函數(shù)的邏輯回歸模型.模型中使用的特征有粉絲數(shù)、相互關(guān)注數(shù)、注冊(cè)時(shí)間、性別、是否認(rèn)證、用戶偏好于主題間的KL散度、用戶活躍鄰居數(shù)、距離微博發(fā)布時(shí)間的間隔、結(jié)構(gòu)影響力以及成對(duì)影響力.

SUA-ACNN[4].一個(gè)結(jié)合了卷積神經(jīng)網(wǎng)絡(luò)與注意力機(jī)制的模型.該研究微博轉(zhuǎn)發(fā)預(yù)測問題中，主要考慮的因素有微博作者特征、微博文本特征、待預(yù)測用戶特征和用戶興趣特征，并對(duì)它們進(jìn)行進(jìn)一步的細(xì)化.其中，在用戶興趣特征提取步驟中加入了注意力機(jī)制.

RCMTF[5].一個(gè)基于上下文感知、聯(lián)合矩陣-張量分解的轉(zhuǎn)發(fā)預(yù)測模型.該模型基于網(wǎng)絡(luò)結(jié)構(gòu)、消息內(nèi)容和歷史交互，設(shè)計(jì)了用戶相似度、消息相似度和成對(duì)影響的3個(gè)上下文因子矩陣.

與現(xiàn)有轉(zhuǎn)發(fā)預(yù)測模型的對(duì)比結(jié)果如表6所示.其中，本文的IIFP模型在4個(gè)評(píng)價(jià)指標(biāo)上均取得了了最好的表現(xiàn).Zhang等人[3]提出的模型與本文的思路相似，同樣是基于特征工程的機(jī)器學(xué)習(xí)方法，但實(shí)驗(yàn)結(jié)果不及本文的模型，說明本文選取了更有效的特征.SUA-ACNN[4]模型作為一個(gè)深度學(xué)習(xí)模型并沒有在本研究數(shù)據(jù)集上表現(xiàn)出更好的效果，可能由于深度學(xué)習(xí)往往需要海量數(shù)據(jù)，而本文數(shù)據(jù)集的微博轉(zhuǎn)發(fā)樣本較少，導(dǎo)致深度學(xué)習(xí)無法自動(dòng)提取有效特征.基于矩陣分解的RCMTF[5]模型在本研究數(shù)據(jù)集上同樣未能超越本文模型的性能，分析發(fā)現(xiàn)微博中存在一定數(shù)量的中文詞匯缺少預(yù)訓(xùn)練的中文詞向量，導(dǎo)致矩陣分解中基于詞向量計(jì)算的相似度矩陣不夠準(zhǔn)確，同時(shí)本研究數(shù)據(jù)用戶數(shù)量較大，造成矩陣十分稀疏，導(dǎo)致矩陣分解模型的性能未能達(dá)到原論文中的效果.

Table 6 Comparisonbetween IIFP and Existing Models表6 IIFP與現(xiàn)有模型的對(duì)比

5.3 社交網(wǎng)絡(luò)特定信息抑制實(shí)驗(yàn)

本節(jié)將分別進(jìn)行特定信息單獨(dú)傳播實(shí)驗(yàn)與特定信息與免疫信息共同傳播實(shí)驗(yàn)，并將本文提出算法與多種已有算法在運(yùn)行時(shí)間和抑制影響力2個(gè)方面進(jìn)行對(duì)比.

5.3.1 評(píng)價(jià)指標(biāo)

通常情況下，影響力最大化研究相關(guān)的評(píng)價(jià)方式有2種：影響范圍以及運(yùn)行時(shí)間.通過蒙特卡洛模擬的方式可以仿真信息傳播的影響范圍，多次求解取平均可以得出接近真實(shí)的影響范圍，而算法能否高效地選擇符合要求的種子節(jié)點(diǎn)集合則體現(xiàn)在算法的運(yùn)行時(shí)間上.于是，本研究將影響范圍和運(yùn)行時(shí)間作為評(píng)價(jià)算法效果的指標(biāo).

傳統(tǒng)的蒙特卡洛模擬傳播模型中，節(jié)點(diǎn)只能被激活一次，一旦激活狀態(tài)不再發(fā)生改變.本研究提出的傳播影響模型中，一個(gè)節(jié)點(diǎn)被激活為狀態(tài)A后，仍可能被狀態(tài)B的節(jié)點(diǎn)激活.因此在本文模型下的蒙特卡洛模擬算法如算法3所示：

算法3.計(jì)算種子集合影響范圍的蒙特卡洛模擬算法.

輸入：社交網(wǎng)絡(luò)G(V,E)、每條邊上的概率p(u,v)、特定信息影響集合IA、種子集合IB；

輸出：影響范圍resultA.

① 已被激活的用戶狀態(tài)集合activeA←IA，activeB←IB；

② foru∈activeA，v∈activeB

③ foru′∈Inf(u)activeA∪activeB

④ ifu.active(u′)= =success

⑤ 更新activeA←activeA∪{u′}

⑥ end if

① ② 2條特定不實(shí)信息來自微博社區(qū)管理中心(https://service.account.weibo.com)

⑦ end for

⑧ forv′∈Inf(v)activeB

⑨ ifv.active(v′)= =success

⑩ 更新activeB←activeB∪{v′}

將算法3的蒙特卡洛模擬重復(fù)實(shí)驗(yàn)10 000次，得到的影響范圍取平均值，即可獲得種子節(jié)點(diǎn)集合的影響范圍，從而評(píng)價(jià)算法的有效性.

5.3.2 數(shù)據(jù)準(zhǔn)備

在5.1節(jié)中獲取的1 180條特定信息微博的基礎(chǔ)上，隨機(jī)抽取30%作為實(shí)驗(yàn)對(duì)象進(jìn)行特定信息單獨(dú)傳播實(shí)驗(yàn)與特定信息與免疫信息共同傳播實(shí)驗(yàn).為展示特定信息單獨(dú)傳播時(shí)的影響范圍變化，選取2條特定不實(shí)信息展示其傳播過程：

特定不實(shí)信息(1)：關(guān)于三峽工程發(fā)電收入的歸屬①.

特定不實(shí)信息(2)：關(guān)于某輪奸犯仕途升至縣長的網(wǎng)絡(luò)謠言②.

5.3.3 對(duì)比算法

為了驗(yàn)證本文提出的算法的有效性，現(xiàn)將本文提出算法與多種已有算法進(jìn)行對(duì)比并根據(jù)評(píng)價(jià)指標(biāo)來分析結(jié)果，參與對(duì)比的算法有本文提出的AISPG和AISPH，AISPH_E以及Random算法、Proximity算法、Degree算法、Greedy算法.

參與對(duì)比的7個(gè)算法介紹：

1) AISPG算法.本文提出的異步信息抑制傳播貪心算法；

2) AISPH_E算法.本文提出的異步信息抑制傳播貪心算法-簡版，不考慮選取的種子節(jié)點(diǎn)存在重復(fù)鄰居節(jié)點(diǎn)的情況；

3) AISPH算法.本文提出的異步信息抑制傳播貪心算法；

4) Random算法.隨機(jī)選取種子節(jié)點(diǎn)集合；

5) Proximity算法.一種競爭影響最大化的算法，該算法每次都在需要被抑制的特定信息狀態(tài)的節(jié)點(diǎn)的鄰居節(jié)點(diǎn)中選取免疫信息種子節(jié)點(diǎn)；

6) DegreeHeuristic算法.度啟發(fā)式算法是一種經(jīng)典的啟發(fā)式算法，按照每個(gè)節(jié)點(diǎn)連邊的數(shù)量對(duì)節(jié)點(diǎn)進(jìn)行降序排列，選擇種子節(jié)點(diǎn)集合.

7) Greedy算法.計(jì)算每一個(gè)節(jié)點(diǎn)的邊際影響力，每一次選取當(dāng)前狀態(tài)下邊際影響力最大的節(jié)點(diǎn)加入種子節(jié)點(diǎn)集合.

5.3.4 實(shí)驗(yàn)結(jié)果

1) 特定信息單獨(dú)傳播實(shí)驗(yàn)

本文為了研究免疫信息的抑制效果，首先考慮網(wǎng)絡(luò)中未注入免疫信息的情況，觀察網(wǎng)絡(luò)中已有特定信息的傳播規(guī)律和傳播范圍.經(jīng)過10 000次蒙特卡洛模擬后，得到這些特定信息的平均影響范圍為573 724.55.由此可知，在不進(jìn)行抑制的情況下，特定信息可以自動(dòng)得到廣泛傳播.

為了更好地展示特定信息的影響范圍變化，使用數(shù)據(jù)準(zhǔn)備部分選取的2條特定信息展示其傳播過程.選取的2條特定信息均已在網(wǎng)絡(luò)中有一定范圍的傳播，實(shí)驗(yàn)中將該狀態(tài)作為實(shí)驗(yàn)的初始狀態(tài).表7中反映了選取的特定信息的初始傳播狀態(tài).

Table 7 Number of Nodes Covered by Specific Information表7 特定信息已覆蓋節(jié)點(diǎn)數(shù)

圖4(a)、(b)分別體現(xiàn)了蒙特卡洛模擬下特定信息(1)、特定信息(2)在網(wǎng)絡(luò)中的影響范圍隨步數(shù)變化的規(guī)律.

由圖4可以看出，盡管2條特定信息在傳播過程中的影響范圍變化情況有所不同，但是最終均達(dá)到了很大的影響范圍.

2) 特定信息與免疫信息共同傳播實(shí)驗(yàn)

本文提出的AISPG和AISPH_E，AISPH以及Random算法、Proximity算法、Degree Heuristic算法、Greedy算法的運(yùn)行時(shí)間的對(duì)比圖如圖5(a)所示，其中縱坐標(biāo)表示對(duì)數(shù)形式的算法運(yùn)行時(shí)間(ms)，橫坐標(biāo)表示種子節(jié)點(diǎn)數(shù)(個(gè)).從圖中可知，Greedy算法和AISPG算法的運(yùn)行時(shí)間要遠(yuǎn)大于其他算法.為了能夠更清晰地對(duì)比其他幾種算法的運(yùn)行時(shí)間，本文在圖5(b)中展現(xiàn)了除2種貪心算法外，其他算法的運(yùn)行時(shí)間對(duì)比，其中縱坐標(biāo)表示線性的算法運(yùn)行時(shí)間(ms)，橫坐標(biāo)表示種子節(jié)點(diǎn)數(shù)(個(gè)).

由圖5(a)可看出，Greedy算法運(yùn)行時(shí)間會(huì)隨著節(jié)點(diǎn)選取數(shù)量的增加而迅速增加并且遠(yuǎn)大于其他算法；由圖5(b)可以看出，幾種啟發(fā)式算法的運(yùn)行時(shí)間隨著種子節(jié)點(diǎn)選取數(shù)量的增加基本呈線性增加.

Fig. 4 The range of influence of a particular information in a network varies with the number of steps圖4 特定信息在網(wǎng)絡(luò)中的影響范圍隨步數(shù)變化

Fig. 5 Comparison of algorithm running time圖5 算法運(yùn)行時(shí)間對(duì)比

Fig. 6 Influence range comparison after suppression圖6 抑制后的影響范圍對(duì)比

本文提出的改進(jìn)的貪心算法AISPG算法雖然運(yùn)行時(shí)間也大于其他啟發(fā)式算法，但是其運(yùn)行時(shí)間隨著種子節(jié)點(diǎn)選取數(shù)量的增加并沒有明顯增大，可見是對(duì)Greedy算法效率的有效改進(jìn).

特定信息與免疫信息在社交網(wǎng)絡(luò)中共同傳播的抑制影響力實(shí)驗(yàn)結(jié)果對(duì)比如圖6所示.從圖6可以看出，在本文提出的特定信息傳播與抑制模型下，貪心算法選擇的種子節(jié)點(diǎn)相比于啟發(fā)式算法能達(dá)到更好的抑制效果.而本文提出的貪心算法AISPG能夠在提高運(yùn)行效率的前提下達(dá)到與傳統(tǒng)的Greedy算法接近的抑制效果；本文提出的啟發(fā)式算法AISPH和AISPH_E在算法效果方面雖然略遜于貪心算法，但時(shí)間復(fù)雜度低，更適用于在大型社交網(wǎng)絡(luò)中選取免疫信息節(jié)點(diǎn).

6 總結(jié)與展望

本文提出了不依賴于傳播模型的獨(dú)立信息轉(zhuǎn)發(fā)預(yù)測機(jī)制以及適用于特定信息與免疫信息共同傳播這一特殊場景的異步信息不平等競爭傳播模型，并根據(jù)該傳播模型提出了種子節(jié)點(diǎn)選取算法.實(shí)驗(yàn)驗(yàn)證，本文提出的轉(zhuǎn)發(fā)預(yù)測模型以及種子節(jié)點(diǎn)選取算法具有合理性與有效性.

本文構(gòu)建的獨(dú)立信息轉(zhuǎn)發(fā)預(yù)測機(jī)制考慮到了影響用戶興趣的固有特征.然而，用戶的興趣會(huì)隨著時(shí)間不斷變化.因此，在未來的研究中進(jìn)行用戶興趣點(diǎn)建模時(shí)，可以考慮加入時(shí)序特征，從而更準(zhǔn)確地挖掘用戶興趣的階段性變化.除此以外，如何衡量用戶在動(dòng)態(tài)網(wǎng)絡(luò)中的影響力也是值得進(jìn)一步關(guān)注的問題.

作者貢獻(xiàn)聲明：曹玖新提出研究選題，給出研究思路，設(shè)計(jì)研究方案，終審論文；高慶清完善論文思路，設(shè)計(jì)實(shí)驗(yàn)，完成部分主實(shí)驗(yàn)，撰寫論文；夏蓉清收集分析資料，完成部分主實(shí)驗(yàn)；劉偉佳歸納整理實(shí)驗(yàn)數(shù)據(jù)，校對(duì)論文；朱雪林完成對(duì)比實(shí)驗(yàn)部分；劉波給予論文思路上的指導(dǎo).