基于反向影響采樣的積極影響力最大化

楊書新，許景峰

（江西理工大學(xué)信息工程學(xué)院，江西贛州 341000）

0 引言

隨著互聯(lián)網(wǎng)的蓬勃發(fā)展和信息技術(shù)的日益普及，大型社交網(wǎng)絡(luò)（如Twitter、Facebook 和微博等）已經(jīng)成為人們在日常生活中交流和互動的重要平臺。通過對社交網(wǎng)絡(luò)進行分析和數(shù)據(jù)挖掘，企業(yè)可以制定出更加有效的社會化營銷體系，從而提升品牌的影響力。2001 年，Domingos 等［1］提出了影響力最大化問題，主要思想是：給定一個建模為圖G的社交網(wǎng)絡(luò)，在其中找到k個用戶作為種子節(jié)點，使信息在特定的傳播模型下，通過這k個初始用戶的傳播后能在社交網(wǎng)絡(luò)中達到最大的影響范圍。隨后，影響力最大化問題逐漸成為社交網(wǎng)絡(luò)分析領(lǐng)域的一個研究熱點，廣泛應(yīng)用在病毒營銷、謠言控制和個性化推薦等方面，有重要的現(xiàn)實意義。

目前，大部分的研究工作主要集中在無符號網(wǎng)絡(luò)上，即默認(rèn)社交網(wǎng)絡(luò)用戶之間傳遞的都是積極的關(guān)系。然而在實際生活中，人與人之間有積極的關(guān)系，亦有敵對的關(guān)系。如果僅僅考慮個體之間的積極友好關(guān)系，忽視了敵對的關(guān)系，會造成信息影響范圍不準(zhǔn)確的問題。例如，某個商家想要推廣一種產(chǎn)品，如果商家找到的初始推廣用戶與很多人是敵對關(guān)系，那么，這些人大概率會對這款產(chǎn)品持負(fù)面意見，最終的宣傳效果就不盡如人意。因此，在一些實際場景中，計算信息的傳播范圍需要同時考慮人們之間的積極和敵對關(guān)系，以防止所需的影響范圍被過度估計，可以通過研究符號網(wǎng)絡(luò)［2］中的積極影響力最大化來解決。

然而，針對符號網(wǎng)絡(luò)的積極影響力最大化研究較少，并且其中大部分工作集中在使用傳統(tǒng)的貪心（Greedy）算法或啟發(fā)式算法在符號網(wǎng)絡(luò)中進行研究。貪心算法計算影響范圍時精度高，但時間開銷巨大；啟發(fā)式算法所需的時間消耗少，但計算結(jié)果精度較低。面對日益龐大的社交網(wǎng)絡(luò)，兩種算法都有各自難以克服的缺點。

為了更好地解決符號網(wǎng)絡(luò)中的積極影響力最大化問題，本文提出了一種符號網(wǎng)絡(luò)中基于反向影響采樣（Reverse Influence Sampling in Signed network，RIS-S）的算法。該算法可以在符號網(wǎng)絡(luò)中進行反向影響采樣，找到的種子節(jié)點準(zhǔn)確度較高，時間復(fù)雜度低，能夠高效地解決符號網(wǎng)絡(luò)中的積極影響力最大化問題，適用于大規(guī)模的社交網(wǎng)絡(luò)。

本文的主要工作如下：

1）將反向影響采樣的方法引入到符號網(wǎng)絡(luò)中，以解決積極影響力最大化的問題，該方法能夠在時間消耗和結(jié)果準(zhǔn)確度上取得較好的平衡，與同類型算法IMM（Influence Maximization via Martingales）相比，運行時間更短，準(zhǔn)確度更高。

2）在生成反向可達集階段，考慮了節(jié)點之間的極性關(guān)系，從而可以獲得更加準(zhǔn)確的積極影響范圍；為了減少反向可達集的重疊，限制了采樣深度，提高了反向可達集的有效性。

1 相關(guān)工作

