李　勁　岳　昆　張德海　劉惟一

1(云南大學(xué)軟件學(xué)院　昆明　650091)

2(云南省軟件工程重點實驗室　昆明　650091)

3　　　(云南大學(xué)信息學(xué)院　昆明　650091)

(lijin@ynu.edu.cn)

?

社會網(wǎng)絡(luò)中影響力傳播的魯棒抑制方法

李勁1,2岳昆2,3張德海1,2劉惟一3

1(云南大學(xué)軟件學(xué)院昆明650091)

2(云南省軟件工程重點實驗室昆明650091)

3(云南大學(xué)信息學(xué)院昆明650091)

(lijin@ynu.edu.cn)

Robust Influence Blocking Maximization in Social Networks

Li Jin1,2, Yue Kun2,3, Zhang Dehai1,2, and Liu Weiyi3

1(SchoolofSoftware,YunnanUniversity,Kunming650091)

2(KeyLaboratoryofSoftwareEngineeringofYunnanProvince,Kunming650091)

3(SchoolofInformationScienceandEngineering,YunnanUniversity,Kunming650091)

AbstractInfluence blocking maximization is currently a problem of great interest in the research area of social networks. Existing influence blocking methods assume negative influence sources are definitely known or non-adversarial. However, in real applications, it is hard to obtain the accurate information of influence sources. In addition, adversarial spreader may strategically select the seeds to maximize negative spread. In this paper, we aim to tackle the problems of influence blocking maximization with uncertain and strategic negative influence sources respectively. First, in order to increase the efficiency of the algorithms for mining blocking seeds, we discuss approximate estimation of the influence spread of negative seeds under the competitive linear threshold model. Based on the estimation, we propose a blocking seeds mining algorithm under the situation of finite uncertain and negative influence sources to maximize the expected influence blocking utility. In adversarial influence spread situations, one entity strategically attempts to maximize negative influence spread while the other one tries to block the negative propagation of its competing entity as much as possible by selecting a number of seed nodes that could initiate its own influence propagation. We model the interaction as a game and propose a polynomial time approximate algorithm for solving random blocking strategy based on min-max principle to decrease the worst negative influence spread. Finally, we make experiments on real data sets of social networks to verify the feasibility and scalability of the proposed algorithms.

Key wordssocial networks; influence blocking maximization; minmax principle; approximation algorithms; submodular function

摘要社會網(wǎng)絡(luò)中影響力傳播的有效抑制是當前社會網(wǎng)絡(luò)影響力傳播機制研究關(guān)注的問題之一.針對不確定性、策略性負影響源的影響力傳播抑制，討論社會網(wǎng)絡(luò)中影響力傳播的魯棒抑制問題.首先，作為提高算法運行效率的有效途徑，討論在競爭性線性閾值傳播模型下，負種子集傳播能力的近似估計方法，以此為基礎(chǔ)，提出不確定性負影響源情況下，期望抑制效果最大化的抑制種子集挖掘算法.然后，對于策略性傳播源，以最小化最壞情況下的影響力傳播范圍為目標，基于極小極大優(yōu)化作為抑制決策準則，提出了一個隨機抑制策略的多項式時間近似求解算法.最后，在真實的社會網(wǎng)絡(luò)數(shù)據(jù)集上，通過實驗驗證了所提出方法的有效性.

關(guān)鍵詞社會網(wǎng)絡(luò)；影響力抑制最大化；極小極大原理；近似算法；次模函數(shù)

近年來，許多學(xué)者針對面向多信息源發(fā)布的信息全局傳播機制及其預(yù)測模型，以影響力傳播范圍及傳播速度最大化為目標的關(guān)鍵結(jié)點集選取等問題開展了積極探索，并取得了一系列成果，極大地促進了社會網(wǎng)絡(luò)影響力傳播機制問題的研究[1-7].

然而，由于社會網(wǎng)絡(luò)本身具有開放性和虛擬性，各種不良、虛假信息、反動言論可以跨地域、跨國界地散布和傳播，嚴重危害社會穩(wěn)定及國家安全.因此，為有效抑制萬維網(wǎng)環(huán)境下社會網(wǎng)絡(luò)負面影響傳播，影響力傳播抑制問題也引起了學(xué)術(shù)界的關(guān)注，取得了一些初步的研究成果，成為社會網(wǎng)絡(luò)影響傳播機制研究的一個重要方面[8-11].

