王璿，張瑜，周軍鋒，陳子陽(yáng),2

（1.東華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，上海 201620；2.上海立信會(huì)計(jì)金融學(xué)院信息管理學(xué)院，上海 201620）

0 引言

影響力最大化（IM,influence maximization）[1-2]研究如何從社交網(wǎng)絡(luò)中選擇一組最具影響力的種子節(jié)點(diǎn)，基于這些節(jié)點(diǎn)發(fā)起信息傳播，使最終的傳播范圍最大化。該問(wèn)題廣泛應(yīng)用在產(chǎn)品營(yíng)銷(xiāo)[3]、疾病控制[4]和個(gè)性化推薦[5]等方面。例如，商家會(huì)從社交網(wǎng)絡(luò)中選擇最具影響力的部分用戶(hù)，基于這些用戶(hù)對(duì)產(chǎn)品進(jìn)行推廣和營(yíng)銷(xiāo)，使更多的用戶(hù)了解并最終轉(zhuǎn)化為潛在顧客。

影響力最大化問(wèn)題需要基于特定傳播模型來(lái)描述信息在網(wǎng)絡(luò)中的傳播過(guò)程。目前使用最為廣泛的是獨(dú)立級(jí)聯(lián)（IC,independent cascade）模型[6]和線(xiàn)性閾值（LT,linear threshold）模型[7]。不同的傳播模型適用于不同類(lèi)型的社交網(wǎng)絡(luò)。社交網(wǎng)絡(luò)可以分為個(gè)體網(wǎng)絡(luò)和群體網(wǎng)絡(luò)[8]。個(gè)體網(wǎng)絡(luò)主要考慮單個(gè)節(jié)點(diǎn)和單個(gè)節(jié)點(diǎn)之間的影響關(guān)系，適用于獨(dú)立級(jí)聯(lián)模型。群體網(wǎng)絡(luò)主要考慮單個(gè)節(jié)點(diǎn)和多個(gè)節(jié)點(diǎn)之間、多個(gè)節(jié)點(diǎn)和多個(gè)節(jié)點(diǎn)之間的影響關(guān)系，適用于線(xiàn)性閾值模型。基于選定的傳播模型，影響力最大化問(wèn)題等價(jià)于選擇影響力盡可能大的種子集。

為了得到合適的種子集，Kempe 等[1]首先基于IC模型和LT 模型提出了一個(gè)貪心算法。該算法可以同時(shí)在這2 個(gè)模型上提供近似保證（ε為誤差參數(shù)），但是時(shí)間復(fù)雜度過(guò)高，難以適用于大規(guī)模社交網(wǎng)絡(luò)。后續(xù)的研究者陸續(xù)提出基于某種特定傳播模型的高效算法[10-12]。這些算法雖然在大規(guī)模社交網(wǎng)絡(luò)上的運(yùn)行效率得到提升，但是僅局限于特定傳播模型中，只能解決單一類(lèi)型社交網(wǎng)絡(luò)下的影響力最大化問(wèn)題，當(dāng)使用在不同類(lèi)型社交網(wǎng)絡(luò)上時(shí)效果較差[13]。為解決該問(wèn)題，本文提出一種可以同時(shí)支持IC 模型和LT 模型的高效種子集求解算法，該算法包括3 個(gè)階段。1)預(yù)處理階段，基于節(jié)點(diǎn)度篩選策略，篩選出有效節(jié)點(diǎn)集；2)采樣階段，基于邊界約束策略，確定采樣次數(shù)并從有效節(jié)點(diǎn)集中采樣；3)種子選擇階段，應(yīng)用貪心策略選擇種子節(jié)點(diǎn)，并基于影響力增量剪枝策略，剪枝種子選擇時(shí)的部分無(wú)效排序。具體來(lái)說(shuō)，本文的貢獻(xiàn)如下。

1)提出邊界約束策略，以快速確定估計(jì)最優(yōu)采樣次數(shù)。提出基于節(jié)點(diǎn)度篩選策略，以提升種子集質(zhì)量。提出基于影響力增量剪枝策略，以提高算法運(yùn)行效率。

2)結(jié)合這3 個(gè)策略，提出一種三階段的影響力最大化（MTIM,mixed three-stage influence maximization）算法，該算法不但能夠同時(shí)支持IC 模型和LT 模型，而且具備優(yōu)越的近似保證和期望時(shí)間復(fù)雜度。

3)將MTIM 與IMM、TIM、PMC 等貪心算法，以及OneHop、DegreeDiscount 等啟發(fā)式算法在4 個(gè)真實(shí)社交網(wǎng)絡(luò)上對(duì)比實(shí)驗(yàn)。結(jié)果表明，MTIM 算法能夠適用于大規(guī)模社交網(wǎng)絡(luò)，提供近似保證，并有效提升影響范圍和效率。

1 背景知識(shí)和相關(guān)工作

1.1 背景知識(shí)

本文使用加權(quán)有向圖G=(V,E,W)表示社交網(wǎng)絡(luò)，其中，V表示節(jié)點(diǎn)集（用戶(hù)），E表示有向邊集（用戶(hù)間關(guān)系），W表示每條有向邊對(duì)應(yīng)權(quán)值的集合。W(u,v)∈[0,1]表示有向邊(u,v)的權(quán)值，代表傳播過(guò)程中節(jié)點(diǎn)u把信息傳遞給節(jié)點(diǎn)v的概率，即u激活v的概率。為表述方便，使用n和m分別表示節(jié)點(diǎn)集V和有向邊集E的大小，In(v)和Out(v)分別表示節(jié)點(diǎn)v的入鄰居集合和出鄰居集合。