2001 年，Domingos 等［1］提出使用馬爾可夫隨機場（Markov Random Field）模擬信息的傳播過程，首次提出了影響力最大化問題。Kempe 等［3］將該問題定義為一種離散優(yōu)化問題，并提出了兩種基本的傳播模型：獨立級聯(lián)模型（Independent Cascade Model）和線性閾值模型（Linear Threshold Model）。基于這兩種傳播模型，Kempe 等［3］證明了影響力最大化亦是NP-Hard 問題，并提出了一種近似比為(1 -1/e -ε)的貪心算法，可以獲得影響力最大化問題最優(yōu)解63%的近似解。通過研究目標(biāo)函數(shù)的子模特性，Leskovec等［4］對貪心算法進行了優(yōu)化，提出了CELF（Cost-Effective Lazy-Forward）算法，該算法在時間效率上比傳統(tǒng)的貪心算法快了近700 倍。Goyal 等［5］優(yōu)化了CELF 算法，提出了CELF++算法，進一步提高了時間效率。上述貪心算法時間開銷巨大，難以擴展到現(xiàn)實場景中，有一定的局限性。2009 年，針對傳統(tǒng)度估計算法的影響范圍重疊問題，Chen 等［6］提出了DgreeeDiscount 算法，這是一種啟發(fā)式算法，它的主要思想是：如果節(jié)點u的鄰居節(jié)點中存在種子節(jié)點v，那么將u選為種子節(jié)點時，需要將u的度數(shù)進行一定的折扣，最終再選出度數(shù)最大的前k個節(jié)點作為種子節(jié)點。盡管DgreeDiscount在時間效率上比貪心算法提升明顯，但是該算法求解的精度較低。2014 年，Borgs 等［7］將反向影響采樣的思想引入影響力最大化問題中，提出了反向影響采樣（Reverse Influence Sampling，RIS）算法。他們發(fā)現(xiàn)在尋找k個所需的種子節(jié)點的過程中，沒有必要對整個圖進行計算，并提出了反向可達集（Reverse Reachable Set）的概念。根據(jù)RIS 的思想，如果一個節(jié)點高頻率地出現(xiàn)在采樣圖g所生成的反向可達集中，那么它有較高的可能性是種子節(jié)點的良好候選者。該算法得到的時間復(fù)雜度接近線性，能以不小于1-n-1的概率得到近似比(1 -1/e -ε)。RIS 算法為影響力最大化問題研究提供了一種新穎的思路，此后，學(xué)者們對此類算法進行了更加深入的研究。為了進一步提高算法的效率，Tang 等［8］提出了兩階段影響力最大化（Two-phase Influence Maximization，TIM）算法。相較于RIS 算法，TIM 算法減少了采樣的數(shù)量，降低了時間復(fù)雜度，并且支持觸發(fā)模型。通過對參數(shù)估計的改進，Tang 等［8］還提出了TIM+算法。TIM+與TIM 具有相同的最壞情況復(fù)雜度，但能表現(xiàn)出更加優(yōu)秀的經(jīng)驗性能。盡管如此，TIM 和TIM+在計算成本方面仍然有很大的改進空間。2015年，Tang 等［9］基于鞅（Martingale）的估計技術(shù)提出了IMM 算法，該算法利用折半猜測的方法估計影響力擴展度的下界，實驗結(jié)果表明，IMM 比TIM/TIM+性能更好。

大量的影響力最大化研究聚集在無符號網(wǎng)絡(luò)上，也為解決符號網(wǎng)絡(luò)下的積極影響力最大化問題指明了道路。Li等［10］首次研究了符號網(wǎng)絡(luò)中的影響力最大化問題，他們利用“敵人的朋友就是我的敵人，敵人的敵人就是我的朋友”的社會原則，將IC（Independent Cascade）模型擴展到了符號網(wǎng)絡(luò)中，提出了極性相關(guān)的獨立級聯(lián)（Polarity-related Independent Cascade，IC-P）模型。在此模型下，他們使用了貪心算法解決積極影響力最大化問題，在每次迭代中選擇一個節(jié)點，以提供總影響的最大邊際收益。IC-P 貪心算法與無符號網(wǎng)絡(luò)中的貪心算法一樣有著計算開銷過于龐大的缺點。之后，Li 等［11］又在IC-P 模型中使用了模擬退火算法解決積極影響力最大化問題，該方法在精度（積極影響范圍）方面與IC-P 貪心表現(xiàn)相似，但在效率方面更優(yōu)。Wang 等［12］在符號網(wǎng)絡(luò)中推廣了LT（Linear Threshold）模型，提出了解決積極影響力最大化的LT-A 模型，然而，在進行求解時，使用的是貪心算法，效率偏低，不適用于大型社交網(wǎng)絡(luò)。Hosseini-Pozveh等［13］提出了一種符號感知級聯(lián)模型，并證明了在該模型中積極影響力最大化是NP-Hard 問題，最后使用了一種基于粒子群優(yōu)化的啟發(fā)式算法求解積極影響力最大化。Ju 等［14］使用獨立路徑計算符號網(wǎng)絡(luò)中節(jié)點間的正激活概率，為了避免在估計傳播范圍時進行蒙特卡洛模擬，提出了一種傳播函數(shù)以估計種子集的正影響傳播。Qiu 等［15］針對符號網(wǎng)絡(luò)提出了一種改進的級聯(lián)模型ICWNP（Independent Cascade With the Negative and Polarity），并在該模型下使用了貪心算法解決極性關(guān)系的影響力最大化問題，該方法準(zhǔn)確度較高但運行時間較長。

