基于反向可達集的影響力最大化算法

鄧心惠，賓 晟，孫更新

（青島大學數據科學與軟件工程學院，山東青島 266071）

0 概述

隨著社交網絡的快速發展，用戶數量和信息傳播規模不斷擴大，影響力最大化問題受到越來越多的關注，廣泛應用于病毒營銷［1-2］、輿情預警、疾病控制等任務中。病毒營銷是一種通過用戶之間的口碑效應，最大限度擴大品牌知名度的方式，在有限的資源下選擇合適的初始傳播用戶以最大化最終傳播效果，成為解決影響力最大化問題的關鍵。RICHARDSON 等［1］將影響力最大化問題歸納為算法問題，即在某一信息傳播模型下，從一個社交網絡中選取k個初始種子節點集合，使最終影響傳播范圍最大化。KEMPE 等［3］基于獨立級聯（Independed Cascade，IC）［4］模型和線性閾值（Linear Threshold，LT）［5］模型，證明了影響力最大化問題是一個NPhard 問題，并提出一種貪心算法（Greedy Algorithm，GA）。該算法通過迭代的選擇邊際效應最大的節點加入種子集保證了在范圍內接近最優解，但時間復雜度太高，不適用于大規模社交網絡。很多研究人員針對貪心算法的低效率問題提出了一些優化算法。LESKOVEC 等［6］提 出CELF（Cost-Effective Lazy Forwards）算法，利用節點間影響傳播函數滿足子模性的特征將貪心算法的運行速度提高了700 倍。GOYAL 等［7］提出CELF++算法，進一步降低了CELF 算法的時間復雜度。這些算法在一定程度上提升了運行速度，但每次選取節點加入種子集時均要計算節點的影響增加量，運行效率依然很低，難以擴展到大規模社交網絡中。

目前，多數研究人員采用啟發式算法提高運行效率。CHEN 等［8］在度中心性的基礎上提出影響力［9］最大化算法。CHEN 等［10］基于節點間最大影響傳播路徑提出PMIA 算法。JUNG 等［11］針對IC 模型提出IRIE 啟發式算法。WANG 等［12-14］提出基于網絡拓撲結構的啟發式影響力最大化算法。謝勝男等［15］提出新的啟發式算法提高運行效率。曹玖新等［16］提出基于k-核的CCA 算法。但是，這些啟發式算法僅重點考慮了網絡的拓撲結構特性而缺少一定的理論依據，導致算法得不到最優解?；谝陨纤惴ù嬖诘膯栴}，BROGS 等［17］提出一種將理論與實際效率相結合的反向影響抽樣（Reverse Influence Sampling，RIS）算法，通過生成一定數量的反向可達（Reverse Reachable，RR）集來選擇節點，進而多次計算節點影響力，使得到的時間復雜度接近線性，并具有一定的理論依據。雖然RIS 算法有很多優點，但在選取反向可達集的數量上不夠準確穩定，導致算法在實際應用中會產生大量的計算開銷。本文提出一種基于反向可達集采樣的影響力最大化算法D-RIS，無須提前預設反向可達集生成數量的理論閾值，根據影響力傳播函數的單調性和子模性，自動調試生成一定數量的反向可達集。

1 基于反向可達集的社交網絡影響力最大化算法

將社會網絡抽象為一個具有節點集V（用戶）和有向邊集E（用戶間的關系）的網絡圖G，其中G=(V，P，E)，|V|=n，P∈(0，1)，|E|=m。假 設G中每條邊e都有傳播概率P(E)∈(0，1)，那么P(u，v)∈P(u，v∈V)代表節點u激活節點v的概率。為了表述方便，表1 給出了本文常用的符號表示。

表1 常用符號設置Table 1 Setting of commonly symbolic

1.1 傳播模型和問題描述

在社交網絡中尋找一組特定的影響力最大的種子節點集時，需要運用一定的傳播模型來模擬信息在網絡上的傳播規律。目前，經典的信息傳播模型有IC 模型和LT 模型。