影響力最大化問(wèn)題旨在通過(guò)種子集（信息傳播的源頭節(jié)點(diǎn)）進(jìn)行信息傳播，實(shí)現(xiàn)傳播范圍的最大化。而信息如何在網(wǎng)絡(luò)中傳播是由傳播模型確定的。在信息傳播過(guò)程中，如果節(jié)點(diǎn)v接受某種信息，則稱(chēng)該節(jié)點(diǎn)為激活節(jié)點(diǎn)，否則稱(chēng)其為未激活節(jié)點(diǎn)。目前主流的2 種影響力傳播模型的主要區(qū)別在于節(jié)點(diǎn)的激活方式。

1)IC 模型。假設(shè)節(jié)點(diǎn)u在i時(shí)刻被激活，則節(jié)點(diǎn)u在i+1 時(shí)刻只有一次機(jī)會(huì)以傳播概率W(u,v)激活其尚未被激活的出鄰居v∈Out(u)。

2)LT 模型。每個(gè)節(jié)點(diǎn)有概率閾值φ∈[0,1]，該閾值表示節(jié)點(diǎn)被激活的難易程度。如果節(jié)點(diǎn)v在i時(shí)刻未被激活，且滿(mǎn)足，則節(jié)點(diǎn)v在i+1 時(shí)刻被激活，其中A是節(jié)點(diǎn)v在前i時(shí)刻被激活的入鄰居集合。

給定社交網(wǎng)絡(luò)G、種子集S?V以及傳播模型M，傳播過(guò)程如下。1)在第0 時(shí)刻，S中的所有節(jié)點(diǎn)被激活，其他節(jié)點(diǎn)未被激活。2)如果一個(gè)節(jié)點(diǎn)在i時(shí)刻被激活，則該節(jié)點(diǎn)在i+1 時(shí)刻只有一次機(jī)會(huì)激活其尚未被激活的出鄰居（激活方式取決于傳播模型M），之后它就不能再激活任何節(jié)點(diǎn)。3)重復(fù)步驟2)，直至不再有節(jié)點(diǎn)被激活，傳播結(jié)束。種子集S在傳播模型M下激活節(jié)點(diǎn)的總數(shù)表示為σ(S)，代表種子集S的預(yù)期影響范圍。表1 給出了本文的常用符號(hào)。

表1 常用符號(hào)設(shè)置

問(wèn)題定義（影響力最大化問(wèn)題）給定社交網(wǎng)絡(luò)G、參數(shù)k以及傳播模型M，影響力最大化問(wèn)題旨在找出種子集S?V且=k，使種子集預(yù)期影響范圍σ(S)最大化。

1.2 相關(guān)工作

現(xiàn)有影響力最大化算法大多基于反向影響采樣（RIS,reverse influence sampling）技術(shù)[9]選取種子節(jié)點(diǎn)。反向影響采樣就是先隨機(jī)選一個(gè)節(jié)點(diǎn)，從該節(jié)點(diǎn)出發(fā)，沿著該節(jié)點(diǎn)所有入邊的相反方向模擬傳播，這樣反向可達(dá)的節(jié)點(diǎn)集合就稱(chēng)為反向可達(dá)集（RR set,reverse reachable set）；再生成足夠多的反向可達(dá)集，從中找出影響力最大的種子集（即能夠覆蓋最多反向可達(dá)集的節(jié)點(diǎn)集合）。這里，如果節(jié)點(diǎn)v在集合R中出現(xiàn)，則稱(chēng)節(jié)點(diǎn)v覆蓋集合R；如果集合S中至少有一個(gè)節(jié)點(diǎn)在集合R中出現(xiàn)，則稱(chēng)集合S覆蓋集合R。根據(jù)文獻(xiàn)[9]可知，對(duì)于從節(jié)點(diǎn)v反向采樣得到的反向可達(dá)集R，節(jié)點(diǎn)u∈V{v}覆蓋集合R的概率等于節(jié)點(diǎn)u激活節(jié)點(diǎn)v的概率。利用RIS 技術(shù)，可以使反向可達(dá)集更容易包含極具影響力的節(jié)點(diǎn)，從而提高算法效率。

例1（反向可達(dá)集構(gòu)建示例）以IC 模型為例，反向可達(dá)集構(gòu)造如下。首先在圖1(a)所示的社交網(wǎng)絡(luò)g中隨機(jī)選擇節(jié)點(diǎn)b，此時(shí)反向可達(dá)集R=。接著沿節(jié)點(diǎn)b的所有入邊反向執(zhí)行廣度優(yōu)先遍歷，對(duì)入邊(c,b)生成隨機(jī)數(shù)r1=0.3。由于r1≤0.6，節(jié)點(diǎn)c被節(jié)點(diǎn)b激活，將節(jié)點(diǎn)c加入R中，即R={b,c}。同理，為節(jié)點(diǎn)c的入邊(a,c)生成隨機(jī)數(shù)r2=0.9。由于r2＞0.8，節(jié)點(diǎn)a沒(méi)有被節(jié)點(diǎn)c激活，不將節(jié)點(diǎn)a加入R中，圖1(b)中的虛線(xiàn)表示遍歷失敗，灰線(xiàn)表示遍歷成功，黑線(xiàn)表示社交網(wǎng)絡(luò)g中的有向邊。此時(shí)不再有節(jié)點(diǎn)能被激活，最終反向可達(dá)集R={b,c}。

圖1 反向可達(dá)集構(gòu)建示例

Borgs 等[9]在種子集預(yù)期影響范圍與反向可達(dá)集之間建立了以下聯(lián)系。

引理1設(shè)S?V為種子集，R為傳播模型M下生成的反向可達(dá)集，則

引理1 表明，可以使用反向可達(dá)集來(lái)估計(jì)任意種子集的預(yù)期影響范圍。假設(shè)生成一個(gè)反向可達(dá)集集合 R={R1,R2,…}，令ΛR(S)表示種子集S覆蓋的反向可達(dá)集數(shù)量，代表種子集S在集合R 中的覆蓋范圍，則是對(duì)種子集預(yù)期影響范圍的無(wú)偏估計(jì)，即E[σ(S)]=。