2 問題定義和形式化描述

給定一個符號網(wǎng)絡(luò)Gs=(V，E，P，S)，其中V是節(jié)點的集合，V={v1，v2，…，vn}，每一個節(jié)點v∈V代表社交網(wǎng)絡(luò)中的一個用戶；E={e1，e2，…，en}是有向邊的集合，(u，v) ∈E表示節(jié)點u對節(jié)點v的影響關(guān)系；P(u，v) ∈[0，1]表示節(jié)點u對節(jié)點v的影響概率；S（u，v）表示節(jié)點u和v的極性關(guān)系（S(u，v) ∈{+1，-1}），S（u，v）為+1 表示節(jié)點u對節(jié)點v產(chǎn)生的是積極（友好）的關(guān)系，如果為-1 則是消極（敵對）的關(guān)系。P(u，v) ≠P(v，u)且S(u，v) ≠S(v，u)，即兩節(jié)點之間的影響概率和極性關(guān)系都是雙向的，相互獨立。圖1 展示了符號網(wǎng)絡(luò)的一個具體例子，每條有向邊都有屬性S(u，v) ·P(u，v)。

圖1 符號網(wǎng)絡(luò)Fig.1 Signed network

為了更加清楚地表述，表1 列出了本文常用的符號表示。

表1 常用符號表示Tab.1 Representation of frequently used symbols

2.1 IC-P模型傳播規(guī)則

文獻［10］針對符號網(wǎng)絡(luò)擴展了IC 模型，提出了IC-P 模型，以解決符號網(wǎng)絡(luò)中的影響力最大化問題。在該模型中，如果某個節(jié)點已經(jīng)處于激活狀態(tài)，那么它將有機會在下一輪信息傳播中激活它的出度鄰居節(jié)點（如果節(jié)點a有路徑可以到達節(jié)點b且二者為鄰居節(jié)點，則節(jié)點b為節(jié)點a的出度鄰居節(jié)點，節(jié)點a為節(jié)點b的入度鄰居節(jié)點）。被激活節(jié)點v的狀態(tài)C（v）取決于激活它的節(jié)點u的狀態(tài)C（u）和兩節(jié)點之間的極性關(guān)系S（u，v），遵循如下規(guī)則：

其中：C(v)=+1 表明節(jié)點v處于積極狀態(tài)，即節(jié)點v對傳播的信息持正面意見；C(v)=-1 表明節(jié)點v處于消極狀態(tài)，對傳播的信息持負(fù)面意見。在積極影響力最大化問題中，種子節(jié)點的初始狀態(tài)都為積極狀態(tài)。以病毒式營銷為例，商家想要推廣某種產(chǎn)品，那么他找到的初始推廣人應(yīng)當(dāng)是對產(chǎn)品持正面意見且影響力大的人物，只有這樣營銷才有實際意義。在圖2 所示IC-P 模型信息傳播的具體例子中，節(jié)點n1是種子節(jié)點，節(jié)點n1的初始狀態(tài)C(n1)=+1。在第一輪信息傳播中，節(jié)點n1激活了n2、n3、n4三個節(jié)點，但是依據(jù)式（1）中的規(guī)則，只有n3、n4節(jié)點處于積極狀態(tài)。被激活的節(jié)點有且只有一次機會激活它們的鄰居節(jié)點。在第二輪傳播中，節(jié)點n2成功激活了節(jié)點n6，節(jié)點n3則激活了節(jié)點n5，節(jié)點n4嘗試激活節(jié)點n7但并未成功；在第三輪傳播中，節(jié)點n6激活了節(jié)點n7，此時網(wǎng)絡(luò)中已經(jīng)沒有節(jié)點可以被激活了，整個傳播過程結(jié)束。

圖2 IC-P模型傳播示例Fig.2 Propagation examples of IC-P model

2.2 反向影響采樣相關(guān)概念

定義1采樣圖。在圖G=(V，E，P)中，對于圖G中的每一條邊e∈E，以1 -Pe的概率刪除，最終得到的子圖g是采樣圖。