例如文獻[8]擴展了經(jīng)典的線性閾值模型，給出用于描述社會網(wǎng)絡(luò)中影響力競爭性傳播現(xiàn)象的競爭線性閾值模型(competitive linear threshold model，CLT)，定義影響力傳播抑制最大化問題(influence blocking maximization， IBM)，提出求解IBM問題的高效近似算法.文獻[9] 擴展了獨立級聯(lián)模型，定義多競爭獨立級聯(lián)模型(multi-campaign independent cascade model， MCICM)，及影響力傳播限制問題(eventual influence limitation problem， EIL)，給出了MCICM 模型下，EIL問題目標函數(shù)滿足次模性(submodular)的充分條件及EIL問題的近似求解算法.文獻[8-9]的研究工作均關(guān)注影響力傳播的抑制最大化問題，即最小化競爭對手的影響力傳播范圍.此外，文獻[10]從另一角度研究了影響力傳播的抑制，即限定影響力傳播范圍，求解最小抑制種子集.

不難看出，在解決影響力傳播抑制問題時，文獻[8-10]都假設(shè)在進行抑制決策時影響源已知，在此前提下，將影響力傳播抑制問題建模為相應(yīng)的優(yōu)化問題，進而提出求解問題的近似優(yōu)化算法.然而，在實際社會網(wǎng)絡(luò)應(yīng)用中，在做出抑制決策前，抑制方往往很難掌握影響源的準確信息，因此無法保證已有算法的抑制效果.其次，上述研究工作忽略了影響力傳播方“策略性”傳播行為，即傳播方可能會根據(jù)抑制方采取的抑制決策，有針對性地、策略性地選擇影響力傳播源，變更影響力傳播的途徑，改變影響力傳播結(jié)果，最終導(dǎo)致抑制方無法取得好的抑制效果.

由于影響力傳播與抑制行為的本質(zhì)是傳播方與抑制方之間的一種博弈關(guān)系，最近，文獻[11]以傳播方和抑制方可能選取的種子集作為策略空間，將影響力傳播與抑制的對抗行為建模為一個零和博弈(zero sum game)[12]，最優(yōu)抑制決策就是該博弈的Nash均衡解.然而，該博弈模型具有指數(shù)級的策略空間.為避免對博弈的策略空間進行枚舉，文獻[11]提出了基于策略生成技術(shù)的博弈Nash均衡的近似求解算法.雖然這一研究工作首次從博弈論的角度出發(fā)研究和分析傳播和抑制對抗行為，充分考慮到了影響力傳播行為的策略性，然而，基于策略生成技術(shù)的求解算法在最壞情況下需要窮舉整個策略空間，同時算法不能保證最后收斂到博弈的Nash均衡，也無法得到保證近似下界的近似解，因此只適用于規(guī)模較小的社會網(wǎng)絡(luò).

綜上，針對社會網(wǎng)絡(luò)中影響力傳播抑制問題，已有研究工作取得了積極的成果.但是面對不確定性和策略性影響源，如何有效、魯棒地進行影響力傳播抑制，仍是我們面臨的研究挑戰(zhàn).對此，針對不確定性影響源、策略性影響源2種情況，本文提出社會網(wǎng)絡(luò)中影響力傳播的魯棒抑制問題以及影響力傳播魯棒抑制的有效解決方法.

本文的研究內(nèi)容主要包括：

1) 用影響源上的概率分布來描述影響傳播源具有的不確定性.為有效提高算法的執(zhí)行效率，采用基于局部有向無環(huán)圖(local directed acyclic graph，LDAG)結(jié)構(gòu)的估計方法對影響源傳播范圍進行高效地近似估計，基于此，以期望抑制效果最大化為目標，提出了針對不確定傳影響源的抑制種子集挖掘算法.

2) 針對策略性影響源的影響傳播抑制問題，基于極小極大決策準則，以最小化最壞情況下的影響力傳播范圍為目標，提出用于影響力傳播抑制的多項式時間近似算法.

3) 在真實的社會網(wǎng)絡(luò)數(shù)據(jù)集上，通過實驗驗證了本文提出方法的有效性.對于不確定性影響源，相比較已有方法，本文的算法在執(zhí)行效率和抑制效果之間取得了很好的折中；對于策略性影響源，本文的算法能夠有效抑制最壞情況下的影響力傳播范圍，達到了影響力傳播的魯棒抑制效果.

1背景知識

(1)

在社會網(wǎng)絡(luò)影響力傳播抑制問題中，存在決策目標對立的雙方：傳播方(記為MAX)旨在通過選擇相應(yīng)的負種子集合D(也稱為負影響源)，使得從D出發(fā)的負影響力傳播效用最大化；抑制方(記為MIN)，其通過選取相應(yīng)的正種子集C，正影響從C出發(fā)傳播，負、正影響力按照CLT模型在網(wǎng)絡(luò)中傳播，最終，最小化MAX的負影響力傳播效用.

