陳伯倫，朱國暢，紀(jì)敏，朱鴻飛，韋晨

（淮陰工學(xué)院 計(jì)算機(jī)與軟件工程學(xué)院，江蘇 淮安 223003）

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

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

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

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

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

從國內(nèi)外研究現(xiàn)狀可以看出，在負(fù)影響力抑制研究方面，傳統(tǒng)的方法將正負(fù)影響力傳播特征同等地看待，然而在真實(shí)環(huán)境中，相比于正影響力的傳播，負(fù)影響力的傳播速度更快，傳播范圍更廣。因此在負(fù)影響力傳播抑制的過程中，如何對負(fù)影響力的傳播范圍以及抑制節(jié)點(diǎn)的抑制范圍進(jìn)行合理的度量顯得格外重要，本文利用疊加的隨機(jī)游走策略對網(wǎng)絡(luò)的影響力傳播進(jìn)行度量，將影響力傳播的范圍控制在某一子圖中，設(shè)計(jì)出抑制負(fù)影響力傳播的有效方法。

1 問題的描述

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

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

2 算法的主要思想與步驟

對網(wǎng)絡(luò)中負(fù)節(jié)點(diǎn)影響力傳播的范圍進(jìn)行模擬，使用抽樣子圖的方法對抑制節(jié)點(diǎn)的綜合影響力進(jìn)行精確地度量，設(shè)計(jì)出抑制負(fù)影響力傳播的有效方法，算法步驟如下所示：

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

6) 根據(jù)滲流理論計(jì)算最優(yōu)抑制節(jié)點(diǎn)個(gè)數(shù)k=λNp|S|pm，其中pm為相變值；

7)選取綜合影響力排名靠前的k個(gè)節(jié)點(diǎn)作為負(fù)影響力抑制節(jié)點(diǎn)集合S?。

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

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

2.1 兩點(diǎn)之間影響力權(quán)值計(jì)算

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

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

在這基礎(chǔ)上，將t步及以前的結(jié)果加起來便得到SRW 的影響力權(quán)值，即

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

在得出兩個(gè)節(jié)點(diǎn)之間的影響力權(quán)值后，接下來可以求出每一個(gè)節(jié)點(diǎn)被負(fù)影響力節(jié)點(diǎn)激活的概率，如果節(jié)點(diǎn)的激活概率大于負(fù)影響力影響的閾值 θv，那么該節(jié)點(diǎn)將被負(fù)激活。

2.2 抑制節(jié)點(diǎn)的影響力子圖計(jì)算

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

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

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

圖2 節(jié)點(diǎn)u 與v 之間最大可能概率的路徑lFig.2 Pathlof the maximum possible probability between nodesuandv

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

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

根據(jù)式(4)可知如果使得子圖外的節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)的影響力權(quán)值滿足w(u,v)≤ε，即要求其滿足：

由此可得節(jié)點(diǎn)搜索半徑的取值范圍：

圖3 抑制節(jié)點(diǎn)的影響力子圖Fig.3 Influence sub-graph of restraining nodes

2.3 抑制節(jié)點(diǎn)集合大小的計(jì)算

當(dāng)完成節(jié)點(diǎn)影響力的模擬后，本文通過滲流來模擬網(wǎng)絡(luò)傳播影響力的固有能力，進(jìn)行最優(yōu)抑制節(jié)點(diǎn)個(gè)數(shù)的選取。在網(wǎng)絡(luò)G 中，本文通過改變傳播概率p的值，并在網(wǎng)絡(luò)G 上對節(jié)點(diǎn)進(jìn)行隨機(jī)選擇，通過這種模擬方式模擬了影響力擴(kuò)散的動(dòng)態(tài)演化。其中被選中節(jié)點(diǎn)所形成的最大連通子圖大小s與概率p之間就發(fā)生了冪律行為，在相變值pm處，s變化速率最快，意味著此時(shí)影響力傳播速度最快，因此本文取pm作為影響力傳播速度的上界，即當(dāng)網(wǎng)絡(luò)中傳播概率p>pm時(shí)，網(wǎng)絡(luò)傳播的能力變化已經(jīng)不明顯了，所以本文將pm作為網(wǎng)絡(luò)G 傳播概率的臨界概率，即滲流值，并作為網(wǎng)絡(luò)傳播影響力的固有能力的度量標(biāo)準(zhǔn)。因此本文抑制節(jié)點(diǎn)的個(gè)數(shù)定為k=λ×Np×|S|×pm，此數(shù)值為抑制節(jié)點(diǎn)個(gè)數(shù)的上界，如果超過此數(shù)值，那么其余的抑制節(jié)點(diǎn)的抑制效果是不明顯的。

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

并對其進(jìn)行排序，其中 α 為調(diào)節(jié)節(jié)點(diǎn)的影響力子圖和節(jié)點(diǎn)度的參數(shù)。本文將其設(shè)置成0.5。最后根據(jù)綜合抑制力選取前k個(gè)抑制節(jié)點(diǎn)作為負(fù)影響力抑制節(jié)點(diǎn)集合。

3 實(shí)驗(yàn)結(jié)果及分析

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