本文實驗使用IC 模型模擬用戶影響力最大化傳播。在該模型中給出一個具有n個節點和m條邊的有向加權圖G來表示底層網絡。邊e=(v，u)的權值表示節點v沿著邊e傳播到節點u的概率P。IC 模型中節點被分為已激活、新激活和未激活3 種狀態。每個新激活節點有且僅有一次機會以概率P對未激活的鄰居節點嘗試激活。P值越高，激活的可能性越大。當G中不存在有影響力的活躍節點時，傳播過程結束。在IC 模型上影響力傳播模擬是通過從一組種子節點的隨機傳播開始的。設I(S)為種子節點集S中所有節點的最終影響傳播范圍，即種子節點集S傳播模擬激活的節點個數。期望E[I(S)]是選取的I(S)最優值。該模型模擬傳染病模型［18-19］的傳播過程，種子節點集S類似于一組受感染的個體，激活其鄰居節點的傳播模擬過程類似于疾病從一個個體傳播到另一個個體。

圖1 是由4 個節點組成的一個社交網絡初始圖，每條邊上的權值代表出邊節點到入邊節點的傳播概率Pij。設此社交網絡中所有節點的激活概率為0.5，模擬社交網絡的信息傳播過程。S={a}為初始種子節點集，在T1時刻激活節點a，在T2時刻節點a具有0.2 的概率激活節點c以及0.8 的概率激活節點d，由于Pac=0.5>P=0.2，因此在T2時刻，節點d被激活，S={a，d}。在T3時刻節點c和節點b都具有1 的概率被節點d激活。假設節點d激活節點c而不激活節點b，影響傳播過程結束。網絡上沒有新的節點可以被激活，該傳播過程中激活的節點總數為3，即I(S)=3，S={a，d，c}。若 在T3時刻節點b被激活，則I(S)=4，S={a，b，c，d}。由于IC 模型是一種概率模型［20］，因此傳播過程及最終傳播結果都是不一定的。在實驗過程中經常采用蒙特卡洛方法［21］來多次運行取平均值，以確保結果具有較高的準確率。

圖1 基于獨立級聯模型種子節點集的影響力傳播社交網絡初始圖Fig.1 Initial diagram of the influence propagation social network based on the seed node set of IC model

在給定社交網絡G和常數k的前提下，影響力最大化問題要求在G中尋找一組種子節點集S，使其在IC 傳播模型下傳播影響范圍最大，即找到種子節點集S∈V且|S|=k使得E[I(S)]最大。

1.2 RIS 算法

RIS 算法引入反向可達集采樣方法替代蒙特卡洛方法計算節點預期傳播的影響力，主要思想是生成盡可能少的反向可達集樣本，最終在的范圍內獲得一個近似最優解。RIS 算法證明了對于任何ε>0，都可以在O(β(m+n)klogan)的時間下運行，時間復雜度是近似線性時間的，其中β為選取反向可達集中運行的步數。

RIS 算法避免了貪心算法產生高時間復雜度的問題，同時解決了啟發式算法缺少理論保障，得不到最優解的問題。但是，RIS 算法不能有效控制隨機RR 集的數量。BORGS 等［17］提出一種基于閾值的方法生成隨機RR 集，當生成的節點和邊的總數達到預定的理論閾值時停止生成隨機RR 集。盡管該方法具有近似線性的時間復雜度，但是與生成固定理論閾值的反向可達集之間具有很大的相關性，在實際應用中隱藏的常數較大，導致RIS 算法存在以下問題：1）生成的實際RR 集樣本數量大于理論閾值；2）不能保證理論閾值是生成RR 集樣本數量的最小值。因此，RIS 算法選取RR 集的樣本數量并不準確，不能較好地適用于大規模社交網絡。

1.3 基于反向可達集的D-RIS 算法

針對大多數經典影響力最大化算法存在時間復雜度高或得不到最優解的問題，本文基于IC 模型提出D-RIS 算法。D-RIS 算法主要包括以下步驟：

