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

楊書新，許景峰

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

0 引言

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

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

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

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

本文的主要工作如下：

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

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

1 相關工作

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

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

2 問題定義和形式化描述

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

圖1 符號網絡Fig.1 Signed network

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

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

2.1 IC-P模型傳播規則

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

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

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

2.2 反向影響采樣相關概念

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

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

2.3 符號網絡中的積極影響力最大化

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

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

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

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

詳細介紹如下：

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

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

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

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

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

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

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

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

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

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

4 實驗與結果分析

4.1 實驗數據集與實驗參數設置

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

表2 實驗數據集相關參數Tab.2 Relevant parameters of experimental datasets

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

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

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

4.2 實驗結果與分析

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

4.2.1 積極影響力范圍

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

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

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

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

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

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

4.2.2 運行時間

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

圖7 Bitcoinotc數據集上的運行時間Fig.7 Running time on Bitcoinotc dataset

圖8 Slashdot數據集上的運行時間Fig.8 Running time on Slashdot dataset

圖9 Epinions數據集上的運行時間Fig.9 Running time on Epinions dataset

4.2.3 正節點占比率

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

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

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

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

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

5 結語

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