定義2反向可達集。設(shè)v是圖G中一個給定的節(jié)點，采樣圖g中可以到達節(jié)點v的節(jié)點集合為v在g中的反向可達集。

2.3 符號網(wǎng)絡(luò)中的積極影響力最大化

給定一個數(shù)k∈N，代表種子節(jié)點的個數(shù)。在符號網(wǎng)絡(luò)Gs=(V，E，P，S)中，節(jié)點有三種狀態(tài)：積極狀態(tài)、消極狀態(tài)和未激活狀態(tài)。積極狀態(tài)下的節(jié)點表示其對傳播的事物持正面意見，消極狀態(tài)下的節(jié)點對傳播的事物持負(fù)面意見。積極影響力最大化的目標(biāo)是找到k個種子節(jié)點，使它們在特定傳播模型下能夠影響到的積極狀態(tài)節(jié)點數(shù)達到最大，可以被形式化為式（2）：

其中：seed表示的是種子節(jié)點集合；k是種子集合的大小，在病毒營銷中可以理解為商家用于廣告投放的成本；σ+(seed)表示的是被種子節(jié)點激活的最終具有積極狀態(tài)的節(jié)點個數(shù)期望。

3 基于反向影響采樣的積極影響力最大化

貪心算法在求解符號網(wǎng)絡(luò)中的積極影響力最大化問題時雖然能保證精度，但隨著社交網(wǎng)絡(luò)規(guī)模愈加龐大，此類算法求解的時間成本呈指數(shù)型增長，難以滿足現(xiàn)實需求；啟發(fā)式算法利用直觀上的經(jīng)驗，能在有限的搜索空間內(nèi)較為迅速地得到結(jié)果，然而其求解精度卻難以得到理論保證?；诜聪蛴绊懖蓸铀枷氲乃惴ㄔ诮鉀Q影響力最大化問題時避免了上述問題，在影響力精度和運行效率上取得了較好的平衡，為了更好地解決符號網(wǎng)絡(luò)中的積極影響力最大化問題，本文提出了基于反向影響采樣思想的算法RIS-S，該算法在符號網(wǎng)絡(luò)中進行反向影響采樣，算法主要分為兩階段：1）在符號網(wǎng)絡(luò)Gs的采樣圖g中生成一定數(shù)量的反向可達集。2）在生成的反向可達集中用貪心方法找到k個節(jié)點，使它們覆蓋的反向可達集盡可能地多，這k個節(jié)點即是積極影響力最大化問題中所需的k個種子節(jié)點。

詳細(xì)介紹如下：

1）生成一定數(shù)量的反向可達集。生成反向可達集的前提是需要構(gòu)建符號網(wǎng)絡(luò)G=(V，E，P，S)的采樣圖。依據(jù)定義1，采樣圖的生成只與圖中每條邊的傳播概率Pe有關(guān)，所以在符號網(wǎng)絡(luò)中獲取采樣圖的方法與在無符號網(wǎng)絡(luò)中一致。生成采樣圖g時，兩節(jié)點間的傳播概率越大，它們之間的連接關(guān)系在圖g中更容易出現(xiàn)，這與信息在獨立級聯(lián)模型中的傳播機制類似。在IC-P 模型中，種子節(jié)點的初始狀態(tài)都為積極狀態(tài)，依據(jù)式（1），如果節(jié)點v被節(jié)點u激活且節(jié)點u處于積極狀態(tài)，那么當(dāng)且僅當(dāng)兩節(jié)點間的極性關(guān)系S（u，v）等于+1時，被激活的節(jié)點v才能處于積極狀態(tài)，所以在生成反向可達集時，可以先利用邊上的極性關(guān)系信息剔除不可靠的候選種子用戶。具體的做法是，在生成采樣圖中某一節(jié)點u的反向可達集時，只將可以到達節(jié)點u且路徑中極性關(guān)系都為+1的節(jié)點納入到節(jié)點u的反向可達集中，不僅可以將節(jié)點間的極性關(guān)系融入反向可達集中，還能避免狀態(tài)為-1 的節(jié)點對最終積極影響范圍造成干擾。