令{D}和{C}分別為傳播方和抑制方所有可能的負、正種子集組成的集合，也分別稱作傳播方、抑制方的策略集.基于此，社會網(wǎng)絡(luò)中影響傳播抑制問題定義如下[8]：

定義1. 在社會網(wǎng)絡(luò)G中，給定MAX的負種子集D∈{D}，求解MIN的最優(yōu)抑制種子集C*∈{C}，使得MAX方的負影響力傳播效用最小化：

(2)

定義1是最小化MAX的影響傳播效用.此外，也可用傳播效用的抑制最大化來等價定義該問題.給定D，定義種子集C的抑制效用函數(shù):

(3)

于是，影響力傳播抑制問題定義為求解MIN的最優(yōu)抑制種子集C*∈{C}，使得負影響力傳播抑制效果最大化:

(4)

文獻[8]證明，給定D，σ(C|D)是結(jié)點集V上的次模函數(shù).

2問題定義

在影響力傳播抑制問題中，抑制方不一定能準確地掌握負影響源的信息，其所獲得的負源信息往往帶有不確定性.設(shè)P是{D}上的概率分布空間，用{D}上的概率分布P∈P來描述抑制方對于負影響源信息的不確定性(在后文中，在強調(diào)P是MIN所掌握的關(guān)于的先驗概率信息時，將P記為Pprior).于是，面向不確定性影響源的影響力傳播抑制問題，記為RIBprior.

定義2. 在社會網(wǎng)絡(luò)G中，給定MAX的負種子集{D}上的概率分布Pprior，RIBprior定義為求解MIN的最優(yōu)抑制種子集C*∈{C}，使得MAX方的影響力傳播效用最小化，即：

(5)

在影響力傳播抑制問題中，雙方的決策效果是相互依存的，最終影響力傳播的結(jié)果不僅決定于MAX選擇的影響源，同時也決定于MIN采取的抑制策略.那么，在決策效用相互依存的情況下，MIN應(yīng)如何決策？從而實現(xiàn)對MAX的影響傳播進行有效抑制.從博弈論的角度來說，影響傳播、抑制對抗行為構(gòu)成MAX和MIN之間的一個博弈.對于MIN來說，如果不能預(yù)先獲知MAX決策行為，那么，采取極小極大準則進行抑制決策是合理、有效的選擇.另外，MIN采取隨機抑制策略可以獲得更好的期望抑制效用.

綜上，面向策略性影響源的影響力傳播抑制問題，記為RIBminmax.

定義3. 令{C}是MIN的抑制種子集集合，Q是{C}上的概率分布空間.任意概率分布Q∈Q稱作MIN的隨機抑制策略，即MIN按照Q從{C}中選擇種子集C進行抑制.面對策略性影響力傳播源，MIN按照極小極大決策準則，采取隨機策略Q*∈Q對MAX負影響力傳播進行抑制，使得:

(6)

(7)

只是式(6)的一個特例.

3影響力傳播抑制優(yōu)化算法

3.1影響力傳播效用的近似估計

在RIBprior和RIBminmax問題中，均涉及對影響力傳播效用inf(D,C)進行計算.由式(1)可知，inf(D,C)是關(guān)于閾值隨機向量θ+和θ-的期望值，準確估計inf(D,C)需要進行大量的隨機實驗，計算代價較高.

為有效提高算法的運行效率，本文采用文獻[8]提出的基于LDAG的方法對inf(D,C)進行近似估計，即：基于網(wǎng)中除種子結(jié)點之外的所有結(jié)點的負激活概率之和作為負影響傳播效用的度量標準:

(8)

其中，p-(v|D,C)是結(jié)點v在負種子集D，抑制種子集C下的負激活概率.關(guān)于p-(v|D,C)的計算方法詳見文獻[8].

3.2RIBprior問題的抑制種子集挖掘算法

首先分析RIBprior問題目標函數(shù)的性質(zhì).由式(3)定義的抑制效用函數(shù)σ(C|D)可知，給定Pprior，有:

由于inf(Pprior,?)是常數(shù)，RIBprior可等價地描述為

基于3.1節(jié)介紹的影響力傳播效用的近似估計方法，當MAX的負種子集{D}是有限(設(shè)包含m個負種子集)的情況下，討論期望抑制效用最大化的抑制種子集挖掘算法.設(shè){D}m={D1,D2,…,Dm}(Di?V)是包含m個負種子集的集合.Pm是{D}m上的一個概率分布.隨機策略Pm的期望影響力傳播效用可用負激活概率表示為