Borgs 等的解決方案。利用引理1，Borgs 等[9]提出一種影響力最大化算法，該算法分為兩步：1)采樣，即生成足夠多的反向可達(dá)集；2)種子選擇，即貪心地選擇對(duì)反向可達(dá)集覆蓋率最大的種子集。Borgs 等證明，如果檢驗(yàn)了條邊，則該算法可以提供近似保證。

TIM 和IMM。Tang 等[14-15]基于RIS 技術(shù)提出了TIM 算法和IMM 算法，這些算法的時(shí)間復(fù)雜度均為，明顯優(yōu)于Borgs 等的算法，但是仍存在大量冗余的計(jì)算開(kāi)銷(xiāo)。TIM 算法利用切爾諾夫邊界（Chernoff bound）來(lái)確定采樣次數(shù)，而不再通過(guò)檢驗(yàn)遍歷的邊數(shù)來(lái)判斷是否滿(mǎn)足近似保證，該算法適用于LT 模型。而IMM 算法利用鞅技術(shù)改進(jìn)，進(jìn)一步減少采樣次數(shù)，能夠同時(shí)適用IC模型和LT 模型，算法性能穩(wěn)定高效。

其他基于特定傳播模型的解決方案。Sun 等[10]基于多輪擴(kuò)散（MRT,multi-round triggering）模型提出的MRIM 算法，解決了多輪擴(kuò)散下的影響力最大化問(wèn)題。Guo 等[11]基于觸發(fā)（TR,triggering）模型提出的IMCB 算法，從社區(qū)結(jié)構(gòu)角度解決了影響分布不平衡的問(wèn)題。Guo 等[12]基于加權(quán)級(jí)聯(lián)（WC,weighted cascade）模型提出SUBSIM 算法，對(duì)反向可達(dá)集生成過(guò)程進(jìn)行了優(yōu)化。

2 MTIM 算法

本文針對(duì)現(xiàn)有算法效率低、適用傳播模型單一的問(wèn)題，提出一種三階段影響力最大化算法——MTIM 算法。MTIM 算法包括3 個(gè)階段。

1)預(yù)處理階段。基于節(jié)點(diǎn)度篩選策略，根據(jù)節(jié)點(diǎn)的出度和被鏈接程度，篩選出有效節(jié)點(diǎn)集C。

2)采樣階段?；谶吔缂s束策略，先迭代地確定近似最優(yōu)采樣次數(shù)θ*，再?gòu)腃 中隨機(jī)選點(diǎn)采樣θ*次，得到反向可達(dá)集集合 R={R1,R2,…,Rθ*}。

3)種子選擇階段。應(yīng)用貪心策略找出對(duì)集合R 覆蓋率最大的種子集；同時(shí)，基于影響力增量剪枝策略，剪枝部分種子選擇時(shí)的無(wú)效排序。

MTIM 算法的具體流程如算法1 所示。

2.1 基于節(jié)點(diǎn)度篩選策略的預(yù)處理

RIS 方法每次從整個(gè)社交網(wǎng)絡(luò)中隨機(jī)選點(diǎn)采樣，由于所選節(jié)點(diǎn)質(zhì)量參差不齊，導(dǎo)致求解出的種子集對(duì)反向可達(dá)集的覆蓋率偏低，使種子集影響范圍有限。針對(duì)該問(wèn)題，本文提出基于節(jié)點(diǎn)度篩選策略。該策略的基本思想為根據(jù)節(jié)點(diǎn)的出度和被鏈接程度（lv,linked value）[16]，篩選出潛在影響力較大的節(jié)點(diǎn)集合（即有效節(jié)點(diǎn)集）。利用該策略，不僅可以縮小采樣時(shí)的選點(diǎn)范圍，而且可以提高種子集對(duì)反向可達(dá)集的覆蓋率，從而有效改善種子質(zhì)量。

預(yù)處理階段的主要工作如下。1)根據(jù)節(jié)點(diǎn)的出度和被鏈接程度，從社交網(wǎng)絡(luò)G中篩選出節(jié)點(diǎn)集合A 和集合B，且；2)取這2 個(gè)集合的并集作為有效節(jié)點(diǎn)集C。算法2 為預(yù)處理階段的偽代碼。

對(duì)于有向圖中的節(jié)點(diǎn)，其度包含出度和入度這2 個(gè)含義，因而從這2 個(gè)方面考慮。1)出度大的節(jié)點(diǎn)，影響其出鄰居的潛在可能性較大，則其影響力往往較大。因而，可以根據(jù)節(jié)點(diǎn)的出度降序排序，獲得出度前r% 大的節(jié)點(diǎn)集合A（算法2 的步驟2)～步驟5)）。2)由于傳播在多個(gè)節(jié)點(diǎn)間進(jìn)行，考慮單個(gè)節(jié)點(diǎn)的入度并無(wú)意義，可求單個(gè)節(jié)點(diǎn)被其入鄰居鏈接的程度。被鏈接程度大的節(jié)點(diǎn)，其被入鄰居影響的潛在可能性大，則影響力大的節(jié)點(diǎn)往往存在于被鏈接程度大的節(jié)點(diǎn)的反向可達(dá)集中。因而，可以先根據(jù)式(2)迭代地計(jì)算節(jié)點(diǎn)的被鏈接程度（d為平衡因子），再根據(jù)節(jié)點(diǎn)的被鏈接程度降序排序，獲得被鏈接程度前r% 大的節(jié)點(diǎn)集合B（算法2 的步驟6)～步驟9)）。

此時(shí)，潛在影響力大的節(jié)點(diǎn)多在集合A 和集合B 中，因而，可以取兩集合的并集作為有效節(jié)點(diǎn)集C 輸出（算法2 的步驟10)～步驟11)）。