在實(shí)驗(yàn)?zāi)M中，本文通過4個(gè)真實(shí)數(shù)據(jù)集來對算法進(jìn)行測試與分析，4個(gè)真實(shí)數(shù)據(jù)集分別是：email[23]、socfbBowdoin47[24]、hamsterster[25]和socfb-Smith60[26]。其中，email 由歐洲大型研究機(jī)構(gòu)的電子郵件數(shù)據(jù)組成，數(shù)據(jù)由發(fā)送與接收的郵件信息組成，如果節(jié)點(diǎn)u和v之間至少收發(fā)過一次郵件，那么u和v之間存在一條邊。socfbBowdoin47和socfbSmith60 是從FaceBook 數(shù)據(jù)中提取出來的，代表著用戶之間是否是好朋友。如果節(jié)點(diǎn)之間是好友關(guān)系，那么節(jié)點(diǎn)之間存在一條邊。Hamsterster 是從hamsterster.com 網(wǎng)站上提取的朋友與親人信息。所有數(shù)據(jù)集的拓?fù)鋵傩匀绫? 所示，其中n、m分別為網(wǎng)絡(luò)中節(jié)點(diǎn)和邊的總數(shù)，網(wǎng)絡(luò)中最大節(jié)點(diǎn)的度用dmax表示，平均度用dˉ 表示。網(wǎng)絡(luò)的同配系數(shù)、聚集系數(shù)以及網(wǎng)絡(luò)的密度分別用r、C、D來表示。

表1 4個(gè)不同數(shù)據(jù)集的拓?fù)鋵傩訲able1 Topological properties of four different datasets

4個(gè)不同的數(shù)據(jù)集具有不同的網(wǎng)絡(luò)特性，例如email 數(shù)據(jù)集的同配系數(shù)r<0，表示度大的節(jié)點(diǎn)傾向性和度小的節(jié)點(diǎn)相連接；而其余3個(gè)數(shù)據(jù)集的r>0,表示度大的節(jié)點(diǎn)更傾向性和度大的節(jié)點(diǎn)相連接。hamsterster 數(shù)據(jù)集聚集系數(shù)C更高，因此相比于其余3個(gè)數(shù)據(jù)集而言節(jié)點(diǎn)之間的連接更加緊密。

3.2 最優(yōu)種子節(jié)點(diǎn)數(shù)量的選取

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

因此最終可以通過相變值計(jì)算出最優(yōu)種子節(jié)點(diǎn)的個(gè)數(shù)。如圖4 所示，本文4個(gè)數(shù)據(jù)集的相變值pm分別為0.020、0.009、0.034、0.008。

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

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

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

圖5 4 種經(jīng)典算法抑制影響力隨著負(fù)節(jié)點(diǎn)集合變化曲線Fig.5 Inhibition effect curves of the four classical algorithms with respect to the change of the negative node set

在圖5 中，橫坐標(biāo)為負(fù)種子節(jié)點(diǎn)占整個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)的百分比Np，縱軸上的IF 表示k個(gè)種子節(jié)點(diǎn)的綜合影響力之和。

計(jì)算公式為

其中，α ∈(0,1)為控制抑制節(jié)點(diǎn)個(gè)數(shù)和節(jié)點(diǎn)度影響力的參數(shù)。由實(shí)驗(yàn)結(jié)果可以發(fā)現(xiàn)，在不同數(shù)據(jù)集中，無論負(fù)種子集合大小如何變化，SRW 算法在選取抑制節(jié)點(diǎn)集合所取得的效果幾乎都是最優(yōu)的。

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

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

其中RBR 算法在Np值較小的時(shí)候基于反向元組通過抽樣的方法對負(fù)節(jié)點(diǎn)進(jìn)行抑制，準(zhǔn)確率較高。而FC_IBM 算法首先通過模糊聚類對網(wǎng)絡(luò)進(jìn)行社區(qū)劃分，雖然在社區(qū)結(jié)構(gòu)比較明顯的數(shù)據(jù)集上該算法的效果略優(yōu)，但該方法在社區(qū)不明顯的數(shù)據(jù)集中效果一般。因?yàn)樵诒疚牡?個(gè)數(shù)據(jù)集選取過程中，它們的社區(qū)結(jié)構(gòu)不是太明顯。并且真實(shí)數(shù)據(jù)集中存在著重疊社區(qū)的影響。因此本文提出的SRW 算法效果的魯棒性更強(qiáng)。

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

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

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

圖7 4 種經(jīng)典算法抑制集合種子成本隨著負(fù)節(jié)點(diǎn)集合變化曲線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 種算法抑制集合種子成本隨著負(fù)節(jié)點(diǎn)集合變化曲線Fig.8 Seed cost curves of the inhibition set of the three algorithms with respect to the change of the negative node set

從圖7 中可以看出，隨著負(fù)種子節(jié)點(diǎn)的增加，抑制節(jié)點(diǎn)集合的種子節(jié)點(diǎn)成本也逐漸增加，因?yàn)樾枰懈嗟姆N子節(jié)點(diǎn)來進(jìn)行負(fù)影響力的抑制。但是其中SRW 算法相對于Degree Centrality、PageRank、Random 算法，選取的抑制節(jié)點(diǎn)集合所需要的成本是最低的。從圖8 中SRW 算法與RBR 算法的對比過程中發(fā)現(xiàn)，雖然在Np較小時(shí)候RBR 算法的抑制影響力范圍較優(yōu)，但是他們選擇的種子的成本也較大。綜上所述，SRW 算法在給定的抑制節(jié)點(diǎn)數(shù)量的前提下可以最大化地影響到其余節(jié)點(diǎn)，并且所取的代價(jià)也是較優(yōu)的。

4 結(jié)束語

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