代價約束下基于隨機游走的負影響力傳播抑制方法

陳伯倫，朱國暢，紀敏，朱鴻飛，韋晨

（淮陰工學院 計算機與軟件工程學院，江蘇 淮安 223003）

近年來，隨著在線社交網絡的蓬勃發展，成千上萬的人通過形式多樣的媒介產生前所未有的海量數據，并且數據呈現出多源化、異構化的趨勢。其中，影響力最大化是社交網絡分析中的一項重要的研究課題，主要是通過網絡中的病毒式營銷來驅動，目的是找到在特定傳播模型下最大化影響力傳播的關鍵用戶子集[1-2]。

Morone 和Makse 在Nature上發表論文，對影響力最大化問題進行了深入探討[3]。影響力最大化的目標就是在群體中尋找一些關鍵的種子節點集合用于去最大化其余節點。例如：在病毒式營銷的情況下，公司希望依靠口碑推薦來增加其產品的銷售，通過挖掘網絡中的重要客戶的影響力去最大化宣傳效果[4]。2020 年新型冠狀病毒肺炎的爆發，牛津大學、哈佛大學醫學院、波士頓兒童醫院等團隊在Science上發表論文，他們基于中國百度地圖遷徙大數據平臺的數據，分析了研究人員的遷徙與疫情之間的相關關系，為研究病毒傳播提供了強有力的數據支撐[5]。另外，影響力最大化的研究對病毒傳播、政府部門進行輿情管控、虛假信息控制以及這些信息的發布源追蹤等提供了理論上的支撐，為社會的安全保障活動起到了應有的保障作用[6-7]。

影響力在傳播的過程中，存在著正影響力，例如同意、支持、好評等，也存在著諸如差評、謠言等負影響力，很多負面消息都在網絡中迅猛肆意地擴散，復雜網絡中影響力最大化問題目標是希望能夠最大程度地限制網絡中負影響力的擴散，切斷傳播途徑。新冠肺炎的爆發，網上出現了大量的謠言，這些謠言經過用戶的轉發大規模地擴散。例如，網絡中曾傳白巖松主持一場邀請鐘南山院士介紹疫情的活動新聞。一時間，各微信群、朋友圈、論壇，甚至一些大V 的博主都轉發了該新聞，后來經證實這條新聞是謠言。可以看出負面影響力傳播時間短，但是傳播速度快，影響范圍廣。因此，如何對負影響力進行抑制，通過一些措施來制止謠言的傳播顯得格外重要[8]。

負影響力傳播抑制最大化問題其實就是通過選擇一些種子節點來盡可能地阻止其競爭實體的影響傳播，He 等[9]稱此問題為影響阻塞最大化(influence blocking maximization，IBM)問題，同時證明了在競爭性線性閾值模型中IBM 的目標函數是亞模的，貪婪算法可以達到最優解。當社交網絡中出現負面信息并且部分用戶已經受其影響時，Arazkhani 等[10]提出了基于中心度測量的算法，以尋找適當的正影響種子節點進行擴散以最小化IBM 問題。譚振華等[11]結合引力學思想，對負面信息的傳播過程進行刻畫，并充分考慮用戶的個性化特征，對謠言的傳播進行抑制。Tong 等[12]發現經典的貪心算法與蒙特卡洛模擬相結合的算法運行時間過長，提出了一種隨機近似算法，在保證性能的同時提升了運行效率。劉亞州等[13]考慮到不同節點在受到負影響力影響時的差異性以及影響力在網絡上傳播的特性，進行負影響力傳播的研究。Lee 等[14]通過分析在影響擴散過程中節點的潛在影響趨勢，提出了影響分布重定向算法，通過重定向節點的影響分布，以最大化目標函數來定義影響擴散的初始種子節點。曹玖新等[15]通過K-核和節點的度，提出了基于核數層次特征和影響半徑的核覆蓋啟發式算法。Peng 等[16]通過引入社會關系圖評估節點影響力，然后使用選舉制查找最有影響力的節點，最后通過對前k個有影響力的節點采取免疫措施來阻止負影響力的傳播。陳晉音等[17]對網絡拓撲結構進行了修改，提出了基于信息級聯預測模型的抑制虛假消息傳播的算法。江成等[18]從負影響力傳播的廣度和深度兩個維度，對負面信息傳播影響力進行測度分析，從而設計出抑制負影響力傳播的啟發式策略。