例2（預(yù)處理示例）對(duì)圖1(a)社交網(wǎng)絡(luò)g預(yù)處理流程如下。假設(shè)篩選比例為70%。首先，計(jì)算每個(gè)節(jié)點(diǎn)的出度，并根據(jù)出度降序排序，取出度前70%大的節(jié)點(diǎn)集 A={a,c,d,e}；然后，計(jì)算每個(gè)節(jié)點(diǎn)的被鏈接程度，并根據(jù)被鏈接程度降序排序，取被鏈接程度前70%大的節(jié)點(diǎn)集 B={b,c,d,e}；最后，取A 和B 的并集 C={a,b,c,d,e}作為有效節(jié)點(diǎn)集。

2.2 基于邊界約束策略的采樣

針對(duì)RIS 方法難以確定采樣次數(shù)的問(wèn)題，提出邊界約束策略。該策略的基本思想如下，首先估計(jì)出近似最優(yōu)采樣次數(shù)的取值區(qū)間；然后根據(jù)該區(qū)間依次計(jì)算不同采樣次數(shù)下影響范圍近似解下界和最優(yōu)解上界之比，不斷計(jì)算直至該比值達(dá)到給定要求時(shí)停止。利用該策略，可以快速確定近似最優(yōu)采樣次數(shù)。

采樣階段的主要工作如下，首先估計(jì)出近似最優(yōu)采樣次數(shù)θ*；然后從預(yù)處理階段獲得的有效節(jié)點(diǎn)集C中隨機(jī)選點(diǎn)采樣θ*次，從而得到反向可達(dá)集集合R={R1,R2,…,Rθ*}。

2.2.1 最優(yōu)采樣次數(shù)的估計(jì)

為估計(jì)采樣次數(shù)θ，需進(jìn)一步分析。假設(shè)是期望影響力最大的k大種子集，即OPT=，根據(jù)引理1，如果θ大小適當(dāng)，則≈OPT。給定ε∈[0,1]，根據(jù)文獻(xiàn)[15]可推導(dǎo)出近似最優(yōu)采樣次數(shù)θ*，如式(3)所示。

根據(jù)式(3)，如果OPT 已知，則可以計(jì)算出近似最優(yōu)采樣次數(shù)。但是OPT 實(shí)際未知，因而考慮根據(jù)OPT 的取值范圍估計(jì)出θ*的取值區(qū)間。

已知OPT∈[1,n]，由于中包含k個(gè)節(jié)點(diǎn)，至少能夠影響到這k個(gè)節(jié)點(diǎn)，則可知OPT∈[k,n]。為估計(jì)出θ*的取值區(qū)間，給出引理2[15]與定理1。

引理2給定ε∈(0,1)，?≥1，令θO表示理論最優(yōu)采樣次數(shù)，θ*表示根據(jù)式(3)計(jì)算出的近似最優(yōu)采樣次數(shù)，則滿(mǎn)足

定理1給定x∈[k,n]，令θmax=2λ*ε?2k?1，θmin=λ*n?1，根據(jù)引理2，可知

證明構(gòu)造函數(shù)θ(x)=λ*ε?2x?1，可知該函數(shù)隨著x的增大而單調(diào)遞減。已知x∈[k,n]，則函數(shù)值域?yàn)閇θ(n),θ(k)]。根據(jù)引理2，θmin≤θ(n)≤θ(x)；同時(shí)根據(jù)式(3)計(jì)算的近似最優(yōu)值恰在θ(x)的值域內(nèi)，則必然滿(mǎn)足

證畢。

根據(jù)定理1，可以估計(jì)出近似最優(yōu)采樣次數(shù)的取值區(qū)間為[θmin,θmax]。

2.2.2 影響范圍邊界的估計(jì)

為了從取值區(qū)間[θmin,θmax]中找出近似最優(yōu)采樣次數(shù)θ*，可以根據(jù)該區(qū)間依次計(jì)算出不同采樣次數(shù)θ下影響范圍的近似比，即當(dāng)前解下界和最優(yōu)解上界之比，如果該比值大于或等于，則立刻停止并返回當(dāng)前采樣次數(shù)θ，否則將當(dāng)前采樣次數(shù)θ乘以2 并重復(fù)上述步驟。為估計(jì)影響范圍的邊界，給出引理3[17]。

引理3給定種子集S和由θ個(gè)反向可達(dá)集構(gòu)成的集合 R={R1,R2,…,Rθ}，則對(duì)于?λ＞0，滿(mǎn)足

根據(jù)引理3，當(dāng)前種子集S影響范圍的近似比可以用表示。

2.2.3 算法描述

根據(jù)2.2.1 節(jié)估計(jì)出的近似最優(yōu)采樣次數(shù)θ*的取值區(qū)間[θmin,θmax]，以及2.2.2 節(jié)判斷是否為近似最優(yōu)采樣次數(shù)的邊界約束條件，將其組合，即可構(gòu)成基于邊界約束策略的采樣階段。

算法3 為采樣階段的偽代碼。具體地，首先，根據(jù)式(5)初始化θmin和θmax（算法3 的步驟1)）；接著，至多執(zhí)行imax次for 循環(huán)（算法3 的步驟3)～步驟13)），在第i次時(shí)，先從有效節(jié)點(diǎn)集C 中隨機(jī)選擇節(jié)點(diǎn)采樣，生成θi個(gè)反向可達(dá)集，再根據(jù)式(7)和式(8)計(jì)算出當(dāng)前采樣次數(shù)下種子集Si影響范圍下界與上界之比，如果該比值大于或等于或者當(dāng)前執(zhí)行第imax次循環(huán)，則停止并返回當(dāng)前種子集，否則將θmin乘以2 并重復(fù)計(jì)算。組合后算法的近似比為，原因在于：1)如果循環(huán)次數(shù)少于imax時(shí)就停止，則必能夠提供近似保證；2)如果循環(huán)次數(shù)為imax時(shí)才停止，此時(shí)的采樣次數(shù)必大于或等于θ*，則必能采樣足夠多的反向可達(dá)集，即必能提供近似保證。