在以往的研究中，以IMM 及其優(yōu)化算法（Stop-and-Stare Algorithm，SSA）［16］為代表的基于反向影響采樣思想的算法都專注于研究反向可達集的數(shù)量，從而保證算法的精度，但卻忽略了反向可達集之間的冗余現(xiàn)象。圖3（a）是一個有8個節(jié)點和7 條連接邊的社交網(wǎng)絡(luò)圖G，邊上的數(shù)字代表節(jié)點間的傳播概率，對每一條邊以1 -Pe的概率進行移除操作后，可以獲得采樣圖，再對采樣圖進行遍歷可以獲得不同節(jié)點的反向可達集。采樣圖的生成過程具有隨機性，所以圖G可以生成多個不同的采樣圖（如采樣圖g1 和g2），由此獲得的反向可達集也不盡相同。在采樣圖g1 中，節(jié)點8 的反向可達集是｛1，3，6，8｝，而在采樣圖g2 中，節(jié)點8 的反向可達集為｛3，6，8｝。每條邊的傳播概率P（u，v）相互獨立，傳播路徑1→3→6→8 和3→6→8 出現(xiàn)在采樣圖中的概率可由式（3）計算：

圖3 采樣圖及反向可達集示例Fig.3 Examples of sampling graph and reverse reachable set

其中：（u，v）表示路徑path中的一條邊；P（u，v）表示節(jié)點u對節(jié)點v的影響概率。由此可知，傳播路徑1→3→6→8 出現(xiàn)在采樣圖g1 中的概率為0.125，傳播路徑3→6→8 出現(xiàn)在采樣圖g2 中的概率為0.25，顯然，傳播路徑3→6→8 更容易出現(xiàn)在采樣圖中。因此，當(dāng)反向可達集的數(shù)量有限制時，｛3，6，8｝更可能是節(jié)點8 的反向可達集，而不是｛1，3，6，8｝。

針對上述例子所展現(xiàn)的情況以及基于三度影響力原則［17］，本文提出的RIS-S 算法在生成反向可達集階段控制了最大采樣深度，以減少反向可達集的冗余，進一步提升了最終影響精度，生成反向可達集的方法如算法1 所示。

在算法1 中，首先生成符號網(wǎng)絡(luò)Gs的采樣圖g，然后在Gs中隨機選擇一個要生成其反向可達集的節(jié)點v。new_nodes表示生成反向可達集時新增節(jié)點的集合；RSS0 表示上一輪遍歷生成的反向可達集，其初始值為節(jié)點v；temp用于暫時存儲新增的節(jié)點。第4）～5）行，令初始采樣深度為1，并開始生成節(jié)點v的反向可達集；第6）～9）行，隨機選擇new_nodes中的某個節(jié)點u作為起始節(jié)點，依次搜尋與它極性關(guān)系為+1 的入度鄰居節(jié)點，并加入到反向可達集RRS中，下一輪的new_nodes節(jié)點為本輪加入到RRS中的新增節(jié)點；第10）～13）行，如果某一次迭代中采樣深度depth大于最大影響采樣深度sample_depth，搜尋停止，否則開始新一輪搜尋；第15）行，返回最終的反向可達集RRS。

2）使用最大覆蓋方法選取k個種子節(jié)點。在反向影響抽樣的機制中，節(jié)點的影響力與它覆蓋的反向可達集數(shù)量成正比，如果某個節(jié)點高頻率出現(xiàn)在反向可達集中，那么它將被認(rèn)為是具有高影響力的節(jié)點。選取k個種子節(jié)點的具體方法如下：

算法2 使用最大貪心覆蓋方法在反向可達集中找出k個種子節(jié)點。第1）行，先初始化種子節(jié)點集seed；第2）～4）行，將出現(xiàn)在反向可達集中次數(shù)最多的節(jié)點選為種子節(jié)點，并將其添加到種子節(jié)點集seed中；第5）行，更新反向可達集，剔除包含本輪被選為種子節(jié)點的反向可達集。進行k輪循環(huán)，最后返回種子節(jié)點集seed。

3.1 個體化系統(tǒng)管理模式降低了新生兒出生缺陷率 本研究在孕前及孕早期開展了健康生活方式的教育[5-6]，生殖遺傳咨詢門診，建立了新生兒缺陷的三級預(yù)防體系[7]。結(jié)果顯示，觀察組新生兒出生缺陷(4.95‰)明顯低于對照組(12.53‰)，說明在孕前開展個體化的優(yōu)生優(yōu)育知識健康教育工作的必要性，觀察組建立孕前—圍產(chǎn)期檔案、計劃妊娠管理，從年齡、營養(yǎng)、遺傳和環(huán)境因素進行孕前風(fēng)險評估，做好優(yōu)生優(yōu)育的科普教育，減少遺傳性畸形的出生。孕早期及時補充葉酸及少量維生素，開展實驗室篩查、羊水檢測等物理診斷，充分做好三級預(yù)防體系，將孕期保健時間節(jié)點前移，為孕產(chǎn)婦提供一體化的延伸服務(wù)措施。