1）生成反向可達集。隨機且有放回地選擇n個節點，通過在隨機圖g上進行傳播模擬生成θ個節點RR 集的集合R。

2）節點選擇。使用最大覆蓋方法尋找k個覆蓋最多RR 集的節點并返回種子節點集S。

對RIS 算法理論進行分析可以得出：若隨機RR集采樣數量過少，則會因選取節點不足導致算法得不到最優解；若隨機RR 集采樣數量過多，則雖然誤差減小，但會造成時間復雜度太高。因此，根據種子節點集的準確率判定最終的影響力傳播范圍和時間效率。D-RIS 算法的研究重點是選取盡可能少的RR集樣本數量，使算法在影響力傳播范圍和運行效率之間取得較好平衡。借鑒文獻［17］中采樣方法定義統一的反向可達集采樣框架，在此基礎上提出新的臨界值判斷方法，能夠動態選取盡可能少的RR 集樣本數量，并使用最大覆蓋方法選取種子節點集。給定網絡G=(V，E，P)，D-RIS 算法通過生成隨機RR 集的集合R來捕捉G中節點的影響傳播過程，設Rz為節點v的RR 集的子集，即節點的隨機RR 集，圖g是在G中以1-P(E)的概率去掉邊e后得到的隨機圖。

定義1（反向可達集）隨機圖g中可以到達v的節點集，對于RR 集中的節點u，g中都有一條從u到v的有向路徑。

采樣過程為：1）隨機選擇一個節點v∈V；2）在網絡G上生成樣本隨機圖g；3）返回g中節點v的反向可達集Rz。將采樣過程中的節點v稱為Rz中的源節點，則Rz中的所有節點都存在一定的概率能夠激活源節點v。因此，某一節點出現在更多的RR 集中就意味著能夠激活更多的節點，同時該節點具有較大的影響力傳播范圍?；谕瑯拥耐茢?，如果具有k個節點的節點集S覆蓋大量的RR 集，則在網絡G中的這k個節點具有很強的傳播能力傳播至最大范圍，即I(S)=nP[SCoversRz]。由于節點集S的影響與S和RR 集相交的概率成正比，因此解決影響力最大化問題就是確定R集的下界?；诜聪蚩蛇_集采樣框架，設置一種動態調試方法確定最小R集數量。

通過實例說明在IC 模型下對圖1 社交網絡G生成反向可達集的過程，設置k=1。圖2 是在G上生成的3個隨機圖g1，g2，g3。對于3個隨機選取的源節點c，b，d生成的3 個隨機RR 集R1={c，a}、R2={d，a}、R3={b，c，a}，因為節點a出現在3 個隨機RR 集中，所以節點a是影響力最大的節點，最終返回結果為S={a}。

圖2 基于社交網絡G 生成的隨機圖Fig.2 Random graphs generated based on social network G

1.3.1 反向可達集數量確定

通過對RIS 算法中隨機RR 集的數量選取分析可知，Rz數量越多（R集越大），選取的種子節點集越準確，但會增加時間成本。因此，本文提出一種在不影響最終影響力傳播范圍的同時使得生成的R集數量盡可能少的方法。隨著隨機RR 集數量的增多，影響力傳播范圍的上升并不是線性的，而是效用遞減的。因此，RR集的數量與影響力傳播范圍函數的關系同時滿足單調性和子模性（邊際效用遞減），具體定義如下：

1）單調性。設影響力傳播范圍函數f，對于任意反向可達集的數量q1

2）子模性。對于圖的節點總數t，設影響力傳播范圍函數f，反向可達集數量q10，若q1