為算法描述方便，引入記號γ-(v|Pm,C)，即在Pm和C下，任意結(jié)點v的負激活概率的期望值:

于是，可重寫:

也就是說，inf(Pm,C)是結(jié)點負激活概率的期望值之和.算法1給出了期望抑制效用最大化的抑制種子集挖掘算法，其基本思想如下：

步驟1. 初始化階段.對于網(wǎng)中每個結(jié)點v，初始化與其負激活概率計算相關(guān)的子圖結(jié)構(gòu).對于網(wǎng)中的每個結(jié)點u，初始化其單獨作為抑制結(jié)點時的抑制效用.

步驟2. 抑制種子挖掘階段.本階段從網(wǎng)中挖掘k個抑制種子.算法的執(zhí)行過程與采用貪心法挖掘抑制種子集是一致的，即每次迭代，從VC中選取最大邊際抑制效用值的結(jié)點作為抑制種子加入到C中.每次迭代完成后，更新各個結(jié)點的邊際抑制效用值.經(jīng)過k次迭代完成抑制種子集的挖掘.不過，與貪心法不同的是：算法1采用γ-值來度量抑制效用值.

算法1.RIBprior問題的抑制種子集挖掘算法Aprior.

輸入:G=[V,E],{D}m,{D}m上的概率分布Pm,LDAG結(jié)構(gòu)控制參數(shù)φ、抑制種子集大小k;

①C←?;

② for eachv∈Vdo

④ end for

⑤ for eachu∈Vdo

⑥Δ-(u)←0;

⑦ end for

⑧ for eachv∈Vdo

⑩before←γ-(v|Pm,?),after←γ-(v|Pm,{u}),Δ-(u)←Δ-(u)+(before-after);

Δ-(u)←Δ-(u)-(γ-(s|Pm,C∪

{u})-γ-(s|Pm,C)),

Δ-(u)←Δ-(u)+(γ-(s|Pm,C∪

{c,u})-γ-(s|Pm,C∪{c}));

Fig. 1　Update of the nodes’ marginal blocking utility.圖1　邊際抑制效用更新示意圖

3.3RIBminmax問題的隨機抑制策略求解算法

由定義3可知，RIBminmax問題歸結(jié)為一個極小極大(minmax)優(yōu)化問題.求解MIN的極小極大隨機抑制策略Q*等價于:MIN和MAX分別采用隨機策略P和Q，并以inf(P,Q)作為決策效用函數(shù)進行零和博弈，而Q*就是MIN的Nash均衡解.

零和博弈的Nash均衡解可以通過2種方法進行求解，即基于線性規(guī)劃求解[12]和基于迭代求解[16].然而，采用上述2種方法求解RIBminmax問題，存在2個困難.

1) 基于線性規(guī)劃的求解方法.首先，在RIBminmax問題中，負種子集D∈{D}和抑制種子集C∈{C}的數(shù)目與網(wǎng)絡(luò)中的結(jié)點呈指數(shù)關(guān)系增長.于是，基于線性規(guī)劃求解Q*需要枚舉指數(shù)級的約束關(guān)系且線性方程中含有指數(shù)級個數(shù)的變量.其次，線性規(guī)劃方法需要預(yù)先確定博弈效用矩陣中的效用值，也就是說在求解RIBminmax問題時，對于任意D∈{D}和C∈{C}，需先確定inf(D,C)值，當{D}或{C}的數(shù)目大時，顯然是不現(xiàn)實的.

2) 基于迭代的求解方法.迭代方法在算法迭代求解過程中逐步生成效用矩陣，克服了規(guī)劃求解方法面臨的困難.然而，該方法的收斂性無法得到保證.同時，即便算法收斂，也無法保證所得解的求解質(zhì)量[16].

算法2. 隨機抑制策略的求解算法Aminmax.

輸入:G=V,E,0<μ≤1,LDAG結(jié)構(gòu)控制參數(shù)φ、擬挖掘的正種子集大小k、算法終止的閾值ε>0;

① 初始化MAX的傳播策略權(quán)重:

③ 生成MAX隨機策略P(t),即:

④ 針對隨機策略P(t)，基于算法1求解MIN的近似抑制種子集

⑥ 更新MAX傳播策略的權(quán)重:

⑦t=t+1;

⑧ end for