算法4 為生成反向可達(dá)集集合的偽代碼。具體流程如下。首先，將集合H 初始化為空集（算法4的步驟1)）；接著，執(zhí)行θ次for 循環(huán)（算法4 的步驟2)～步驟6)），每次隨機(jī)選擇節(jié)點(diǎn)v∈C，沿該節(jié)點(diǎn)所有入邊的相反方向進(jìn)行廣度優(yōu)先遍歷（即基于傳播模型發(fā)起信息傳播），將激活的節(jié)點(diǎn)依次插入反向可達(dá)集Ri，并將Ri插入H；最后，輸出H（算法4 的步驟7)）。

例3（采樣示例）IC 模型下采樣階段流程如下。假設(shè)采樣次數(shù)θ=3，參數(shù)k=1。預(yù)處理階段從圖1(a)中篩選出有效節(jié)點(diǎn)集 C={a,b,c,d,e}（詳見(jiàn)例2）。如圖2 所示，從C 中隨機(jī)選點(diǎn)b、c、e，生成反向可達(dá)集集合 R={R1,R2,R3}，其中R1={b,c}，R2={a,c}，R3={b,c,d,e}。圖2 中的虛線(xiàn)表示遍歷失敗，灰線(xiàn)表示遍歷成功，黑線(xiàn)表示社交網(wǎng)絡(luò)g中的有向邊。因?yàn)楣?jié)點(diǎn)c對(duì)R 覆蓋率最大，即節(jié)點(diǎn)c的影響力最大，所以將其加入種子集。最后，返回種子集{c}。

圖2 采樣示例

2.3 基于影響力增量剪枝策略的種子選擇

由于RIS 方法每次找出對(duì)反向可達(dá)集集合R覆蓋率最高的種子節(jié)點(diǎn)后，需要更新其他節(jié)點(diǎn)對(duì)R的覆蓋率，并根據(jù)各節(jié)點(diǎn)對(duì)R 的覆蓋率重新排序，導(dǎo)致存在節(jié)點(diǎn)對(duì)R 的覆蓋率更新后相對(duì)排名不變時(shí)的無(wú)效排序，影響算法運(yùn)行效率。針對(duì)該問(wèn)題，本文提出基于影響力增量的剪枝策略。該策略的基本思想為保存前一輪排序后的數(shù)據(jù)，在刪除該節(jié)點(diǎn)及其覆蓋的反向可達(dá)集后，比較前一輪中原次大節(jié)點(diǎn)更新后和第三大節(jié)點(diǎn)更新前對(duì)R 的覆蓋率，若前者大于等于后者，則直接選擇原次大節(jié)點(diǎn)作為新一輪中的種子，而無(wú)須重新排序。利用該策略，可以剪枝部分種子選擇時(shí)的無(wú)效排序，從而降低算法時(shí)耗。

種子選擇階段的主要工作如下。應(yīng)用貪心策略找出對(duì)R 覆蓋率最高的種子集S；同時(shí)，剪枝節(jié)點(diǎn)對(duì)R 的覆蓋率更新后相對(duì)排名不變時(shí)的無(wú)效排序。

算法5 為種子選擇階段的偽代碼。具體地，首先，初始化種子集為空集（算法5 的步驟1)），計(jì)算出每個(gè)節(jié)點(diǎn)v∈V對(duì)集合R 的覆蓋率FR({v})，保存至pairs （算法5 的步驟2)～步驟5)）；接著，執(zhí)行k次for 循環(huán)，每次根據(jù)FR({v})對(duì)pairs 降序排序，選擇對(duì)R 的覆蓋率最高的節(jié)點(diǎn)，將其加入種子集，并刪除該節(jié)點(diǎn)及其覆蓋的反向可達(dá)集（算法5 的步驟6)～步驟9)和步驟12)）。同時(shí)，至多執(zhí)行k?i次while 循環(huán)，每次保存前一輪排序結(jié)果，比較前一輪中次大節(jié)點(diǎn)更新后以及第三大節(jié)點(diǎn)更新前對(duì)R 的覆蓋率，若前者大于等于后者，則直接選擇原次大節(jié)點(diǎn)作為新一輪的種子；重復(fù)比較，直至不滿(mǎn)足該關(guān)系或者種子個(gè)數(shù)達(dá)k時(shí)結(jié)束循環(huán)（算法5 的步驟10)～步驟21)）；最后，將種子集S輸出（算法5 的步驟22)）。

例4（種子選擇示例）令表示第i輪中節(jié)點(diǎn)v對(duì)集合R 的覆蓋率。如圖3 所示，第1 輪已計(jì)算出每個(gè)節(jié)點(diǎn)對(duì)R 的覆蓋率，降序排序后選擇當(dāng)前對(duì)R 覆蓋率最大的節(jié)點(diǎn)b作為種子，并更新其他節(jié)點(diǎn)影響力。進(jìn)入第2 輪，先比較前一輪中原次大節(jié)點(diǎn)c更新后和原第三大節(jié)點(diǎn)a更新前對(duì)R 的覆蓋率，發(fā)現(xiàn)，則節(jié)點(diǎn)c必為新一輪的最優(yōu)種子，直接選擇節(jié)點(diǎn)c而無(wú)須重新排序。

圖3 種子選擇示例

2.4 MTIM 算法時(shí)間復(fù)雜度分析

預(yù)處理階段（算法2）主要用于篩選有效節(jié)點(diǎn)，其時(shí)間復(fù)雜度為O(n(ncnt+logn))，其中cnt 為迭代次數(shù)。采樣階段（算法3）主要用于生成反向可達(dá)集，其時(shí)間復(fù)雜度為。種子選擇階段（算法5），所花時(shí)間主要與反向可達(dá)集集合R和采樣次數(shù)θ相關(guān)，其時(shí)間復(fù)雜度為。組合3 個(gè)階段后得到的MTIM 算法（算法1），其時(shí)間復(fù)雜度為。