基于以上理論，對于給定的G，算法設置一個隨機RR 集數量的臨界值θ，其中θ=n×α，α為隨機RR 集選取比例。當隨機RR 集的數量小于θ時，會導致選取隨機RR集的數量不足而不能取得最大影響力傳播范圍。當隨機RR 集的數量大于θ時，邊際效益遞減，影響力傳播范圍的上升幅度過于緩慢或不再上升，會導致時間成本增加。因此，基于網絡中節點當前的傳播情況，算法每輪自動加倍生成反向可達集，直至滿足算法1 中設置的臨界值判斷條件3 次，認為算法生成的RR 集數量無限逼近臨界值。設本輪次影響力傳播范圍為fc，上輪次影響力傳播范圍為fp。算法1 給出了D-RIS 算法反向可達集生成過程的偽代碼，主要過程如下：

1）設置初始的反向可達集生成比例為一個極小的值α，例如算法1 將α值取0.001，此時θ=0.001n，從種子節點集S中隨機選取節點生成比例為α的隨機RR 集并計算影響力傳播范圍fc（算法1 中的第4～6 行）。

2）每輪將α的值加倍并計算本輪影響力傳播范圍增加量Ic，即Ic=fc-fp，下面對本輪影響力傳播范圍增加量進行判斷（算法1 中的第7 行），若滿足條件，則認定本輪α加倍對影響力增長不起作用，影響力可能已經接近臨界值。判斷條件為：若IC≤0 或Ic＜math.loga（Ip，2），則本輪影響力范圍增加量小于等于0 或小于上輪影響力范圍增加量開根號的結果。

3）迭代上述步驟，直到連續3 次的α加倍無效，或α的值大于等于1 時停止繼續生成反向可達集，此時算法生成的隨機RR 集數量逼近臨界值。設最終的反向可達集生成比例為α1，此時得到了相對穩定且有效的反向可達集的臨界值θ，即θ=n×α1。

算法1反向可達集生成算法

在動態調試確定α值的過程中，α值是跳躍式逐漸上升，直至接近臨界值。除了第一輪以外，每輪迭代并不是生成α個反向可達集，而是生成個反向可達集，存儲上一輪個反向可達集，從而組合成本輪的α個反向可達集，即在原有反向可達集的基礎上生成同樣數量的反向可達集，達到加倍的作用。因此，本文算法極大地提升了算法的時間效率。

基于影響力傳播函數滿足單調性和子模性的特點，根據網絡中節點實時傳播情況，提出一種確定隨機RR 集臨界值θ的方法，并遵循反向可達集采樣框架，生成θ個反向可達集。

1.3.2 種子節點選擇

D-RIS算法使用最大覆蓋方法進行種子節點選擇。給定G、k和反向可達集的數量θ。將算法1 中生成的θ個隨機RR 集插入到集合R中。若S∩Rj≠?，則種子集S覆蓋一個隨機RR 集Rj，即CoverR(S)=，將I(S)的近似值定義為I(S)=。算法2給出了D-RIS算法的節點選擇過程的偽代碼，k次迭代過程如下：

1）每次算法在R集中選擇一個覆蓋最多RR 集數量的節點v。

2）刪除R集中節點v所在的所有反向可達集，被刪除的反向可達集中的節點都有一條通過節點v能到達的路徑。

3）將節點v加入到S集中，更新R集進行下一次迭代。

4）選出節點集S=k，迭代結束。

由于在使用最大覆蓋方法選擇k個節點集的過程中，利用貪心算法反復選擇覆蓋最大邊際收益的節點加入種子節點集S中，因此可以返回的近似解，并且能得到近似線性的時間復雜度。

算法2節點選擇算法

