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

李　勁　岳　昆　張德海　劉惟一

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

2(云南省軟件工程重點(diǎn)實(shí)驗(yàn)室　昆明　650091)

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

(lijin@ynu.edu.cn)

?

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

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

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

2(云南省軟件工程重點(diǎn)實(shí)驗(yàn)室昆明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

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

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

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

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

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

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

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

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

本文的研究?jī)?nèi)容主要包括：

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

2) 針對(duì)策略性影響源的影響傳播抑制問題，基于極小極大決策準(zhǔn)則，以最小化最壞情況下的影響力傳播范圍為目標(biāo)，提出用于影響力傳播抑制的多項(xiàng)式時(shí)間近似算法.

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

1背景知識(shí)

(1)

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

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

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

(2)

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

(3)

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

(4)

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

2問題定義

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

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

(5)

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

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

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

(6)

(7)

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

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

3.1影響力傳播效用的近似估計(jì)

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

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

(8)

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

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

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

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

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

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

于是，可重寫:

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

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

步驟2. 抑制種子挖掘階段.本階段從網(wǎng)中挖掘k個(gè)抑制種子.算法的執(zhí)行過程與采用貪心法挖掘抑制種子集是一致的，即每次迭代，從VC中選取最大邊際抑制效用值的結(jié)點(diǎn)作為抑制種子加入到C中.每次迭代完成后，更新各個(gè)結(jié)點(diǎn)的邊際抑制效用值.經(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問題的隨機(jī)抑制策略求解算法

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

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

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

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

算法2. 隨機(jī)抑制策略的求解算法Aminmax.

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

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

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

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

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

⑦t=t+1;

⑧ end for

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

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

(9)

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

(10)

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

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

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

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

其中，β=1-1e.

定理1的證明見附錄A.

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

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

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

Table 1　Statistics Information of the Experimental Data

所有實(shí)驗(yàn)程序采用C++語言編寫，編譯器版本gcc 4.8.2.實(shí)驗(yàn)運(yùn)行環(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抑制效果的度量標(biāo)準(zhǔn)

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

4.2.2Aprior算法的抑制效果

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

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

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

圖2和圖3分別給出了4種算法在NetHEPT-600和NetPHY-600數(shù)據(jù)集上的期望抑制效果對(duì)比結(jié)果.圖4給出了Greedy算法和Aprior算法分別在HEPT和PHY數(shù)據(jù)集上的運(yùn)行時(shí)間對(duì)比結(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算法運(yùn)行時(shí)間比較

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

4.2.3Aminmax算法的抑制效果

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

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

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

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

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

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

Fig. 7　Running time comparison of Aoracle and Aminmax on NetPHY-6000.圖7　Aoracle和Aminmax算法在NetPHY-6000運(yùn)行時(shí)間對(duì)比

5結(jié)束語

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

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

參考文獻(xiàn)

[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]. 計(jì)算機(jī)學(xué)報(bào), 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)(楊士強(qiáng), 崔鵬. 社區(qū)媒體信息傳播機(jī)制[J]. 中國(guó)計(jì)算機(jī)學(xué)會(huì)通訊, 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)(田家堂, 王軼彤, 馮小軍. 一種新型的社會(huì)網(wǎng)絡(luò)影響最大化算法 [J]. 計(jì)算機(jī)學(xué)報(bào), 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]. 計(jì)算機(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中負(fù)種子集的個(gè)數(shù).在算法2 中，時(shí)刻t，MAX采取隨機(jī)傳播策略P(t)，MIN基于1β(近似算法求解抑制種子集(t)對(duì)P(t)響應(yīng).那么，經(jīng)過4lnm次迭代后可獲得求解RIBminmax問題的近似解，使得:

其中，β=1-1e.

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

(A1)

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

(A2)

(A3)

(A4)

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

(A5)

(A6)

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

(A7)

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

(A8)

證畢.

中圖法分類號(hào)TP391

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

基金項(xiàng)目：國(guó)家自然科學(xué)基金項(xiàng)目(61562091,61472345,61263043)；云南省自然科學(xué)基金項(xiàng)目(2014FA023,201501CF00022)；云南大學(xué)骨干教師培養(yǎng)計(jì)劃基金項(xiàng)目(XT412003)；云南大學(xué)創(chuàng)新團(tuán)隊(duì)建設(shè)項(xiàng)目(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).