在假定MAX的傳播策略集{D}含有有限的m個負種子集的情況下(記為{D}m)，提出一個求解Q*的多項式時間的近似算法，即算法2.其基本思想是：時刻t，MAX按照一定的隨機策略選擇負種子集，針對該隨機策略，MIN選擇最優(yōu)抑制種子集C(t)∈{C}進行抑制.在時刻t+1，根據(jù)D∈{D}m在C(t)的傳播效用，MAX更新D的權(quán)重，即傳播效用越大的D，獲得越大的權(quán)重，并按照各策略的在前t個時刻的累積權(quán)重來確定時刻t+1的隨機傳播策略P(t).完成T次博弈后，由T個抑制種子集C(1)，C(2)，…，C(T)確定{C}上的一個隨機抑制策略，該隨機抑制策略就是最優(yōu)隨機抑制策略的近似解.

對算法2進行說明：步驟④即MIN對P(t)的“最優(yōu)響應(yīng)”.在雙方進行第t次博弈時，MAX采取P(t)作為隨機策略(初始時P(t)是均勻分布，即P(1)=1m).MIN對P(t)進行最優(yōu)響應(yīng)，即MIN采取C(t)對MAX進行抑制：

(9)

由算法1可知，求解C(t)歸結(jié)為一個次模函數(shù)的最大化問題，因此，存在保證近似下界的近似算法，例如基于貪心法的次模函數(shù)的最大化求解方法.于是，由算法1可獲得C(t)的1β(近似抑制策略(t)(β=1-1e)，滿足：

(10)

其中，C*是對P(t)的最優(yōu)響應(yīng).

綜上，算法2 克服了已有的線性規(guī)劃和迭代方法求解Q*所面臨的困難，給出了求解最優(yōu)隨機抑制策略的有效近似方法.

定理1證明了算法2在多項時間內(nèi)可求得RIBminmax問題的隨機近似抑制策略.

定理1. 給定近似因子0<ε<1.設(shè)m是{D}m中負種子集的個數(shù).在算法2 中，時刻t，MAX采取隨機傳播策略P(t)，MIN基于1β(近似算法求解抑制種子集(t)對P(t)響應(yīng).那么，經(jīng)過4lnm次迭代后可獲得求解RIBminmax問題的近似解，使得：

其中，β=1-1e.

定理1的證明見附錄A.

4實驗結(jié)果

4.1實驗環(huán)境設(shè)置

所有實驗在NetHEPT和NetPHY兩個真實數(shù)據(jù)集上完成(數(shù)據(jù)下載自文獻[17]).按照文獻[8]描述的方式，我們對數(shù)據(jù)集進行了預(yù)處理，并采用廣度優(yōu)先搜索的方法，從完成預(yù)處理后的NetHEPT和NetPHY中抽取了相應(yīng)的連通子圖.表1給出了實驗中所用到的子圖數(shù)據(jù)的統(tǒng)計信息:

Table 1　Statistics Information of the Experimental Data

所有實驗程序采用C++語言編寫，編譯器版本gcc 4.8.2.實驗運行環(huán)境：Intel Xeon CPU E5620 2.4 GHz，8 GB內(nèi)存的服務(wù)器、操作系統(tǒng)Linux Ubuntu 14.04 LTS.

4.2算法的抑制效果

4.2.1抑制效果的度量標準

在算法1和算法2中，算法的目標函數(shù)定義為所有結(jié)點的負激活概率的期望值之和.在求解抑制種子集(或隨機抑制策略)后，為將抑制效用與式(1)的定義保持一致，求得每個結(jié)點在給定正、負種子情況下的負激活概率，并以此為基礎(chǔ)進行重復(fù)實驗1 000次，以隨機實驗時負激活的結(jié)點集大小的平均值，作為影響傳播的抑制效果.

4.2.2Aprior算法的抑制效果

Fig. 2　Comparison of the blocking results on NetHEPT-600.圖2　NetHEPT-600上不同算法抑制效果比較

為驗證算法1的有效性，將其與其他抑制算法進行了對比實驗.1)Greedy算法.基于貪心法挖掘抑制種子集,在每次挖掘抑制種子時，采用10 000次蒙特卡羅仿真來估計結(jié)點的期望邊際抑制效用.2)Random算法.等概率從圖中選取大小為k的抑制種子集.3)Degree算法以結(jié)點度為概率權(quán)重，隨機選取k個抑制種子構(gòu)成抑制種子集.

考慮到Greedy算法的運行效率，只在2個子圖：NetHEPT-600和NetPHY-600進行實驗.首先，按照均勻分布，隨機地從子圖結(jié)點集V中抽取20個結(jié)點生成負種子集Di，一共生成100個負種子集Di構(gòu)成{D}m=100，記Pprior=1m是{D}m=100上的均勻分布.其次，對抑制種子集C= 10，20，30，40，50，60執(zhí)行4種抑制種子集挖掘算法，并對比期望抑制效果.其中，Aprior算法中參數(shù)φ=0.01.