由上文分析可知，D-RIS 算法主要包括兩個階段。在第一階段中，隨機選取n個節點生成θ個反向可達集，其中θ=n×α(α<1)，時間復雜度為O(θ)。對于任意隨機選取的節點vj，如果基于一定傳播模型進行傳播模擬生成的反向可達集的時間復雜度為O(EEPV)，其中EEPV是隨機RR 集的寬度（即隨機圖g中指向節點vj的有向邊數），則D-RIS 算法的第一階段的時間復雜度為O（θ×EEPV）。在第二階段中，使用最大覆蓋方法選擇k個節點運用了貪心算法，可以得到線性的時間復雜度為O（θ×EEPV）。貪心算法的時間復雜度O(kmnr)，其中，r代表使用蒙特卡洛采樣次數，n和m分別代表網絡G中全部的節點個數和邊數，在通常情況下n、m、r的數值都很大。D-RIS 算法相比貪心算法時間復雜度更低，相比同樣能達到線性時間復雜度的RIS 算法，在反向可達集數量的選取上更加準確合理。根據上述時間復雜度的分析結果可以得出，D-RIS 算法更適用于大規模社交網絡。

2 實驗與結果分析

2.1 實驗數據集

為更好地驗證D-RIS 算法的合理性和時效性，采用兩個真實數據集進行實驗，如表2 所示。Slashdot 數據集是分享科技資訊網站的朋友數據集，此網站允許用戶將彼此標記為朋友或敵人，其中76.7%是朋友關系。為方便不同算法之間的比較，對Slashdot數據集進行處理，在朋友關系中隨機選取10 000 個節點，預處理后的這些節點間存在36 338 條邊，代表10 000 個用戶之間存在的社交關系。Epinions 數據集是一種基于信任的在線社交網絡數據集。若節點v到節點u存在一條有向邊，則節點v信任節點u，即節點u可以影響節點v，對Epinions 數據集進行了相同的預處理后，保留了信任關系中的10 000 個節點和67 059 條邊。Slashdot和Epinions 數據集［22］均可在斯坦福大學大型網絡數據集網站上下載得到。

表2 數據集信息Table 2 Datasets information

2.2 結果分析

實驗中使用的信息傳播模型為IC 模型，傳播概率為0.08，運行10 000 次蒙特卡洛［18］模擬信息傳播過程，并取平均值作為最終的影響力傳播范圍。為驗證D-RIS 算法的合理性和時效性，選取的對比算法為當前具有代表性的5 種算法，具體如下：

1）CELF 算法。該算法是貪心算法的改進算法，核心思想與貪婪算法基本一致且效率提升明顯。

2）HighDegree 算法。該算法是基于節點中心性的經典啟發式算法，選擇k個度最大的節點作為種子節點集。

3）LIR［13］算法。該算法是基于拓撲結構的啟發式算法，選取并排序局部度最大的節點進而選取種子節點集。

4）pBmH［14］算法。該算法是基于拓撲結構的啟發式算法，考慮了節點受多重鄰居節點的影響，避免了富人俱樂部現象。

5）RIS［17］算法。該算法是反向影響抽樣算法，通過生成一定理論閾值數量的反向可達集進而選取種子節點集。

設置以下3 種仿真實驗：

1）D-RIS 算法傳播規律合理性驗證。使用Slashdot 數據集對RIS 算法中影響力傳播函數滿足單調性和子模性進行分析與驗證。

2）D-RIS 算法與RIS 算法的性能比較。在Slashdot 和Epinions 數據集上，設置不同的反向可達集生成比例的RIS 算法的反向可達集數量，與D-RIS算法分別進行影響力傳播范圍和運行時間比較。

3）D-RIS算法與經典算法的性能比較。對D-RIS算法與CELF 算法、HighDegree 算法、LIR 算法和pBmH算法在兩個真實數據集上進行影響力傳播范圍和運行時間比較，以驗證D-RIS 算法的時效性更優。

2.2.1 D-RIS 算法傳播規律合理性驗證

設置k=5，RIS 算法從α=0.001 開始迭代，每輪加倍反向可達集生成比例直到連續3 次加倍無效或α≥1 時停止。

