鄧心惠，賓 晟，孫更新

（青島大學(xué)數(shù)據(jù)科學(xué)與軟件工程學(xué)院，山東青島 266071）

0 概述

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

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

1 基于反向可達(dá)集的社交網(wǎng)絡(luò)影響力最大化算法

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

表1 常用符號(hào)設(shè)置Table 1 Setting of commonly symbolic

1.1 傳播模型和問題描述

在社交網(wǎng)絡(luò)中尋找一組特定的影響力最大的種子節(jié)點(diǎn)集時(shí)，需要運(yùn)用一定的傳播模型來模擬信息在網(wǎng)絡(luò)上的傳播規(guī)律。目前，經(jīng)典的信息傳播模型有IC 模型和LT 模型。

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

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

圖1 基于獨(dú)立級(jí)聯(lián)模型種子節(jié)點(diǎn)集的影響力傳播社交網(wǎng)絡(luò)初始圖Fig.1 Initial diagram of the influence propagation social network based on the seed node set of IC model

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

1.2 RIS 算法

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

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

1.3 基于反向可達(dá)集的D-RIS 算法

針對(duì)大多數(shù)經(jīng)典影響力最大化算法存在時(shí)間復(fù)雜度高或得不到最優(yōu)解的問題，本文基于IC 模型提出D-RIS 算法。D-RIS 算法主要包括以下步驟：

1）生成反向可達(dá)集。隨機(jī)且有放回地選擇n個(gè)節(jié)點(diǎn)，通過在隨機(jī)圖g上進(jìn)行傳播模擬生成θ個(gè)節(jié)點(diǎn)RR 集的集合R。

2）節(jié)點(diǎn)選擇。使用最大覆蓋方法尋找k個(gè)覆蓋最多RR 集的節(jié)點(diǎn)并返回種子節(jié)點(diǎn)集S。

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

定義1（反向可達(dá)集）隨機(jī)圖g中可以到達(dá)v的節(jié)點(diǎn)集，對(duì)于RR 集中的節(jié)點(diǎn)u，g中都有一條從u到v的有向路徑。

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

通過實(shí)例說明在IC 模型下對(duì)圖1 社交網(wǎng)絡(luò)G生成反向可達(dá)集的過程，設(shè)置k=1。圖2 是在G上生成的3個(gè)隨機(jī)圖g1，g2，g3。對(duì)于3個(gè)隨機(jī)選取的源節(jié)點(diǎn)c，b，d生成的3 個(gè)隨機(jī)RR 集R1={c，a}、R2={d，a}、R3={b，c，a}，因?yàn)楣?jié)點(diǎn)a出現(xiàn)在3 個(gè)隨機(jī)RR 集中，所以節(jié)點(diǎn)a是影響力最大的節(jié)點(diǎn)，最終返回結(jié)果為S={a}。

圖2 基于社交網(wǎng)絡(luò)G 生成的隨機(jī)圖Fig.2 Random graphs generated based on social network G

1.3.1 反向可達(dá)集數(shù)量確定

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

1）單調(diào)性。設(shè)影響力傳播范圍函數(shù)f，對(duì)于任意反向可達(dá)集的數(shù)量q1

2）子模性。對(duì)于圖的節(jié)點(diǎn)總數(shù)t，設(shè)影響力傳播范圍函數(shù)f，反向可達(dá)集數(shù)量q10，若q1

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

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

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

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

算法1反向可達(dá)集生成算法

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

基于影響力傳播函數(shù)滿足單調(diào)性和子模性的特點(diǎn)，根據(jù)網(wǎng)絡(luò)中節(jié)點(diǎn)實(shí)時(shí)傳播情況，提出一種確定隨機(jī)RR 集臨界值θ的方法，并遵循反向可達(dá)集采樣框架，生成θ個(gè)反向可達(dá)集。

1.3.2 種子節(jié)點(diǎn)選擇

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

1）每次算法在R集中選擇一個(gè)覆蓋最多RR 集數(shù)量的節(jié)點(diǎn)v。

2）刪除R集中節(jié)點(diǎn)v所在的所有反向可達(dá)集，被刪除的反向可達(dá)集中的節(jié)點(diǎn)都有一條通過節(jié)點(diǎn)v能到達(dá)的路徑。

3）將節(jié)點(diǎn)v加入到S集中，更新R集進(jìn)行下一次迭代。

4）選出節(jié)點(diǎn)集S=k，迭代結(jié)束。

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

算法2節(jié)點(diǎn)選擇算法

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

2 實(shí)驗(yàn)與結(jié)果分析