RIS-S 算法的時間復(fù)雜度分析過程如下：在算法1 的第1）行中，獲取采樣圖的時間復(fù)雜度為O（|E|）；在第5）～7）行中，搜尋與new_nodes節(jié)點極性關(guān)系為+1 的入度鄰居節(jié)點的時間復(fù)雜度為O(|new_nodes| · |new_nodes| · |E(g)|)，其中|E（g）|表示采樣圖g的邊數(shù)，其余行的代碼時間復(fù)雜度為O（1）。算法2 使用最大貪心覆蓋方法尋找k個種子節(jié)點的時間復(fù)雜度為O（k）。綜上所述，RIS-S 算法的時間復(fù)雜度為O(|E|+|E(g)| · |new_nodes|2+k)。在采樣圖g中，邊數(shù)|E（g）|小于整個符號網(wǎng)絡(luò)Gs中的邊數(shù)|E|，new_nodes中的節(jié)點數(shù)也遠(yuǎn)遠(yuǎn)小于采樣圖g中總節(jié)點數(shù)|V（g）|。貪心算法的時間復(fù)雜為O（k·|E|·|V|），|E|和|V|分別表示符號網(wǎng)絡(luò)Gs的邊數(shù)和節(jié)點個數(shù)。在大型社交網(wǎng)絡(luò)中，|E|和|V|的數(shù)值往往很大，所以RIS-S 算法更適用于大型社交網(wǎng)絡(luò)。

4 實驗與結(jié)果分析

4.1 實驗數(shù)據(jù)集與實驗參數(shù)設(shè)置

為了驗證RIS-S 算法求解符號網(wǎng)絡(luò)中積極影響力最大化問題的有效性，本文選取了三個真實的符號網(wǎng)絡(luò)數(shù)據(jù)集Bitcoinotc、Slashdot 和Epinions 進行了仿真實驗。Bitcoinotc是一個比特幣交易評估網(wǎng)絡(luò)，用戶可以以信任和不信任關(guān)系對其他人進行排名；Slashdot 是一個科技新聞網(wǎng)站，該網(wǎng)站的Slashdot Zoo 功能允許用戶標(biāo)記其他用戶為朋友或敵人；Epinions 數(shù)據(jù)集來源于大眾消費者點評網(wǎng)站Epinions.com，網(wǎng)站的用戶可以通過查看某個用戶的產(chǎn)品評分和評論決定是否信任該用戶。這些數(shù)據(jù)集可以從斯坦福大型網(wǎng)絡(luò)數(shù)據(jù)集網(wǎng)站（http：//snap.stanford.edu/data）中找到。實驗數(shù)據(jù)集相關(guān)參數(shù)如表2 所示。表2 中：|V|和|E|分別表示圖的節(jié)點數(shù)、邊數(shù)；d代表網(wǎng)絡(luò)直徑；E-/E+是負(fù)邊占比率。

表2 實驗數(shù)據(jù)集相關(guān)參數(shù)Tab.2 Relevant parameters of experimental datasets

貪心算法并不適用于較大規(guī)模的社交網(wǎng)絡(luò)，所以在實驗中，本文選取了Random 算法、POD（Positive Out-Degree）算法、Effective Degree 算法和IMM 算法與RIS-S 算法進行對比。Random 算法［18］是解決影響力最大化問題最常用的算法之一，它從圖中隨機地選取k個節(jié)點作為種子節(jié)點。POD 算法［19］是一種啟發(fā)式算法，它選取圖中正出度最大的前k個節(jié)點作為種子節(jié)點。Effective Degree 算法［20］是有效度算法，節(jié)點的正出度數(shù)量減去負(fù)出度數(shù)量為有效度，此算法選擇k個有效度最大的節(jié)點作為種子節(jié)點。IMM 算法［9］是基于反向影響采樣思想的代表性算法之一，它在解決影響力最大化問題中有著較好的結(jié)果準(zhǔn)確性與運行效率。

實驗在操作系統(tǒng)為64 位的Windows 10 中進行，CPU 為AMD Ryzen5 2600@3.40 GHz 六核，內(nèi)存為16 GB，硬盤大小為512 GB，編程環(huán)境為Python 3.6。