由圖3 可知，隨著反向可達集生成比例的增加，曲線呈上升趨勢，即影響力傳播范圍不斷增大，表明算法影響力傳播范圍函數具有單調性。RIS 算法的反向可達集生成比例大于0.01 后，隨著反向可達集生成比例的上升，影響力傳播范圍曲線趨于平緩，這是由于影響力傳播范圍函數滿足子模性導致邊際效益遞減，從而呈現影響力傳播范圍曲線擴大趨勢逐漸減緩。當反向可達集生成比例為0.03 時，曲線有稍微下降的趨勢，符合實際情況。理論上，算法的影響力傳播范圍具有單調性，但由于采用的傳播模型為概率模型，因此在實驗中具有一定的波動性。

圖3 RIS 算法和D-RIS 算法在Slashdot 數據集中反向可達集生成比例與影響力傳播范圍的關系Fig.3 Relation between reverse reachable set generation ratio and influence propagation range of the RIS algorithm and the D-RIS algorithm on the Slashdot dataset

由圖3 中RIS 算法的曲線趨勢可以看出，影響力傳播函數由于滿足單調性和子模性，因此出現遞增后逐漸減緩的情況。同時，對D-RIS 算法進行驗證，結果表明隨著反向可達集數量的增加曲線上升趨勢先增大后趨于平緩。RIS 算法需要提前預設反向可達集生成比例，若選取不合理則導致算法達不到最優影響傳播范圍或增加時間成本。D-RIS 算法只需給定一個較小的反向可達集生成比例，就可自動加倍調試反向可達集生成比例直到滿足條件時停止。因此，該實驗證明了D-RIS 算法傳播規律的合理性和實用性。

2.2.2 D-RIS 算法與RIS 算法的性能比較

將RIS 算法反向可達集生成比例分別設置為0.001、0.2、0.5，在兩個數據集上與D-RIS 算法進行影響力傳播范圍和運行時間的比較。

1）設置RIS 算法反向可達集生成比例為0.001。由圖4、圖5 可知，當RIS 算法的反向可達集生成比例為0.001 時，相較D-RIS 算法，RIS 算法運行速度更快，但影響力傳播范圍過小。特別地，當種子節點數量k較低時，兩者的影響力傳播范圍存在成倍的差距。這是由于RIS 算法中的反向可達集生成比例過小導致選取種子節點數量不夠精準，影響算法的最終傳播范圍。

圖4 RIS 算法和D-RIS 算法在Slashdot 數據集上的實驗結果比較（反向可達集生成比例為0.001）Fig.4 Comparison of the experimental results of the RIS algorithm and the D-RIS algorithm on the Slashdot dataset（reverse reachable set generation ratio is 0.001）

圖5 RIS 算法和D-RIS 算法在Epinions 數據集上的實驗結果比較（反向可達集生成比例為0.001）Fig.5 Comparison of the experimental results of the RIS algorithm and the D-RIS algorithm on the Epinions dataset（reverse reachable set generation ratio is 0.001）

2）設置RIS 算法反向可達集生成比例為0.2。如圖6、圖7 可知，當RIS 算法的反向可達集生成比例為0.2 時，在Slashdot 數據集中，兩種算法的影響力傳播范圍接近，但D-RIS 算法的運行效率高于RIS 算法。在Epinions 數據集中，D-RIS 算法在獲得較大影響力傳播范圍的情況下，大幅降低了運行時間，且選取的種子節點集個數越多，在運行效率方面優勢越明顯。

圖6 RIS 算法和D-RIS 算法在Slashdot 數據集上的實驗結果比較（反向可達集生成比例為0.2）Fig.6 Comparison of the experimental results of the RIS algorithm and the D-RIS algorithm on the Slashdot dataset（reverse reachable set generation ratio is 0.2）

圖7 RIS 算法和D-RIS 算法在Epinions 數據集上的實驗結果比較（反向可達集生成比例為0.2）Fig.7 Comparison of the experimental results of the RIS algorithm and the D-RIS algorithm on the Epinions dataset（reverse reachable set generation ratio is 0.2）