圖2和圖3分別給出了4種算法在NetHEPT-600和NetPHY-600數(shù)據(jù)集上的期望抑制效果對比結(jié)果.圖4給出了Greedy算法和Aprior算法分別在HEPT和PHY數(shù)據(jù)集上的運行時間對比結(jié)果.

Fig. 3　Comparison of the blocking results on NetPHY-600.圖3　NetPHY-600上不同算法抑制效果比較

Fig. 4　Running time comparison of Greedy and Aprior algorithms.圖4　Greedy與Aprior算法運行時間比較

由實驗結(jié)果可知，相比較Random，Degree兩種算法，Greedy，Aprior算法在抑制效果上均有顯著的提升.其中，Greedy算法具有最好的抑制效果，但該算法在執(zhí)行過程中需要通過隨機仿真來評價結(jié)點的邊際抑制效用，運行時間較長，不適用于大尺寸數(shù)據(jù)集.Aprior算法在抑制效果上與Greedy算法差距不大，且該算法采用基于LDAG結(jié)構(gòu)的方法對結(jié)點的邊際抑制效用進行近似評估，算法運行時間顯著減少.因此，Aprior算法在抑制效果和算法運行時間2方面取得了很好的折中.

4.2.3Aminmax算法的抑制效果

首先，為直觀展示Aminmax算法的抑制效果，將其與Aprior算法進行了對比.其次，為說明Aminmax算法在求解抑制策略上的有效性和優(yōu)勢，將其與文獻[11]提出的基于迭代的零和博弈求解算法(double oracle algorithm,Aoracle)進行對比.實驗采用NetHEPT-6000和NetPHY-6000數(shù)據(jù)集.

圖5直觀地展示Aminmax算法對最具傳播能力的負種子集的傳播抑制效果.對于NetPHY-6000數(shù)據(jù)集，當每個抑制種子集大小k=50時，{D}m中100個不同的負種子集分別在：無抑制種子集、Aprior算法的抑制種子集以及Aminmax算法的隨機抑制策略下的負激活結(jié)點(期望)數(shù)目分布的情況.3種情況下負激活結(jié)點數(shù)目的平均值分別為：1003.15，597.54，628.21.此外，圖5中用箭頭標示了Aprior，Aminmax算法進行抑制時，最大的負激活結(jié)點數(shù)目(其中，Aprior算法抑制時，最大負激活結(jié)點數(shù)目為1121，而Aminmax算法抑制數(shù)目為896).

Fig. 5　Demonstration of blocking result of Aprior and Aminmax on NetPHY-6000.圖5　Aprior和Aminmax算法在NetPHY-6000的抑制結(jié)果示例

文獻[11]采用線性規(guī)劃和Aoracle算法來求解博弈的Nash均衡解.由于數(shù)據(jù)集包含6 000個結(jié)點，因此，采用函數(shù)pagerank-oracle作為Aoracle算法，線性規(guī)劃則采用軟件包CPLEX 12.6[18]完成.在NetHEPT-6000和NetPHY-6000數(shù)據(jù)集上，對比實驗的結(jié)果相似，因此，只給出在NetPHY-6000的結(jié)果.此外，當抑制種子集大小超過150時，Aoracle算法無法在有限時間內(nèi)輸出結(jié)果，于是只給出抑制種子集在150以內(nèi)的對比結(jié)果.

圖6給出了Aoracle和Aminmax算法的抑制效果對比結(jié)果.當抑制結(jié)點數(shù)少于70時，Aoracle算法的平均抑制效果和最差情況的抑制效果要優(yōu)于Aminmax算法.隨著抑制結(jié)點數(shù)增加2個算法的期望抑制效果相近，而對于最差情況的抑制效果Aminmax算法明顯比Aoracle算法穩(wěn)定.主要原因是隨著抑制結(jié)點數(shù)的增加，Aoracle算法不能保證收斂，這影響了算法的平均抑制效果.圖7給出了Aoracle和Aminmax算法的求解時間對比結(jié)果.Aminmax算法運行時間基本隨抑制結(jié)點集的大小線性增長，然而，Aoracle算法的運行時間隨抑制結(jié)點集大小快速增長.綜上，對于小數(shù)據(jù)集而言，Aoracle算法有著不錯的抑制效果和合理的求解時間，然而，對于大數(shù)據(jù)集來說，在抑制效果和求解時間上Aminmax算法更有優(yōu)勢.