所有算法都是在IC-P 模型下進行積極影響力計算的，節(jié)點激活概率P設(shè)置為0.05。在模擬信息傳播階段，實驗進行10 000 次蒙特卡洛模擬，取平均值作為各種子集最終的積極影響力范圍。為了更符合信息在真實社交網(wǎng)絡(luò)中的傳播規(guī)律，最大影響采樣深度sample_depth設(shè)置為各數(shù)據(jù)集的網(wǎng)絡(luò)直徑。RIS-S 算法中，近似比參數(shù)ε=0.5，錯誤概率參數(shù)l=1，與IMM 算法一致。

4.2 實驗結(jié)果與分析

實驗的對比指標(biāo)有：積極影響力范圍、算法的運行時間和正節(jié)點占比率。積極影響力范圍和正節(jié)點占比率可以表明算法的準(zhǔn)確度，而運行時間則可以反映出算法的運行效率。

4.2.1 積極影響力范圍

圖4 是各算法計算出的種子集在Bitcoinotc 數(shù)據(jù)集上的積極影響力范圍。Bitcoinotc 是相對較小的數(shù)據(jù)集，由圖4 可知，雖然RIS-S 算法在種子個數(shù)小于15 時積極影響力范圍不如POD 算法和Effective Degree 算法；但當(dāng)k≥15 時，RIS-S 算法是五種算法中表現(xiàn)最好的。

圖4 Bitcoinotc數(shù)據(jù)集上的積極影響力范圍Fig.4 Positive influence range on Bitcoinotc dataset

圖5 是各種子集在Slashdot 數(shù)據(jù)集上的積極影響力范圍。由圖5 可知，Random 算法積極影響力范圍在數(shù)據(jù)集Slashdot 中遠(yuǎn)遠(yuǎn)小于其他三種算法；RIS-S 算法積極影響力范圍最廣，POD 算法次之；Effective Degree 算法與POD 算法表現(xiàn)較為接近；IMM 算法在積極影響力范圍上表現(xiàn)不如Effective Degree 算法、POD 算法和RIS-S 算法，但大幅領(lǐng)先于Random 算法。Random 算法在尋找種子時隨機性過強，找到的種子質(zhì)量較差，所以在五種算法中表現(xiàn)出了最糟糕的積極影響力范圍。IMM 算法在尋找種子時沒有考慮節(jié)點間的極性關(guān)系，由式（1）可知，在符號網(wǎng)絡(luò)中，高影響力的節(jié)點并不一定擁有較高的積極影響力范圍，因此IMM 算法在解決積極影響力問題上與Effective Degree 算法、POD 算法和RIS-S算法有一定的準(zhǔn)確度差距。在Slashdot 數(shù)據(jù)集中，IMM 算法的積極影響力范圍比POD 算法平均低23.3%，與RIS-S 算法的平均差距有27.3%。Effective Degree 算法在k=5，10，15 時與POD 算法表現(xiàn)幾乎一致，二者總體的積極影響力范圍差異較小。RIS-S 算法從種子數(shù)k=5 到k=50 時積極影響力范圍都優(yōu)于POD 算法，并且在k=30 時逐步拉開兩者之間的積極影響力范圍差距，在k=50 時RIS-S 算法比POD 算法高出5.5%的積極影響力范圍。

圖5 Slashdot數(shù)據(jù)集上的積極影響力范圍Fig.5 Positive influence range on Slashdot dataset

圖6 是各種子集在Epinions 數(shù)據(jù)集上的積極影響力范圍。從圖6 可看出：面對更加龐大的符號網(wǎng)絡(luò)，RIS-S 算法在k=50 時積極影響力范圍比POD 算法高7.2%，比IMM 算法高20.5%，表現(xiàn)出色，而Random 算法的積極影響力范圍最低。Effective Degree 算法依然與POD 算法表現(xiàn)相似。由圖5～6 可得知：在Slashdot 和Epinions 中，正出度最大的前15 個節(jié)點擁有較少的負(fù)邊。POD 算法選擇正出度最大的節(jié)點作為種子節(jié)點，僅能保證在第一輪影響傳播中被激活的節(jié)點處于積極狀態(tài)，無法保證后續(xù)影響傳播激活的節(jié)點處于積極狀態(tài)；RIS-S 算法通過考慮符號的反向影響采樣技術(shù)，生成的反向可達集全部為處于積極狀態(tài)的節(jié)點，所以RIS-S 算法擁有更加優(yōu)異的積極影響力范圍。

圖6 Epinions數(shù)據(jù)集上的積極影響力范圍Fig.6 Positive influence range on Epinions dataset