目前還有一部分工作是基于網絡的社區結構的。Arazkhani 等[19]提出了一種使用模糊聚類和集中度度量來找到用于擴散正信息的節點的良好候選子集的方法。Lv 等[20]根據影響力的種子節點在社區中的分布，首先確定種子節點的數量，然后，選擇影響力最大的前k個節點，提出了一種網絡社區結構的模型，從而解決社交網絡中影響力擴散的局部性的問題。除此之外，Wang 等[21]提出了一種具有用戶體驗的動態謠言影響最小化模型，該模型同時考慮了謠言的全球知名度和吸引力以及用戶體驗效用的約束，為每個節點分配一個容忍時間閾值，如果用戶的阻止時間超過該閾值，則用戶對該網絡的滿意度將會降低。Zhu 等[22]發現位置信息可以在影響力傳播中發揮重要作用，針對位置感知影響塊最大化問題，通過尋找一個正種子集，以阻止負面影響在給定區域中的傳播，提出了基于四叉樹索引和最大影響樹狀結構的兩種啟發式算法。

從國內外研究現狀可以看出，在負影響力抑制研究方面，傳統的方法將正負影響力傳播特征同等地看待，然而在真實環境中，相比于正影響力的傳播，負影響力的傳播速度更快，傳播范圍更廣。因此在負影響力傳播抑制的過程中，如何對負影響力的傳播范圍以及抑制節點的抑制范圍進行合理的度量顯得格外重要，本文利用疊加的隨機游走策略對網絡的影響力傳播進行度量，將影響力傳播的范圍控制在某一子圖中，設計出抑制負影響力傳播的有效方法。

1 問題的描述

本文將社交網絡影響力傳播問題用圖的結構來進行模擬，首先用G=(V,E)來定義該網絡，其中V代表網絡中節點的集合，節點可以被正影響力激活也可以被負影響力激活。E代表節點之間邊的集合。如果社交網絡G 中存在兩個節點u和v，且u和v不是同一個節點，那么 (u,v)∈E表示u和v之間存在一條連邊，它們之間可以進行影響力的直接傳播，該傳播概率用p來表示。其中，n表示網絡G 中節點的總個數，即n=|V|，用m表示網絡G 中的總邊數，即m=|E|。那么影響力最大化問題即轉化成在圖G 中尋找k個種子節點使其能夠阻止節點的負影響力在網絡中的傳播。

在網絡G 中，如果想要選擇一些節點來抑制網絡中節點負影響力的傳播，則需要付出相應的代價。例如：某企業想通過明星代言來擴大自己的影響力，而每一位明星的出場費是不同的，并且企業的廣告宣傳費用是有限的，那么成本限制下影響力最大化就轉化成如何在有限的成本下，邀請到的明星能夠使得企業的影響力最大。因此，本文設 c ost(v)為節點v的代價，成本的總代價為Q。設I(SN,SP)為被負種子集合激活的頂點個數的期望值。 (SN為負種子集合，SP為正種子集合)因此，成本限制下的負影響力抑制問題的目的是在頂點集合VSN中選擇一個最優的正種子集合S?，使得I(SN,S?)最小：

2 算法的主要思想與步驟

對網絡中負節點影響力傳播的范圍進行模擬，使用抽樣子圖的方法對抑制節點的綜合影響力進行精確地度量，設計出抑制負影響力傳播的有效方法，算法步驟如下所示：

算法基于隨機游走的負影響力傳播抑制方法(SRW-IBM)

6) 根據滲流理論計算最優抑制節點個數k=λNp|S|pm，其中pm為相變值；

7)選取綜合影響力排名靠前的k個節點作為負影響力抑制節點集合S?。

算法的流程圖如圖1 所示。

圖1 算法流程Fig.1 Flow diagram of algorithm

2.1 兩點之間影響力權值計算