Fig. 6　Comparison of the worst-case and average-case blocking results of Aoracle and Aminmax on NetPHY-6000.圖6　Aoracle和Aminmax算法NetPHY-6000平均及最差抑制效果對比

Fig. 7　Running time comparison of Aoracle and Aminmax on NetPHY-6000.圖7　Aoracle和Aminmax算法在NetPHY-6000運行時間對比

5結(jié)束語

影響力傳播的建模和分析及其控制是當前社會網(wǎng)絡(luò)研究的重要內(nèi)容.其中，影響傳播的有效抑制是當前研究面臨的一個新的挑戰(zhàn).針對實際應(yīng)用環(huán)境中，不確定性負影響源、策略性負影響源2種情況，本文提出了社會網(wǎng)絡(luò)中負面影響傳播的魯棒抑制問題.針對不確定性負影響源的情況，以期望抑制效果最大化為目標，提出了抑制種子集挖掘算法；針對策略性負影響源的情況，以極小極大優(yōu)化作為決策準則，提出了多項式時間的隨機抑制策略的近似求解算法.最后，在實際社會網(wǎng)絡(luò)數(shù)據(jù)集的實驗結(jié)果驗證了本文提出算法的有效性.

在本文研究的基礎(chǔ)上，未來可以在3個方面繼續(xù)開展研究.1)本文中影響力傳播模型是對線性閾值模型擴展而得，而對于其他典型的傳播模型，例如獨立級聯(lián)模型進行擴展，進而提出相應(yīng)的影響力競爭性傳播模型，并提出該模型下的針對不確定性負影響源、策略性負影響源的影響傳播抑制算法;2)社會網(wǎng)絡(luò)的圖結(jié)構(gòu)對影響傳播和抑制有很大的影響，深入研究圖結(jié)構(gòu)與影響傳播、抑制之間的關(guān)系，并提出基于圖結(jié)構(gòu)信息的負影響傳播的有效抑制算法;3)針對大尺寸社會網(wǎng)絡(luò)數(shù)據(jù)，如何基于圖抽樣的方法[19]進一步在抑制策略的求解效率和求解質(zhì)量之間進行有效折中，這些都是將來值得研究的課題.

參考文獻

[1]Wu Xindong, Li Yi, Li Lei. Influence analysis of online social networks [J]. Chinese Journal of Computers, 2014, 37(4): 735-752(in Chinese)(吳信東, 李毅, 李磊. 在線社交網(wǎng)絡(luò)影響力分析[J]. 計算機學(xué)報, 2014, 37(4): 735-752)

[2]Yang Shiqiang, Cui Peng. The Information propagation model of social media[J]. Communications of CCF, 2011, 7(12): 20- 24 (in Chinese)(楊士強, 崔鵬. 社區(qū)媒體信息傳播機制[J]. 中國計算機學(xué)會通訊, 2011, 7(12): 20-24)

[3]Leskovec J, Krause A, Guestrin C, et al. Cost-effective outbreak detection in networks[C]Proc of the 13th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2007: 420-429

[4]Tian Jiatang, Wang Yitong, Feng Xiaojun. A new hybrid algorithm for influence maximization in social networks [J]. Chinese Journal of Computers, 2011, 34(10): 1956-1965 (in Chinese)(田家堂, 王軼彤, 馮小軍. 一種新型的社會網(wǎng)絡(luò)影響最大化算法 [J]. 計算機學(xué)報, 2011, 34(10): 1956-1965)

[5]Chen Hao, Wang Yitong. Threshold-based heuristic algorithm for influence maximization[J]. Journal of Computer Research and Development, 2012, 49(10): 2181-2188 (in Chinese)(陳浩, 王軼彤. 基于閾值的社交網(wǎng)絡(luò)影響力最大化算法[J]. 計算機研究與發(fā)展, 2012, 49(10): 2181-2188)

[6]Chen W, Yuan Y, Zhang L. Scalable influence maximization in social networks under the linear threshold model [C]Proc of the 10th IEEE Int Conf on Data Mining. Piscataway, NJ: IEEE, 2010: 88-97

[7]Goyal A, Lu W, Lakshmanan L V S. Simpath: An efficient algorithm for influence maximization under the linear threshold model [C]Proc of the 11th IEEE Int Conf on Data Mining. Piscataway, NJ: IEEE, 2011: 211-220

[8]He X, Song G, Chen W, et al. Influence blocking maximization in social networks under the competitive linear threshold model [C]Proc of the SIAM Int Conf on Data Mining. Philadelphia, PA: SIAM, 2012: 463-474

[9]Nguyen N P, Yan G, Thai M T, et al. Containment of misinformation spread in online social networks[C]Proc of the 3rd Annual ACM Web Science Conf. New York: ACM, 2012: 213-222