3 實(shí)驗(yàn)與分析

3.1 實(shí)驗(yàn)設(shè)置

實(shí)驗(yàn)的硬件配置Intel(R)Xeon(R)Silver 4208 CPU @ 2.10 GHz，運(yùn)行內(nèi)存64 GB，操作系統(tǒng)Ubuntu 20.04（64 位），所有算法均采用C++實(shí)現(xiàn)并使用G++4.8.5 編譯。

實(shí)驗(yàn)采用4 個(gè)真實(shí)的社交網(wǎng)絡(luò)數(shù)據(jù)集。其中，Slashdot 是提供技術(shù)資訊服務(wù)的社交網(wǎng)絡(luò)；soc-LiveMocha 是提供外語(yǔ)學(xué)習(xí)服務(wù)的社交網(wǎng)絡(luò)；Web-BerkStan 是BerkStan 的社交網(wǎng)絡(luò)；soc-pokec是斯洛伐克的社交網(wǎng)絡(luò)。

表2 給出了數(shù)據(jù)集的統(tǒng)計(jì)信息。其中，|V|表示圖中的節(jié)點(diǎn)個(gè)數(shù)，|E|表示圖中的邊個(gè)數(shù)，Avg.deg表示圖的平均度。

表2 數(shù)據(jù)集的統(tǒng)計(jì)信息

3.2 算法性能比較分析

算法評(píng)價(jià)標(biāo)準(zhǔn)包括：①運(yùn)行時(shí)間，即求解出種子集的時(shí)間；②預(yù)期影響范圍，即求解出的種子集能夠影響到的節(jié)點(diǎn)個(gè)數(shù)。

實(shí)驗(yàn)使用IC 模型和LT 模型，基于4 個(gè)社交網(wǎng)絡(luò)數(shù)據(jù)集分別在k∈{1,10,20,50,100}5 種規(guī)模下實(shí)驗(yàn)。根據(jù)之前的工作[10-15,17]，設(shè)置誤差參數(shù)ε=0.5。根據(jù)表3，不同數(shù)據(jù)集單位時(shí)間篩選節(jié)點(diǎn)總數(shù)在r=70時(shí)最大，因而預(yù)處理階段的篩選比例r%設(shè)置為70%。為避免誤差，本文所涉及的算法都運(yùn)行30 次，各算法評(píng)價(jià)指標(biāo)取其均值。

表3 不同篩選比例r%下的篩選節(jié)點(diǎn)個(gè)數(shù)和篩選時(shí)間比較

為驗(yàn)證算法高效性，設(shè)置對(duì)比算法，具體如下。

1)TIM 算法[14]，為貪心算法。TIM 算法基于反向影響采樣技術(shù)，利用切爾諾夫邊界確定采樣次數(shù)，支持LT 模型，可應(yīng)用于大規(guī)模社交網(wǎng)絡(luò)。本文將該算法用于LT 模型下對(duì)比實(shí)驗(yàn)。

2)IMM 算法[15]，為貪心算法。IMM 算法是TIM算法的改進(jìn)算法，利用鞅技術(shù)確定采樣次數(shù)，同時(shí)支持IC 模型和LT 模型。本文以IMM 算法為基準(zhǔn)，并同時(shí)用于IC 模型和LT 模型下對(duì)比實(shí)驗(yàn)。

3)OneHop 算法[18]，為啟發(fā)式算法。OneHop算法基于跳步思想選取種子，支持IC 模型，是目前精確度最高的啟發(fā)式算法。本文將該算法用于IC模型下對(duì)比實(shí)驗(yàn)。

4)PMC 算法[19]，為貪心算法。PMC 算法基于蒙特卡羅模擬技術(shù)，支持IC 模型。該算法將原圖隨機(jī)切割為τ個(gè)子圖，在子圖中進(jìn)行T 次傳播模擬來(lái)估計(jì)節(jié)點(diǎn)影響力，選擇前k大的節(jié)點(diǎn)作為種子。本文設(shè)置τ=200，T=10 000，并將該算法用于IC模型下對(duì)比實(shí)驗(yàn)。

5)DegreeDiscount 算法[20]，為經(jīng)典啟發(fā)式算法。DegreeDiscount 算法基于折扣度思想選取種子，支持LT 模型。本文將該算法用于LT 模型下對(duì)比實(shí)驗(yàn)。

6)MTIM 算法，為本文算法。

3.2.1 IC 模型下的結(jié)果

第一組實(shí)驗(yàn)。基于IC 模型比較了MTIM、IMM、OneHop、PMC 這4 種算法在不同數(shù)據(jù)集上的預(yù)期影響范圍，結(jié)果如圖4 所示。根據(jù)圖4 可以發(fā)現(xiàn)，1)隨著種子集規(guī)模k的增大，4 種算法的預(yù)期影響范圍總體均呈上升趨勢(shì)，并且種子集預(yù)期影響范圍的增幅隨種子個(gè)數(shù)的增加而遞減。2)MTIM 的預(yù)期影響范圍最廣，IMM 和PMC 次之，而OneHop 表現(xiàn)最差。具體而言，MTIM 算法的預(yù)期影響范圍較IMM 算法提高了約20%，IMM 算法的預(yù)期影響范圍較PMC 算法提高了10%～20%，而OneHop 算法的預(yù)期影響范圍為IMM 算法的50%左右。

圖4 IC 模型下的預(yù)期影響范圍比較