本文首先設置節點被負影響力影響的閾值θv，如果兩點之間的相似性大于該權值，那么該節點將被負激活。接下來對負節點的傳播范圍進行估計，設N(SN,G)為在網絡G中被負種子節點集合SN激活的頂點集合。我們將有疊加的局部隨機游走(superposed random walk，SRW)的相關思想與影響力傳播模型相結合，對負節點的傳播范圍進行度量。假設負影響力節點u從t時刻傳播，定義πt(u,v)為t+1 時刻負影響力正好傳播到節點v的概率，那么可以得到系統演化方程：

式中：π0(u)為一個N×1的向量，只有第u個元素為1，其他元素為0。其中矩陣P=[p(u,v)]。p(u,v)=a(u,v)/k(u)。a(u,v)為鄰接矩陣A中的元素，k(u)為節點u的度。設定各個節點的初始資源分布為q(u)，那么基于t步隨機游走的兩點之間影響力權值為

在這基礎上，將t步及以前的結果加起來便得到SRW 的影響力權值，即

對式（4）的計算，關鍵在于對 πl(u,v)的計算。設Hl(x)為由x出發所有長度不超過l 的路徑的集合。設路徑h∈Hl(x)，定義d(h)為h中頂點u到v的距離。則 πl(u,v)可以寫成：

在得出兩個節點之間的影響力權值后，接下來可以求出每一個節點被負影響力節點激活的概率，如果節點的激活概率大于負影響力影響的閾值 θv，那么該節點將被負激活。

2.2 抑制節點的影響力子圖計算

確定了負激活頂點的集合后，接下來需要對網絡中的每一個可能被負種子集合激活的節點v進行抑制，抑制其被負激活。如果v在被負激活之前能被正種子u激活，則稱u為v的抑制頂點。其中頂點v的抑制頂點集合，稱之為反向被抑制，用 RI(v,G)來表示。頂點u可以抑制被負激活的頂點集合，稱之為節點u的正向抑制，用PI(u,G)來表示。為阻止節點v在被激活成負節點之前被正激活，需要設計抑制頂點被負激活的規則，即求每個頂點v∈N(SN,G)的 RI(v,G)的集合S。本文首先設最大的抑制節點集合S=V?SN，在計算S中每個節點u的抑制集合 PI(u,G)過程中，對每一節點在整個網絡中進行遍歷是一項巨大的耗時工程，因此本文擬對S中節點影響力的傳播用抽樣子圖方法進行模擬，使得節點的正影響力在某一范圍內進行傳播，降低算法的搜索時間復雜度。

首先，文中定義Gu(r)是以u為中心，r為半徑的子圖。給定一個 ε>0，即可以求出一個關于目標節點u的子圖Gu(r)，使得Gu(r)中的頂點v與u的影響力不小于 ε，而Gu(r)外的頂點與u的影響力小于ε。這樣，可不必考慮Gu(r)以外的頂點，只需考慮Gu(r)中的節點與u的影響力。

接下來，在給定 ε 的情況下，關鍵是要計算節點u的子圖半徑r。記 πt(u,v)為 πt(u)的第v個分量，為影響力由頂點u出發，t時刻到達頂點v的概率。設G的子圖Gu(r)滿足：對所有的節點y∈G?Gu(r)，有wt(u,v)≤ε。因為y∈G?Gu(r)，那么節點v到節點u的最短路徑大于r，即影響力從u出發到v最快在r時間到達，即 π1(u,v)，π2(u,v)，…，πr?1(u,v)，全為0。對于t≥r，設k(u)=h，k(u)為節點u的度。則從u到v的路徑最大可能的概率是由圖2 所示的路徑l構成。路徑l滿足如下條件：起點u和終點v的度分別為k(u)和k(v)，路徑l中其余節點的度皆為2。

圖2 節點u 與v 之間最大可能概率的路徑lFig.2 Pathlof the maximum possible probability between nodesuandv

因此，粒子選擇此路徑的概率為

根據粒子選擇路徑的概率優化問題，本文使用牛頓法來進行求解。因此得出 πt(u,v)和πt(v,u)的取值范圍是和搜索半徑r相關的某一函數，記為

根據式(4)可知如果使得子圖外的節點和目標節點的影響力權值滿足w(u,v)≤ε，即要求其滿足：