[10]Budak C, Agrawal D, El Abbadi A. Limiting the spread of misinformation in social networks[C]Proc of the 20th Int Conf on World Wide Web. New York: ACM, 2011: 665-674

[11]Tsai J, Nguyen T H, Weller N, et al. Game-theoretic target selection in contagion-based domains [J]. The Computer Journal, 2014, 57(6): 893-905

[12]Myerson R B. Game Theory: Analysis of Conflict [M]. Cambridge, MA: Harvard University Press, 1997

[13]Kempe D, Kleinberg J, Tardos é. Maximizing the spread of influence through a social network[C]Proc of the 9th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2003: 137-146

[14]Fujishige S. Submodular Functions and Optimization [M]. Amsterdam: Elsevier Science Press, 2005

[15]Nemhauser G L, Wolsey L A, Fisher M L. An analysis of approximations for maximizing submodular set functions[J]. Mathematical Programming, 1978, 14(1): 265-294

[16]Halvorson E, Conitzer V, Parr R. Multi-step multi-sensor hider-seeker games[C]Proc of the 21st Int Joint Conf on Artificial Intelligence. San Francisco: Morgan Kaufmann, 2009: 159-166

[17]Chen W, Social network dataset [EBOL]. Beijing: Microsoft Research Laboratory, 2010 [2014-12-09]. http:research.microsoft.comen-uspeopleweicprojects.aspx

[18]IBM Corporation. CPLEX Optimizer[CP]. New York: IBM Corporation, 2009 [2014-12-09]. http:www-01.ibm.comsoftwarecommerceoptimizationcplex-optimizerindex.html

[19]Ribeiro B, Towsley D. Estimating and sampling graphs with multidimensional random walks[C]Proc of the 10th ACM SIGCOMM Conf on Internet Measurement. New York: ACM, 2010: 390-403

[20]Freund Y, Schapire R E. Adaptive game playing using multiplicative weights [J]. Games and Economic Behavior, 1999, 29(1): 79-103Li Jin, born in 1975. PhD and associate professor. Member of China Computer Federation. His current research interests include massive data analysis and machine learning.

Yue Kun, born in 1979. PhD and professor. Member of China Computer Federation. His current research interests include massive data analysis and uncertainty in artificial intelligence.

Zhang Dehai, born in 1977. PhD and associate professor. His current research interests include knowledge engineering, machine learning.

Liu Weiyi, born in 1950. Professor and PhD supervisor in the Yunnan University. His current research interests include intelligent data analysis, social computing, and knowledge engineering.

附錄A. 正文中定理1的證明.

定理A1. 即正文中的定理1.給定近似因子0<ε<1.設(shè)m是{D}m中負種子集的個數(shù).在算法2 中，時刻t，MAX采取隨機傳播策略P(t)，MIN基于1β(近似算法求解抑制種子集(t)對P(t)響應(yīng).那么，經(jīng)過4lnm次迭代后可獲得求解RIBminmax問題的近似解，使得:

其中，β=1-1e.

證明. 算法2可以看作是MAX，MIN雙方T輪重復(fù)博弈的過程.因此，由文獻[20]結(jié)論可知，對于MAX，如果其采取算法2與MIN進行重復(fù)博弈，其T輪博弈的累積期望傳播效用:

(A1)

其中，0<μ<1，P是{D}上的任意概率分布，也就是MAX的任意隨機策略.

(A2)

(A3)

(A4)

其中，C(t)是時刻t，MIN對P(t)的最優(yōu)響應(yīng).此外，任意時刻t，有：

(A5)

(A6)

結(jié)合不等式(A3)的結(jié)果，有：

(A7)

令μ=ε2，T=4lnmε2，于是整理后，有：

(A8)

證畢.

中圖法分類號TP391

通信作者：岳昆(kyue@ynu.edu.cn)

基金項目：國家自然科學(xué)基金項目(61562091,61472345,61263043)；云南省自然科學(xué)基金項目(2014FA023,201501CF00022)；云南大學(xué)骨干教師培養(yǎng)計劃基金項目(XT412003)；云南大學(xué)創(chuàng)新團隊建設(shè)項目(XT412011)

收稿日期：2014-12-09；修回日期：2015-06-23

This work was supported by the National Natural Science Foundation of China (61562091,61472345,61263043), the Natural Science Foundation of Yunnan Province of China (2014FA023,201501CF00022), the Program for Backbone Teacher Development of Yunnan University (XT412003), and the Program for Innovative Research Team of Yunnan University (XT412011).