其原因主要是節(jié)點(diǎn)度篩選策略的應(yīng)用。該策略通過(guò)約束采樣范圍，提高種子集S對(duì)反向可達(dá)集集合R 的覆蓋率FR(S)，從而擴(kuò)大影響范圍。根據(jù)式(1)，，即種子集預(yù)期影響范圍E[σ(S)]與覆蓋率FR(S)正相關(guān)。圖5 統(tǒng)計(jì)了k=100時(shí)IMM算法和MTIM 算法在各數(shù)據(jù)集上的覆蓋率，可以發(fā)現(xiàn)MTIM 算法較IMM 算法覆蓋率提高約20%。因而，MTIM 算法較IMM 算法預(yù)期影響范圍提高約20%。而PMC 算法由于需要對(duì)網(wǎng)絡(luò)中的所有節(jié)點(diǎn)進(jìn)行多次傳播模擬，取預(yù)期影響范圍平均值來(lái)估計(jì)節(jié)點(diǎn)影響力，導(dǎo)致實(shí)際結(jié)果不夠精確。OneHop 啟發(fā)式算法基于跳步思想選擇種子，并未考慮復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)，導(dǎo)致所選節(jié)點(diǎn)質(zhì)量不高。因而，IMM 算法、PMC 算法和OneHop 算法的預(yù)期影響范圍均不如MTIM 算法。

圖5 覆蓋率統(tǒng)計(jì)信息

第二組實(shí)驗(yàn)?；贗C 模型比較了MTIM、IMM、OneHop、PMC 這4 種算法在不同數(shù)據(jù)集上的運(yùn)行時(shí)間，結(jié)果如圖6 所示。根據(jù)圖6 可以發(fā)現(xiàn)，1)隨著種子集規(guī)模k的增大，MTIM 算法、IMM 算法和PMC 算法的運(yùn)行時(shí)間及其差距倍增，而OneHop 算法運(yùn)行時(shí)間趨于平穩(wěn)。2)OneHop 的運(yùn)行時(shí)間最短，MTIM 次之，PMC 和IMM 的運(yùn)行時(shí)間較長(zhǎng)。具體而言，當(dāng)k＜20 時(shí)，MTIM 算法與OneHop 算法的性能差異不大；當(dāng)k＞20 時(shí)，MTIM 算法略慢于OneHop 算法。MTIM 算法較IMM 算法快了4～9 倍，且數(shù)據(jù)集規(guī)模越大，提升效果越明顯。PMC 算法較IMM 算法減少運(yùn)行時(shí)間約50%。

圖6 IC 模型下的運(yùn)行時(shí)間比較

其原因主要有兩點(diǎn)。1)邊界約束策略的應(yīng)用。該策略利用更高精度的邊界約束來(lái)估計(jì)最優(yōu)采樣次數(shù)，降低確定采樣次數(shù)時(shí)間，從而提升算法的運(yùn)行效率。圖7(a)統(tǒng)計(jì)了k=100時(shí)IMM 算法和MTIM 算法在各數(shù)據(jù)集上的確定采樣次數(shù)時(shí)間，由于各數(shù)據(jù)集的運(yùn)行時(shí)間相差較大，因此將時(shí)間設(shè)置為T(mén)=lgy，其中y表示實(shí)際運(yùn)行時(shí)間，可以發(fā)現(xiàn)：MTIM 算法較IMM 算法減少確定采樣次數(shù)時(shí)間40%～50%。圖7(b)統(tǒng)計(jì)了k=100時(shí)IMM算法和MTIM算法生成的反向可達(dá)集個(gè)數(shù)（即采樣次數(shù)），可以發(fā)現(xiàn)，MTIM 算法所確定的采樣次數(shù)約為IMM 算法的70%。2)影響力增量剪枝策略的應(yīng)用。該策略避免了部分種子選擇時(shí)的無(wú)效排序。圖7(c)統(tǒng)計(jì)了k=100時(shí)IMM 算法和MTIM 算法在各數(shù)據(jù)集上種子選擇時(shí)的有效排序次數(shù)，可以發(fā)現(xiàn)：MTIM 算法較之IMM 算法剪枝了約15%的無(wú)效排序。因而，MTIM 算法較之IMM 算法快了4～9 倍。而PMC 算法將原社交網(wǎng)絡(luò)隨機(jī)分割為多個(gè)較小規(guī)模的子圖網(wǎng)絡(luò)，從子圖中選擇種子。因而，PMC 算法快于IMM 算法。OneHop 算法基于啟發(fā)式規(guī)則粗略估計(jì)節(jié)點(diǎn)影響力，直接選擇前k大的節(jié)點(diǎn)作為種子。因而，OneHop 算法的運(yùn)行速度總體優(yōu)于MTIM 算法、IMM 算法和PMC 算法。

圖7 統(tǒng)計(jì)信息

3.2.2 LT 模型下的結(jié)果

第一組實(shí)驗(yàn)?；贚T 模型比較了MTIM、IMM、TIM、DegreeDiscount 這4 種算法在不同數(shù)據(jù)集上的預(yù)期影響范圍，結(jié)果如圖8 所示。根據(jù)圖8 可以發(fā)現(xiàn)，1)隨著種子集規(guī)模k的增大，4 種算法的預(yù)期影響范圍總體呈上升趨勢(shì)，且預(yù)期影響范圍的增幅隨種子個(gè)數(shù)的增加而遞減。2)MTIM 的預(yù)期影響范圍最廣，IMM 和TIM 次之，而DegreeDiscount 表現(xiàn)最差。具體而言，MTIM 算法較IMM 算法擴(kuò)大預(yù)期影響范圍約30%，且數(shù)據(jù)集規(guī)模越大，提升效果越明顯；IMM 算法和TIM 算法折線(xiàn)幾乎重合，性能差異不大；而DegreeDiscount 算法的預(yù)期影響范圍約為IMM 算法的50%。

圖8 LT 模型下的預(yù)期影響范圍比較