由此可得節點搜索半徑的取值范圍：

圖3 抑制節點的影響力子圖Fig.3 Influence sub-graph of restraining nodes

2.3 抑制節點集合大小的計算

當完成節點影響力的模擬后，本文通過滲流來模擬網絡傳播影響力的固有能力，進行最優抑制節點個數的選取。在網絡G 中，本文通過改變傳播概率p的值，并在網絡G 上對節點進行隨機選擇，通過這種模擬方式模擬了影響力擴散的動態演化。其中被選中節點所形成的最大連通子圖大小s與概率p之間就發生了冪律行為，在相變值pm處，s變化速率最快，意味著此時影響力傳播速度最快，因此本文取pm作為影響力傳播速度的上界，即當網絡中傳播概率p>pm時，網絡傳播的能力變化已經不明顯了，所以本文將pm作為網絡G 傳播概率的臨界概率，即滲流值，并作為網絡傳播影響力的固有能力的度量標準。因此本文抑制節點的個數定為k=λ×Np×|S|×pm，此數值為抑制節點個數的上界，如果超過此數值，那么其余的抑制節點的抑制效果是不明顯的。

最后在確定完抑制種子節點的個數以后，需要從S集合中挑選出最優的抑制節點。算法首先計算每一個節點u的影響力子圖，然后計算抑制集合中節點的個數 |PI(u,G′)|，然后，結合節點的度k(u)計算出每一個節點的綜合抑制力：

并對其進行排序，其中 α 為調節節點的影響力子圖和節點度的參數。本文將其設置成0.5。最后根據綜合抑制力選取前k個抑制節點作為負影響力抑制節點集合。

3 實驗結果及分析

3.1 數據集介紹

在實驗模擬中，本文通過4個真實數據集來對算法進行測試與分析，4個真實數據集分別是：email[23]、socfbBowdoin47[24]、hamsterster[25]和socfb-Smith60[26]。其中，email 由歐洲大型研究機構的電子郵件數據組成，數據由發送與接收的郵件信息組成，如果節點u和v之間至少收發過一次郵件，那么u和v之間存在一條邊。socfbBowdoin47和socfbSmith60 是從FaceBook 數據中提取出來的，代表著用戶之間是否是好朋友。如果節點之間是好友關系，那么節點之間存在一條邊。Hamsterster 是從hamsterster.com 網站上提取的朋友與親人信息。所有數據集的拓撲屬性如表1 所示，其中n、m分別為網絡中節點和邊的總數，網絡中最大節點的度用dmax表示，平均度用dˉ 表示。網絡的同配系數、聚集系數以及網絡的密度分別用r、C、D來表示。

表1 4個不同數據集的拓撲屬性Table1 Topological properties of four different datasets

4個不同的數據集具有不同的網絡特性，例如email 數據集的同配系數r<0，表示度大的節點傾向性和度小的節點相連接；而其余3個數據集的r>0,表示度大的節點更傾向性和度大的節點相連接。hamsterster 數據集聚集系數C更高，因此相比于其余3個數據集而言節點之間的連接更加緊密。

3.2 最優種子節點數量的選取

為了計算網絡G的相變值pm，首先需要計算函數F(x)的變化速率。圖4 中，p為傳播概率，縱坐標為函數F(x)的變化速率rate，即函數dF(x)的值。圖4 中綠色的點用pm來表示，也是函數F(x)變化最快的時候。當網絡的傳播概率p小于相變值pm時，變化率r還處于較低水平，滲流后的網絡由零散的小團塊組成，當傳播概率p大于pm時，滲流后的網絡趨向由主團塊組成，逐漸呈現出以最大連通子圖為主的圖結構。本文相變值pm反應了網絡G傳播影響力的固有能力，也就是相變值反應網絡G中邊被激活的能力，即在影響力傳播模型下，被激活邊占總邊數的比例。

因此最終可以通過相變值計算出最優種子節點的個數。如圖4 所示，本文4個數據集的相變值pm分別為0.020、0.009、0.034、0.008。

圖4 不同數據集擬合函數變化速率Fig.4 Changing rate of fitting function in different datasets