3）設置RIS 算法反向可達集生成比例為0.5。由圖8、圖9 可知，當RIS 算法的反向可達集生成比例設置為0.5 時，在兩個數據集上，D-RIS 算法有較大的影響力傳播范圍，且運行效率遠高于RIS算法。由此可以看出，過大的反向可達集生成比例會增加算法最終的時間成本。對于Slashdot 數據集，RIS 算法的運行時間是D-RIS 算法的2 倍多。對于Epinions 數據集，RIS 算法的運行時間是D-RIS 算法的7 倍多，因此D-RIS 算法具有更高的運行效率。

圖8 RIS 算法和D-RIS 算法在Slashdot 數據集上的實驗結果比較（反向可達集生成比例為0.5）Fig.8 Comparison of the experimental results of the RIS algorithm and the D-RIS algorithm on the Slashdot dataset（reverse reachable set generation ratio is 0.5）

圖9 RIS 算法和D-RIS 算法在Epinions 數據集上的實驗結果比較（反向可達集生成比例為0.5）Fig.9 Comparison of the experimental results of the RIS algorithm and the D-RIS algorithm on the Epinions dataset（reverse reachable set generation ratio is 0.5）

在兩個真實數據集上的實驗結果表明：1）當RIS算法的反向可達集生成比例的理論閾值設置太小時影響力傳播范圍較小，當理論閾值設置太大時運行效率太差，D-RIS 算法在達到較優的影響力傳播范圍的同時運行效率更高；2）與RIS 算法相比，D-RIS 算法避免了反向可達集生成比例的理論閾值設置不準確，導致達不到最優影響力傳播范圍或增加時間成本的問題。對于目前復雜的社交網絡，D-RIS 算法無需重復計算，可自動調試生成一定比例的反向可達集，因此更適用于后續拓撲結構變化的社交網絡。

2.2.3 D-RIS 算法與經典算法的性能比較

在兩個不同數據集上，將D-RIS算法與CELF、LIR、pBmH 和HighDegree 算法進行影響力傳播范圍和運行時間的比較，如圖10、圖11 所示。

圖10 5 種算法分別在Slashdot 數據集上的影響力傳播范圍與運行時間比較Fig.10 Comparison of the influence propagation range and running time of five algorithms on the Slashdot dataset

圖11 5 種算法在Epinions 數據集上的影響力傳播范圍與運行時間比較Fig.11 Comparison of the influence propagation range and running time of five algorithms on the Epinions dataset

由于5 種算法的運行時間相差較大，因此運行時間設置為T=2y，其中y表示縱坐標數值。根據圖10、圖11實驗結果分析可知：

2）相比LIR、pBmH 和HighDegree 啟發式算法，D-RIS 算法雖在運行速度方面表現較差，但影響力傳播范圍明顯更優。在Epinions 數據集中，啟發式算法的影響力傳播范圍僅有D-RIS 算法的50%左右。在Slashdot 數據集中，D-RIS 算法的影響力傳播范圍優勢更為明顯?？梢?，啟發式算法雖有極高的運行效率，但未考慮到復雜網絡后續結構變化導致選取的種子節點不夠準確，影響力傳播范圍較小且得不到最優解，同時在不同數據集中啟發式算法的穩定性不佳。

通過以上算法的對比實驗分析可知：D-RIS 算法在影響力傳播范圍和運行時間兩方面取得了較好的平衡，且表現出較好的通用性和穩定性，更適用于拓撲結構變化和規模較大的社交網絡。

3 結束語

本文基于獨立級聯模型，結合反向可達集采樣提出一種改進的影響力最大化算法D-RIS，根據影響力傳播函數的單調性和子模性，設置隨機生成反向可達集數量臨界值的判斷條件，自動調試生成一定數量的反向可達集。實驗結果表明，D-RIS 算法可在獲得較大影響力傳播范圍的同時避免增加時間成本，并且能較好地應用于拓撲結構變化和規模較大的社交網絡。下一步可將D-RIS 算法擴展到多關系社交網絡的影響力傳播模型中，解決社交網絡中多條信息同時傳播情況下的影響力最大化問題。