2.1 實(shí)驗(yàn)數(shù)據(jù)集

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

表2 數(shù)據(jù)集信息Table 2 Datasets information

2.2 結(jié)果分析

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

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

2）HighDegree 算法。該算法是基于節(jié)點(diǎn)中心性的經(jīng)典啟發(fā)式算法，選擇k個(gè)度最大的節(jié)點(diǎn)作為種子節(jié)點(diǎn)集。

3）LIR［13］算法。該算法是基于拓?fù)浣Y(jié)構(gòu)的啟發(fā)式算法，選取并排序局部度最大的節(jié)點(diǎn)進(jìn)而選取種子節(jié)點(diǎn)集。

4）pBmH［14］算法。該算法是基于拓?fù)浣Y(jié)構(gòu)的啟發(fā)式算法，考慮了節(jié)點(diǎn)受多重鄰居節(jié)點(diǎn)的影響，避免了富人俱樂部現(xiàn)象。

5）RIS［17］算法。該算法是反向影響抽樣算法，通過生成一定理論閾值數(shù)量的反向可達(dá)集進(jìn)而選取種子節(jié)點(diǎn)集。

設(shè)置以下3 種仿真實(shí)驗(yàn)：

1）D-RIS 算法傳播規(guī)律合理性驗(yàn)證。使用Slashdot 數(shù)據(jù)集對(duì)RIS 算法中影響力傳播函數(shù)滿足單調(diào)性和子模性進(jìn)行分析與驗(yàn)證。

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

3）D-RIS算法與經(jīng)典算法的性能比較。對(duì)D-RIS算法與CELF 算法、HighDegree 算法、LIR 算法和pBmH算法在兩個(gè)真實(shí)數(shù)據(jù)集上進(jìn)行影響力傳播范圍和運(yùn)行時(shí)間比較，以驗(yàn)證D-RIS 算法的時(shí)效性更優(yōu)。

2.2.1 D-RIS 算法傳播規(guī)律合理性驗(yàn)證

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

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

圖3 RIS 算法和D-RIS 算法在Slashdot 數(shù)據(jù)集中反向可達(dá)集生成比例與影響力傳播范圍的關(guān)系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 算法的曲線趨勢可以看出，影響力傳播函數(shù)由于滿足單調(diào)性和子模性，因此出現(xiàn)遞增后逐漸減緩的情況。同時(shí)，對(duì)D-RIS 算法進(jìn)行驗(yàn)證，結(jié)果表明隨著反向可達(dá)集數(shù)量的增加曲線上升趨勢先增大后趨于平緩。RIS 算法需要提前預(yù)設(shè)反向可達(dá)集生成比例，若選取不合理則導(dǎo)致算法達(dá)不到最優(yōu)影響傳播范圍或增加時(shí)間成本。D-RIS 算法只需給定一個(gè)較小的反向可達(dá)集生成比例，就可自動(dòng)加倍調(diào)試反向可達(dá)集生成比例直到滿足條件時(shí)停止。因此，該實(shí)驗(yàn)證明了D-RIS 算法傳播規(guī)律的合理性和實(shí)用性。

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

將RIS 算法反向可達(dá)集生成比例分別設(shè)置為0.001、0.2、0.5，在兩個(gè)數(shù)據(jù)集上與D-RIS 算法進(jìn)行影響力傳播范圍和運(yùn)行時(shí)間的比較。

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

圖4 RIS 算法和D-RIS 算法在Slashdot 數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果比較（反向可達(dá)集生成比例為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 數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果比較（反向可達(dá)集生成比例為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）設(shè)置RIS 算法反向可達(dá)集生成比例為0.2。如圖6、圖7 可知，當(dāng)RIS 算法的反向可達(dá)集生成比例為0.2 時(shí)，在Slashdot 數(shù)據(jù)集中，兩種算法的影響力傳播范圍接近，但D-RIS 算法的運(yùn)行效率高于RIS 算法。在Epinions 數(shù)據(jù)集中，D-RIS 算法在獲得較大影響力傳播范圍的情況下，大幅降低了運(yùn)行時(shí)間，且選取的種子節(jié)點(diǎn)集個(gè)數(shù)越多，在運(yùn)行效率方面優(yōu)勢越明顯。