3.3 影響力范圍的比較與分析

本文將SRW 算法和經典的度中心性(degree centrality，DC)[27]、網頁排序(pagerank，PR)[28]、隨機算法(random，RD)[29]的抑制影響力范圍變化隨著負種子集合大小變化的結果進行比較，實驗結果如圖5 所示。

圖5 4 種經典算法抑制影響力隨著負節點集合變化曲線Fig.5 Inhibition effect curves of the four classical algorithms with respect to the change of the negative node set

在圖5 中，橫坐標為負種子節點占整個網絡節點總數的百分比Np，縱軸上的IF 表示k個種子節點的綜合影響力之和。

計算公式為

其中，α ∈(0,1)為控制抑制節點個數和節點度影響力的參數。由實驗結果可以發現，在不同數據集中，無論負種子集合大小如何變化，SRW 算法在選取抑制節點集合所取得的效果幾乎都是最優的。

另外本文還將SRW 算法和基于反向元組的隨機化算法(reverse-tuple based randomized，RBR)[14]以及基于社區劃分算法FC_IBM[19]的抑制影響力范圍變化隨著負種子集合大小變化的結果進行比較，如圖6 所示。

圖6 3 種算法抑制影響力隨著負節點集合變化曲線Fig.6 Inhibition effect curves of the three algorithms with respect to the change of the negative node set

其中RBR 算法在Np值較小的時候基于反向元組通過抽樣的方法對負節點進行抑制，準確率較高。而FC_IBM 算法首先通過模糊聚類對網絡進行社區劃分，雖然在社區結構比較明顯的數據集上該算法的效果略優，但該方法在社區不明顯的數據集中效果一般。因為在本文的4個數據集選取過程中，它們的社區結構不是太明顯。并且真實數據集中存在著重疊社區的影響。因此本文提出的SRW 算法效果的魯棒性更強。

3.4 影響力成本的比較與分析

負影響力在傳播的過程中，需要選取性價比較高的節點作為抑制節點集合，這樣可以在有限的成本下最大化完成影響力的抑制。本文中，節點v的成本定義如下:

其值正比于節點的度，節點的度越大，表明需要選取該節點作為抑制該節點所需要的成本就越高。圖7 和圖8 分別為SRW 算法與經典算法以及SRW 算法與RBR、FC_IBM 算法在選取抑制節點集合的成本代價總和隨著負種子節點集合大小變化而變化的趨勢。

圖7 4 種經典算法抑制集合種子成本隨著負節點集合變化曲線Fig.7 Seed cost curves of the inhibition set of the four classical algorithms with respect to the change of the negative node set

圖8 3 種算法抑制集合種子成本隨著負節點集合變化曲線Fig.8 Seed cost curves of the inhibition set of the three algorithms with respect to the change of the negative node set

從圖7 中可以看出，隨著負種子節點的增加，抑制節點集合的種子節點成本也逐漸增加，因為需要有更多的種子節點來進行負影響力的抑制。但是其中SRW 算法相對于Degree Centrality、PageRank、Random 算法，選取的抑制節點集合所需要的成本是最低的。從圖8 中SRW 算法與RBR 算法的對比過程中發現，雖然在Np較小時候RBR 算法的抑制影響力范圍較優，但是他們選擇的種子的成本也較大。綜上所述，SRW 算法在給定的抑制節點數量的前提下可以最大化地影響到其余節點，并且所取的代價也是較優的。

4 結束語

在社交網絡的信息傳播機制中，不同用戶之間信息擴散往往會受到用戶之間影響力的影響。本文主要對負影響力的傳播進行抑制研究，在未知影響力傳播模型的基礎上，通過有疊加的隨機游走策略對負影響力傳播進行模擬。在抑制節點的影響力度量中，提出了節點的影響力傳播子圖的概念，使得抑制節點的影響力傳播局限在以該節點為源點的某一子圖中，有效地降低了影響力計算模擬的復雜度。在此基礎上，引入滲流的思想來進行抑制節點集合大小的選取，構建了代價約束下的抑制節點的最優選擇方法。實驗結果表明，該方法對負影響力抑制中，抑制節點的選取起著重要的指導性作用。