4.2.2 運行時間

算法的運行時間也是一個重要的性能衡量指標(biāo)。圖7是RIS-S 算法與IMM 算法在Bitcoinotc 數(shù)據(jù)集上的運行時間。整體上，RIS-S 算法的運行時間比IMM 算法的更短，并且隨著種子個數(shù)的增加，RIS-S 算法的運行時間優(yōu)勢愈加明顯。圖8是RIS-S 算法與IMM 算法在Slashdot 數(shù)據(jù)集中的運行時間。從圖8 可看出：RIS-S 算法在擁有更高積極影響力范圍的情況下，算法運行時間比IMM 算法更低，在種子個數(shù)k=50 時，RIS-S 算法的運行時間比IMM 少35%。RIS-S 算法在生成反向可達集階段控制了采樣的深度，一定程度上減少了反向可達集的冗余，由文獻［9］可知，IMM 算法的時間復(fù)雜度為O((k+l)(|E|+|V|)lb(|V|/ε2))，而RIS-S 算法的時間復(fù)雜度為O(|E|+|E(g)| · |new_nodes|2+k)，|E（g）|小于|E|，|new_nodes|也遠(yuǎn)小于|V|，所以RIS-S 算法相較于IMM 算法更快。圖9 是RIS-S 算法與IMM 算法在Epinions 數(shù)據(jù)集中的時間對比。在k=40，45，50 時，RIS-S 算法的運行時間接近IMM 算法，原因在于Epinions 數(shù)據(jù)集比Slashdot 數(shù)據(jù)集網(wǎng)絡(luò)直徑更長，負(fù)邊占比更低，但總體上，RIS-S 算法的運行效率更加優(yōu)異。

圖7 Bitcoinotc數(shù)據(jù)集上的運行時間Fig.7 Running time on Bitcoinotc dataset

圖8 Slashdot數(shù)據(jù)集上的運行時間Fig.8 Running time on Slashdot dataset

圖9 Epinions數(shù)據(jù)集上的運行時間Fig.9 Running time on Epinions dataset

4.2.3 正節(jié)點占比率

正節(jié)點占比率可以進一步評估算法在解決積極影響力最大化問題時的準(zhǔn)確度，其計算方式為：

其中：|V+|為被激活的正節(jié)點數(shù)；I（seed）表示最終被激活的節(jié)點數(shù)；Pr∈［0，1］為正節(jié)點占比率，值越接近1，說明此算法找到的種子更加準(zhǔn)確。

表3 是各算法在種子數(shù)k=50 時的正節(jié)點占比率情況。

表3 k=50正節(jié)點占比率對比Tab.3 Comparison of positive ratio at k=50

從表3 可看出：RIS-S 算法在三個數(shù)據(jù)集中的正節(jié)點占比率都是五種算法中最高的。由于Bitcoinotc 數(shù)據(jù)集中正邊占比率達到了90%，五種算法在Bitcoinotc 數(shù)據(jù)集中都有著較高的正節(jié)點占比率。在Slashdot 數(shù)據(jù)集中，RIS-S 的正節(jié)點占比率比POD 算法高5.5%，比Effective Degree 算法高6.9%，三者的正節(jié)點占比率都超過了70%；與IMM 算法和Random 算法相比，RIS-S 算法優(yōu)勢明顯，正節(jié)點占比率分別高20.3%和48.1%。在Epinions 數(shù)據(jù)集中，RIS-S 算法的正節(jié)點占比率比表現(xiàn)第二好的POD 算法高9.5%，這說明在更大規(guī)模的符號網(wǎng)絡(luò)中，RIS-S 算法在解決積極影響力最大化問題時更具優(yōu)勢。

5 結(jié)語

本文基于IC-P 模型，結(jié)合反向影響采樣思想提出了一種解決符號網(wǎng)絡(luò)積極影響力最大化問題的算法RIS-S。實驗結(jié)果表明RIS-S 算法與基于反向采樣思想的代表算法IMM 相比，具有更短的運行時間，在解決積極影響力最大化問題中有著更高的積極影響范圍，在病毒式營銷場景中有一定的應(yīng)用價值。文獻［21］的研究表明，回聲室效應(yīng)（Echo chamber）和過濾氣泡（filter bubbles）問題會使社交網(wǎng)絡(luò)用戶處于相對封閉的社交環(huán)境，因此，未來的工作將在RIS-S 算法的基礎(chǔ)上融入消極影響力，以解決信息暴露平衡問題。