其原因與IC 模型類(lèi)似，主要是節(jié)點(diǎn)度篩選策略的應(yīng)用。利用該策略，可以提高種子集對(duì)反向可達(dá)集的覆蓋率，從而擴(kuò)大種子集預(yù)期影響范圍。因而，MTIM 算法較IMM 算法擴(kuò)大預(yù)期影響范圍約30%。IMM 算法是TIM 算法的改進(jìn)算法，在確保獲得相同近似保證的同時(shí)，主要研究如何提升算法的運(yùn)行速度。因而，IMM 算法和TIM 算法的預(yù)期影響范圍極為接近。DegreeDiscount 算法是經(jīng)典啟發(fā)式算法，基于折扣度思想來(lái)選擇種子節(jié)點(diǎn)，并未考慮網(wǎng)絡(luò)結(jié)構(gòu)的復(fù)雜性。因而，該算法的預(yù)期影響范圍遠(yuǎn)不如MTIM算法、IMM 算法和TIM 算法。

第二組實(shí)驗(yàn)?；贚T 模型比較了MTIM、IMM、TIM、DegreeDiscount 這4 種算法在不同數(shù)據(jù)集下的運(yùn)行時(shí)間，結(jié)果如圖9 所示。根據(jù)圖9 可以發(fā)現(xiàn)，1)隨著種子集規(guī)模k的增大，DegreeDiscount、MTIM 和IMM 的運(yùn)行時(shí)間遞增，并且增幅逐漸減??；而TIM 在k＜10 時(shí)運(yùn)行時(shí)間遞減，在k≥10 時(shí)運(yùn)行時(shí)間遞增，并且增幅逐漸減小。2)MTIM 運(yùn)行時(shí)間最短，DegreeDiscount 和IMM 次之，TIM 運(yùn)行時(shí)間最長(zhǎng)。具體而言，MTIM 算法略快于DegreeDiscount 算法，MTIM 算法較IMM 算法快了1.5～2.3 倍，而TIM 算法的運(yùn)行時(shí)間為IMM 算法的2 倍多。

圖9 LT 模型下的運(yùn)行時(shí)間比較

其原因與IC 模型類(lèi)似，是因?yàn)檫吔缂s束策略和影響力增量剪枝策略的應(yīng)用。利用這2 個(gè)策略，不僅可以快速確定近似最優(yōu)采樣次數(shù)，提升算法效率，而且可以避免部分種子選擇時(shí)的無(wú)效排序，降低算法時(shí)耗。因而，MTIM 算法優(yōu)于TIM 算法和IMM 算法，略快于DegreeDiscount 啟發(fā)式算法。但是，相比于IC模型，LT 模型下的優(yōu)化效果并不顯著，主要是因?yàn)楣?jié)點(diǎn)信息的傳播方式不同，IC 模型下反映的是單個(gè)用戶(hù)與單個(gè)用戶(hù)之間的影響關(guān)系，而LT 模型下反映的是多個(gè)用戶(hù)與單個(gè)用戶(hù)之間的影響關(guān)系。

綜合2 個(gè)傳播模型下的實(shí)驗(yàn)結(jié)果可知，1)相比于IMM、TIM 和PMC 等貪心算法，以及OneHop和DegreeDiscount 等啟發(fā)式算法，MTIM 算法均獲得最大預(yù)期影響范圍，提供近似保證，且種子集規(guī)模越大，優(yōu)勢(shì)越明顯。2)與IMM、TIM和PMC 等貪心算法相比，MTIM 算法運(yùn)行時(shí)間最短。而與啟發(fā)式算法相比，在IC 模型上，MTIM 算法略慢于OneHop 算法；在LT 模型上，MTIM 算法運(yùn)行速度與DegreeDiscount 算法極為接近，總體略快于DegreeDiscount 算法。3)MTIM 算法不僅預(yù)期影響范圍更優(yōu)、精確度更高，而且運(yùn)行速度優(yōu)于大多貪心算法，略快于部分啟發(fā)式算法。因而，MTIM 算法能夠更好地適用于大規(guī)模社交網(wǎng)絡(luò)。

4 結(jié)束語(yǔ)

針對(duì)現(xiàn)有影響力最大化算法效率低、適用模型單一的問(wèn)題，本文基于2 個(gè)基礎(chǔ)影響力傳播模型，結(jié)合反向影響采樣技術(shù)，提出了MTIM 算法，該算法包括3 個(gè)階段。1)預(yù)處理階段：基于節(jié)點(diǎn)度篩選策略，篩選出有效節(jié)點(diǎn)集。2)采樣階段：基于邊界約束策略，確定近似最優(yōu)采樣次數(shù)并從有效節(jié)點(diǎn)集中選點(diǎn)采樣。3)種子選擇階段：應(yīng)用貪心策略選擇種子節(jié)點(diǎn)，并基于影響力增量剪枝策略，剪枝種子選擇時(shí)的無(wú)效排序?；? 個(gè)真實(shí)社交網(wǎng)絡(luò)的實(shí)驗(yàn)結(jié)果表明，MTIM 算法不僅可以提供近似保證，而且其預(yù)期影響范圍遠(yuǎn)高于DegreeDiscount和OneHop 等啟發(fā)式算法，優(yōu)于IMM、TIM、PMC等貪心算法；在運(yùn)行時(shí)間方面，MTIM 算法顯著快于IMM、TIM、PMC 等貪心算法，總體上略慢于OneHop，略快于DegreeDiscount。因而，MTIM 算法在擁有較快運(yùn)行速度的同時(shí)，保證了較大預(yù)期影響范圍、較高近似保證，能夠更好地適用于大規(guī)模社交網(wǎng)絡(luò)。

后續(xù)工作中將會(huì)進(jìn)行如下深入研究。1)影響力傳播模型的擴(kuò)展。進(jìn)一步考慮特定的、復(fù)雜多變的應(yīng)用場(chǎng)景下，如何解決影響力最大化問(wèn)題。2)動(dòng)態(tài)圖下的研究。實(shí)際情況下，社交網(wǎng)絡(luò)的結(jié)構(gòu)以及用戶(hù)間的關(guān)系往往會(huì)隨著消息的傳播而發(fā)生一定變化，未來(lái)可以嘗試在動(dòng)態(tài)圖上進(jìn)行研究。