圖6 RIS 算法和D-RIS 算法在Slashdot 數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果比較（反向可達(dá)集生成比例為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 數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果比較（反向可達(dá)集生成比例為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）設(shè)置RIS 算法反向可達(dá)集生成比例為0.5。由圖8、圖9 可知，當(dāng)RIS 算法的反向可達(dá)集生成比例設(shè)置為0.5 時(shí)，在兩個(gè)數(shù)據(jù)集上，D-RIS 算法有較大的影響力傳播范圍，且運(yùn)行效率遠(yuǎn)高于RIS算法。由此可以看出，過大的反向可達(dá)集生成比例會(huì)增加算法最終的時(shí)間成本。對(duì)于Slashdot 數(shù)據(jù)集，RIS 算法的運(yùn)行時(shí)間是D-RIS 算法的2 倍多。對(duì)于Epinions 數(shù)據(jù)集，RIS 算法的運(yùn)行時(shí)間是D-RIS 算法的7 倍多，因此D-RIS 算法具有更高的運(yùn)行效率。

圖8 RIS 算法和D-RIS 算法在Slashdot 數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果比較（反向可達(dá)集生成比例為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 數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果比較（反向可達(dá)集生成比例為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）

在兩個(gè)真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明：1）當(dāng)RIS算法的反向可達(dá)集生成比例的理論閾值設(shè)置太小時(shí)影響力傳播范圍較小，當(dāng)理論閾值設(shè)置太大時(shí)運(yùn)行效率太差，D-RIS 算法在達(dá)到較優(yōu)的影響力傳播范圍的同時(shí)運(yùn)行效率更高；2）與RIS 算法相比，D-RIS 算法避免了反向可達(dá)集生成比例的理論閾值設(shè)置不準(zhǔn)確，導(dǎo)致達(dá)不到最優(yōu)影響力傳播范圍或增加時(shí)間成本的問題。對(duì)于目前復(fù)雜的社交網(wǎng)絡(luò)，D-RIS 算法無需重復(fù)計(jì)算，可自動(dòng)調(diào)試生成一定比例的反向可達(dá)集，因此更適用于后續(xù)拓?fù)浣Y(jié)構(gòu)變化的社交網(wǎng)絡(luò)。

2.2.3 D-RIS 算法與經(jīng)典算法的性能比較

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

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

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

由于5 種算法的運(yùn)行時(shí)間相差較大，因此運(yùn)行時(shí)間設(shè)置為T=2y，其中y表示縱坐標(biāo)數(shù)值。根據(jù)圖10、圖11實(shí)驗(yàn)結(jié)果分析可知：

2）相比LIR、pBmH 和HighDegree 啟發(fā)式算法，D-RIS 算法雖在運(yùn)行速度方面表現(xiàn)較差，但影響力傳播范圍明顯更優(yōu)。在Epinions 數(shù)據(jù)集中，啟發(fā)式算法的影響力傳播范圍僅有D-RIS 算法的50%左右。在Slashdot 數(shù)據(jù)集中，D-RIS 算法的影響力傳播范圍優(yōu)勢更為明顯。可見，啟發(fā)式算法雖有極高的運(yùn)行效率，但未考慮到復(fù)雜網(wǎng)絡(luò)后續(xù)結(jié)構(gòu)變化導(dǎo)致選取的種子節(jié)點(diǎn)不夠準(zhǔn)確，影響力傳播范圍較小且得不到最優(yōu)解，同時(shí)在不同數(shù)據(jù)集中啟發(fā)式算法的穩(wěn)定性不佳。

通過以上算法的對(duì)比實(shí)驗(yàn)分析可知：D-RIS 算法在影響力傳播范圍和運(yùn)行時(shí)間兩方面取得了較好的平衡，且表現(xiàn)出較好的通用性和穩(wěn)定性，更適用于拓?fù)浣Y(jié)構(gòu)變化和規(guī)模較大的社交網(wǎng)絡(luò)。

3 結(jié)束語

本文基于獨(dú)立級(jí)聯(lián)模型，結(jié)合反向可達(dá)集采樣提出一種改進(jìn)的影響力最大化算法D-RIS，根據(jù)影響力傳播函數(shù)的單調(diào)性和子模性，設(shè)置隨機(jī)生成反向可達(dá)集數(shù)量臨界值的判斷條件，自動(dòng)調(diào)試生成一定數(shù)量的反向可達(dá)集。實(shí)驗(yàn)結(jié)果表明，D-RIS 算法可在獲得較大影響力傳播范圍的同時(shí)避免增加時(shí)間成本，并且能較好地應(yīng)用于拓?fù)浣Y(jié)構(gòu)變化和規(guī)模較大的社交網(wǎng)絡(luò)。下一步可將D-RIS 算法擴(kuò)展到多關(guān)系社交網(wǎng)絡(luò)的影響力傳播模型中，解決社交網(wǎng)絡(luò)中多條信息同時(shí)傳播情況下的影響力最大化問題。