關(guān)聯(lián)影響力傳播最大化方法*

張?jiān)骑w，李 勁，岳 昆，羅之皓，劉惟一

1.云南大學(xué) 信息學(xué)院，昆明 650091

2.云南大學(xué) 軟件學(xué)院，昆明 650091

3.云南省軟件工程重點(diǎn)實(shí)驗(yàn)室，昆明 650091

1 引言

針對(duì)目前萬維網(wǎng)環(huán)境下社會(huì)網(wǎng)絡(luò)信息傳播研究中存在的問題，有三個(gè)層面上的問題需要進(jìn)行研究[1]：（1）信息與行為交叉層面，主要關(guān)注多模態(tài)信息主題的用戶偏好模型；（2）網(wǎng)絡(luò)與行為交叉層面，主要研究基于用戶親密度度量的網(wǎng)絡(luò)模型構(gòu)建；（3）信息、行為及網(wǎng)絡(luò)交叉層面，主要揭示主題和網(wǎng)絡(luò)環(huán)境約束下影響力傳播機(jī)制，并最終建立有效、安全的社會(huì)網(wǎng)絡(luò)信息的全局傳播機(jī)制。其中，影響力傳播模型是揭示影響傳播機(jī)制的微觀基礎(chǔ)，而有效、安全的信息傳播機(jī)制是研究的最終目標(biāo)和核心內(nèi)容。

近年來，許多學(xué)者針對(duì)面向多信息源發(fā)布的信息全局傳播機(jī)制及其預(yù)測(cè)模型，以影響力傳播范圍及傳播速度最大化為目標(biāo)的關(guān)鍵結(jié)點(diǎn)集選取等問題開展了積極探索，并取得了一系列成果，極大地促進(jìn)了社會(huì)網(wǎng)絡(luò)影響力傳播機(jī)制問題的研究[2-5]。然而，社會(huì)網(wǎng)絡(luò)中傳播的各種影響力之間不是完全獨(dú)立的：既有影響力傳播之間的對(duì)抗，也會(huì)有一種影響力的傳播促進(jìn)另一種影響力傳播的情況。為有效地分析社會(huì)網(wǎng)絡(luò)中多種影響力傳播機(jī)制，以多種影響力下的社會(huì)網(wǎng)絡(luò)影響力傳播模型，及多影響力傳播模型下的傳播優(yōu)化[6-14]等問題引起了關(guān)注，取得了一些初步的研究成果。

例如，文獻(xiàn)[6]擴(kuò)展經(jīng)典的線性閾值模型（linear threshold model，LT），給出了用于描述社會(huì)網(wǎng)絡(luò)中正、負(fù)影響競(jìng)爭(zhēng)傳播現(xiàn)象的競(jìng)爭(zhēng)線性閾值模型，提出影響力傳播的新問題：影響傳播抑制最大化問題（influence blocking maximization），證明了IBM的目標(biāo)函數(shù)滿足子模性（submodularity），給出了解決IBM問題的高效近似算法。文獻(xiàn)[7]基于影響力傳播的獨(dú)立級(jí)聯(lián)模型（independent cascade model）建立了多競(jìng)爭(zhēng)級(jí)聯(lián)模型（multiple competitive independent cascade model，MCICM），提出影響傳播抑制問題（eventual influence limitation，EIL），給出MCICM模型下，EIL問題目標(biāo)函數(shù)滿足子模性的充分條件，以及EIL問題的近似求解算法。由于影響力傳播與抑制行為的本質(zhì)是傳播方與抑制方之間的一種博弈關(guān)系，文獻(xiàn)[8-9]以傳播方和抑制方的種子集作為策略空間，將傳播與抑制決策建模為零和博弈，并提出了博弈Nash均衡的近似求解算法。最近，文獻(xiàn)[10]針對(duì)社會(huì)網(wǎng)絡(luò)中影響力傳播抑制問題，擴(kuò)展了經(jīng)典的線性閾值模型，提出了一種新型的影響力傳播、抑制模型，并給出了此模型上的影響傳播的最優(yōu)抑制方法。文獻(xiàn)[11]假設(shè)競(jìng)爭(zhēng)網(wǎng)絡(luò)中r個(gè)分組獨(dú)立選擇種子，每個(gè)分組可以感知對(duì)手但不能感知對(duì)手策略，當(dāng)結(jié)點(diǎn)受到一些分組影響時(shí)就不再受其他分組影響。討論了在更符合實(shí)際的假設(shè)下，競(jìng)爭(zhēng)影響傳播最大化問題。

值得注意的是以上研究主要針對(duì)兩種處于競(jìng)爭(zhēng)狀態(tài)下的影響力的對(duì)抗傳播。對(duì)于網(wǎng)絡(luò)中多種影響力傳播時(shí)，存在相互促進(jìn)的情況，以及此情況下的傳播優(yōu)化問題，研究較少。Narayanam等人[12]研究了通過社交網(wǎng)絡(luò)推廣兩組商品，其中一組商品對(duì)另一組商品的傳播有促進(jìn)作用時(shí)，如何選擇兩組商品的種子，使傳播總收益最大。Lu等人[13]通過擴(kuò)展經(jīng)典的獨(dú)立級(jí)聯(lián)模型，提出了Com-IC模型，并討論了Com-IC下影響力之間促進(jìn)和競(jìng)爭(zhēng)傳播的情況。Zarezade等人[14]研究了網(wǎng)絡(luò)中不同的級(jí)聯(lián)傳播行為之間合作或競(jìng)爭(zhēng)關(guān)系，并提出了一種采用Hawkes process隨機(jī)過程對(duì)關(guān)聯(lián)級(jí)聯(lián)過程進(jìn)行建模、分析的方法。

與上述研究工作不同，本文研究：已知網(wǎng)絡(luò)中影響力B的傳播種子集，且影響力A和B之間存在傳播促進(jìn)關(guān)系，對(duì)于影響力A，如何有效地選擇傳播種子集，使得影響力A的傳播范圍最大化?；诖耍疚奶岢鲫P(guān)聯(lián)影響力傳播最大化問題（correlational influence maximization，CIM）。首先，對(duì)經(jīng)典線性閾值模型進(jìn)行擴(kuò)展，提出關(guān)聯(lián)影響力線性閾值模型（correlational linear threshold model，CLT），用CLT模型對(duì)網(wǎng)絡(luò)中關(guān)聯(lián)影響力傳播過程進(jìn)行建模。其次，證明了CIM問題是NP-hard的，并進(jìn)一步證明了該問題的目標(biāo)函數(shù)滿足子模性?；诖?，提出了針對(duì)關(guān)聯(lián)影響力最大化的種子集挖掘算法。此外，為有效提高算法的執(zhí)行效率，提出了基于結(jié)點(diǎn)激活貢獻(xiàn)估計(jì)的最大化算法。由于結(jié)點(diǎn)激活貢獻(xiàn)估計(jì)是相互獨(dú)立的，進(jìn)一步地，提出了并行化的基于結(jié)點(diǎn)激活貢獻(xiàn)估計(jì)的最大化算法。最后，采用Spark GraphX并行圖計(jì)算平臺(tái)實(shí)現(xiàn)了相關(guān)算法，在真實(shí)的社會(huì)網(wǎng)絡(luò)數(shù)據(jù)集上通過實(shí)驗(yàn)驗(yàn)證了所提出的方法的可行性和有效性。

2 關(guān)聯(lián)影響力線性閾值模型

一般地，社會(huì)網(wǎng)絡(luò)中同時(shí)存在多種影響進(jìn)行傳播，這些影響之間可能不是相互獨(dú)立，有些影響力之間在傳播行為上存在相互促進(jìn)的關(guān)系。為描述相互間具有傳播促進(jìn)作用的影響力在社會(huì)網(wǎng)絡(luò)中的傳播情況，本文對(duì)社會(huì)網(wǎng)絡(luò)影響力傳播的經(jīng)典模型線性閾值模型[2]進(jìn)行了擴(kuò)展，提出了一種新型的影響力傳播模型，即關(guān)聯(lián)影響力線性閾值模型。

設(shè)帶權(quán)有向圖G=(V,E)是一個(gè)社會(huì)網(wǎng)絡(luò)，其中V為結(jié)點(diǎn)集，表示網(wǎng)絡(luò)中的個(gè)體，E為有向邊集，表示個(gè)體間的影響關(guān)系，每條邊e(u,v)有相應(yīng)權(quán)重wu,v>0，表示u對(duì)v影響程度。為描述方便，設(shè)A和B為兩種不同的影響力，其中B為A的關(guān)聯(lián)影響，且對(duì)A有促進(jìn)作用，作為對(duì)LT的擴(kuò)展。設(shè)每條邊有3個(gè)權(quán)值：表示網(wǎng)中只有A在傳播時(shí)，u對(duì)v影響力度；表示網(wǎng)中B傳播時(shí)，u對(duì)v影響力度；表示當(dāng)v被B激活時(shí)u對(duì)v影響力度。當(dāng)時(shí)，說明如果結(jié)點(diǎn)v被B激活后，u對(duì)v的A激活影響程度增強(qiáng)，那么說影響力B對(duì)影響力A有傳播促進(jìn)作用。

一般地，結(jié)點(diǎn)v獨(dú)立地從[0,1]中等概率選取激活閾值。與經(jīng)典的LT模型類似，在時(shí)刻t，記INA(v)、INB(v)分別為v處于A、B激活態(tài)的入鄰居結(jié)點(diǎn)集。當(dāng)，且時(shí)，v被A激活；如果v已被B激活，INA(v)≠? 且時(shí)，v被A激活。顯然，當(dāng)成立時(shí)，網(wǎng)絡(luò)中結(jié)點(diǎn)被A激活的概率提高。因此，網(wǎng)絡(luò)中同時(shí)有A、B在傳播時(shí)，A影響范圍的期望值將增大。

可以發(fā)現(xiàn)邊e(u,v)的屬性wu,v是反映u、v間影響程度重要的量。下面給出wu,v的一種衡量方法。先從網(wǎng)絡(luò)結(jié)構(gòu)角度給出相鄰結(jié)點(diǎn)間緊密度的衡量方法。

設(shè)網(wǎng)絡(luò)G=(V,E)中，。那么，用衡量u對(duì)v的緊密度。注意到，。其中 |N(v)?N(u)|表示結(jié)點(diǎn)u與v共同鄰居的數(shù)量，加1表示u與v是一對(duì)鄰居，同時(shí)也保證了λu,v的合理性。

相鄰結(jié)點(diǎn)間傳遞信息時(shí)，其影響程度除了與結(jié)點(diǎn)間的緊密度有關(guān)外，還與信息本身是否容易被接受有關(guān)。下面從商品信息的角度，給出商品信息接受率的衡量方法。

假定A商品的交易數(shù)為mA，B商品的交易數(shù)為mB，同時(shí)購買A和B的交易數(shù)mAB，商品的總交易數(shù)為n。記A商品信息的接受率pA|?=mAn，B商品信息的接受率pB=mBn，接受B后A的接受率pA|B=mABmB。商品信息的接受率體現(xiàn)商品信息的平均接受程度。

根據(jù)結(jié)點(diǎn)間的緊密度及商品接受率的概念，給出wu,v的一種計(jì)算方法。設(shè)u∈IN(v)，當(dāng)v未被B激活時(shí)，；當(dāng)u被B激活時(shí)，pA|B。如果pA|B>pA|?，在有B傳播的情況下，就可能增大結(jié)點(diǎn)被A激活的概率，擴(kuò)大A的傳播范圍。

下面通過一個(gè)例子來說明CLT模型在某確定圖上關(guān)聯(lián)影響力的傳播過程，如圖1、圖2所示。

Fig.1 Example of influence diffusion under LT model圖1 LT模型影響力傳播示例

Fig.2 Example of influence diffusion under CLT model圖2 CLT模型影響力傳播示例

如圖1所示，設(shè)v1是A影響種子結(jié)點(diǎn)。A影響按照LT模型進(jìn)行傳播，t=3時(shí)，圖中被A激活的結(jié)點(diǎn)為{v1,v3,v4}。圖2中，t=0時(shí)，v1被A激活，{v2,v3,v4,v5}最終被B激活。假定對(duì)于任意結(jié)點(diǎn)，均有影響力按照CLT模型進(jìn)行傳播。在t=3時(shí)，與圖1所示結(jié)果不同，網(wǎng)絡(luò)中所有結(jié)點(diǎn)均A激活，即B影響力對(duì)A影響力的傳播起到了促進(jìn)作用。

于是，基于CLT模型，本文提出一個(gè)新的社會(huì)網(wǎng)絡(luò)影響力傳播優(yōu)化問題，即：CLT下的關(guān)聯(lián)影響力傳播最大化問題。具體地，令G=(V,E)是一個(gè)帶權(quán)有向圖，表示社會(huì)網(wǎng)絡(luò)。分別表示CLT模型中結(jié)點(diǎn)集V上的A、B兩種影響閾值隨機(jī)向量。當(dāng)θA與θB取某具體值時(shí)，得到確定圖g，所有確定圖組成隨機(jī)網(wǎng)絡(luò)集G，g∈G。設(shè)A、B影響力的種子集分別記為SA、SB，兩種影響力按照CLT模型在G中進(jìn)行傳播。最終，被A激活的結(jié)點(diǎn)集記為：。由于θA和θB是隨機(jī)向量，因此是一個(gè)隨機(jī)變量。用該隨機(jī)變量的期望值作為A影響力的傳播效用，記為：

于是，關(guān)聯(lián)影響力傳播最大化問題可定義為：

定義1（最大化問題的定義）設(shè)A、B影響力按照CLT進(jìn)行影響力傳播。給定B影響種子集SB的情況下，求解A影響傳播效用最大化的種子集SA，使得：

定理1（最大化問題的復(fù)雜性）關(guān)聯(lián)影響力傳播最大化問題是NP-hard的。

證明在CLT模型中，當(dāng)SB=? 時(shí)，CLT模型退化為經(jīng)典的LT模型。因此，LT是CLT的一個(gè)特例。Kempe等人[2]證明了LT模型的影響力最大化問題是NP-hard問題，因此，式（1）描述的CLT的影響力最大化問題也是NP-hard的。

定理2（效用函數(shù)的性質(zhì)）在CLT中，給定SB的條件下，A影響傳播效用函數(shù)inf(SA,SB)是關(guān)于SA的非負(fù)、單調(diào)、子模函數(shù)。

下面證明在CLT中，給定SB的情況下，A影響力傳播效用函數(shù)inf(SA,SB)是子模函數(shù)。

證明由CLT中影響力傳播過程可知，在確定圖g中，由種子集SB可以確定B的傳播范圍。任意結(jié)點(diǎn)v是否處于B激活態(tài)將影響其入邊傳播的A影響權(quán)重，進(jìn)而影響v被A激活的可能性。因此，可先給定SB，獨(dú)立進(jìn)行B影響力傳播，然后再進(jìn)行A影響力傳播。任意結(jié)點(diǎn)v及其入邊A激活結(jié)點(diǎn)u∈INA(v)，將u對(duì)v的影響權(quán)重記為wu,v。那么，如果當(dāng)前v未被B激活，則u對(duì)v的傳播影響權(quán)重設(shè)為。如果當(dāng)前v已被B激活，同時(shí)，則u對(duì)v的影響權(quán)重設(shè)為。此時(shí)，從SA出發(fā)，A影響力將按照LT模型進(jìn)行傳播，最終得到A的傳播范圍。在所有的網(wǎng)絡(luò)集G中得到inf(SA,SB)。由于Kempe等人證明了LT下影響力傳播效用函數(shù)是子模的[2]，因此在CLT下，關(guān)聯(lián)影響力傳播效用函數(shù)inf(SA,SB)也是關(guān)于SA的子模函數(shù)。

3 關(guān)聯(lián)影響力最大化算法

本章給出求解關(guān)聯(lián)影響力最大化問題的算法。由于B的傳播也是隨機(jī)事件，首先給出能保證種子傳播效果的基于貪心策略的最大化算法。其次，為提高算法效率提出了基于結(jié)點(diǎn)激活貢獻(xiàn)估計(jì)的最大化算法。鑒于不同結(jié)點(diǎn)的激活貢獻(xiàn)值相互獨(dú)立，進(jìn)一步提出基于圖計(jì)算框架Spark GraphX[15]的并行最大化算法。

3.1 基于貪心策略的關(guān)聯(lián)影響力傳播最大化算法

由定義1及定理2可知，求解SA可歸結(jié)為一個(gè)子模函數(shù)優(yōu)化問題。于是，給定種子集SB的情況下，以inf(SA,SB)作為子模目標(biāo)函數(shù)，以結(jié)點(diǎn)對(duì)于當(dāng)前解的期望邊際傳播收益作為貪心選擇標(biāo)準(zhǔn)，由子模函數(shù)優(yōu)化理論[16]可知，用貪心法可得(1-1e)-近似解。由于CLT是一個(gè)隨機(jī)模型，因此算法先隨機(jī)生成激活閾值向量θA、θB，每一對(duì)閾值向量確定一個(gè)網(wǎng)絡(luò)g。結(jié)點(diǎn)的期望邊際傳播收益由結(jié)點(diǎn)對(duì)于當(dāng)前解在隨機(jī)網(wǎng)絡(luò)集G上的期望值來決定。給定g，算法以SB作為種子集按照LT模型進(jìn)行B影響力傳播，確定g中被B激活的結(jié)點(diǎn)。如果，則將置為v的入邊A影響權(quán)重，并根據(jù)LT模型對(duì)g上每個(gè)結(jié)點(diǎn)的A影響傳播效用進(jìn)行估計(jì)，進(jìn)而確定邊際傳播收益值。最終，算法根據(jù)結(jié)點(diǎn)當(dāng)前解的期望邊際傳播收益選擇值最大的新結(jié)點(diǎn)加入到SA。

算法1Greedy(G,SB,k)

輸入：網(wǎng)絡(luò)G(V,E),B影響種子集SB,A影響種子集大小k。

輸出：A影響種子集SA。

3.2 基于結(jié)點(diǎn)激活貢獻(xiàn)估計(jì)的關(guān)聯(lián)影響力傳播最大化算法

為提高算法效率，本文提出一種基于結(jié)點(diǎn)激活貢獻(xiàn)估計(jì)的影響最大化算法。其中結(jié)點(diǎn)激活貢獻(xiàn)值估計(jì)是該算法計(jì)算密集環(huán)節(jié)。由于不同結(jié)點(diǎn)的激活貢獻(xiàn)估計(jì)是相互獨(dú)立的，可進(jìn)行并行計(jì)算，進(jìn)一步提出基于圖計(jì)算框架Spark GraphX[15]的并行最大化算法。

3.2.1 結(jié)點(diǎn)激活貢獻(xiàn)的估計(jì)方法

先定義結(jié)點(diǎn)的入邊對(duì)結(jié)點(diǎn)激活的貢獻(xiàn)值。

定義2（邊的激活貢獻(xiàn)）設(shè)v是確定圖g中的任意處于未激活態(tài)的結(jié)點(diǎn)。IN(v)是v的處于激活態(tài)的入鄰居結(jié)點(diǎn)集。設(shè)u是v的任意處于未激活態(tài)的入結(jié)點(diǎn)。則結(jié)點(diǎn)u通過邊e(u,v)對(duì)v的激活貢獻(xiàn)值記為AC(u,v)∈[0,1]，并定義如下：

注意到，定義2中v是未激活結(jié)點(diǎn)，定義中總有，否則v應(yīng)處于激活態(tài)。此外，如果u被激活后，可由入邊e(u,v)直接激活v，由式（2）可知，此時(shí)AC(u,v)=1。

進(jìn)一步地，可以基于邊的激活貢獻(xiàn)來定義結(jié)點(diǎn)的激活貢獻(xiàn)。具體地，對(duì)于結(jié)點(diǎn)u∈V，可由該結(jié)點(diǎn)所有出邊的激活貢獻(xiàn)值之和來定義u的激活貢獻(xiàn)值。同時(shí)，考慮任意結(jié)點(diǎn)u對(duì)其l-步鄰居的激活影響，可定義結(jié)點(diǎn)的l-步激活貢獻(xiàn)，記為ACl(u)，定義如下：

定義3（結(jié)點(diǎn)的激活貢獻(xiàn)）令OUT(v)是結(jié)點(diǎn)v的出邊鄰居集。記v的l-步激活貢獻(xiàn)值為ACl(v)(l≥2)，計(jì)算公式如下：

其中，當(dāng)l=1時(shí)，結(jié)點(diǎn)v對(duì)其1-步鄰居的潛在貢獻(xiàn)值為：。直觀地，AC1(v)反映了結(jié)點(diǎn)v從未激活轉(zhuǎn)換為激活狀態(tài)時(shí)，對(duì)其1-步鄰居結(jié)點(diǎn)的影響。

下面，舉例說明CLT模型中，結(jié)點(diǎn)激活貢獻(xiàn)值的估計(jì)方法。

圖3中已處于A激活態(tài)的結(jié)點(diǎn)為{v1,v2}，已處于B激活態(tài)的結(jié)點(diǎn)為{v5,v6}。任意有向邊e(u,v)的權(quán)重表示結(jié)點(diǎn)間的A影響權(quán)重。此外，設(shè)，。針對(duì)未激活結(jié)點(diǎn)v3，計(jì)算其激活貢獻(xiàn)值以及。

Fig.3 Example of estimation of activation contributions of vertices under CLT model圖3 CLT中結(jié)點(diǎn)激活貢獻(xiàn)值估計(jì)示例

首先，由定義2可知，有向邊e(3,4)對(duì)v4的激活貢獻(xiàn)為，得AC(3,4)=1，說明v4一定會(huì)被激活。類似地，得到AC(3,5)=。進(jìn)一步，由定義3得到AC1(v3)=1.25。同理，得AC(4 ,5)=0.625，AC1(v4)=0.625，AC1(v5)=0。因此，由定義3得到。

3.2.2 基于結(jié)點(diǎn)激活貢獻(xiàn)估計(jì)的影響最大化算法

基于結(jié)點(diǎn)激活貢獻(xiàn)估計(jì)的影響最大化算法（activation contribution based algorithm，ACA）的基本流程與算法1類似，時(shí)間復(fù)雜度為，其中D為以結(jié)點(diǎn)為中心l步的平均邊數(shù)，顯然D?R。ACA與Greedy最大的區(qū)別在于，在ACA中，用結(jié)點(diǎn)的激活貢獻(xiàn)估計(jì)值A(chǔ)Cl(v)取代了算法1中結(jié)點(diǎn)的邊際效用估計(jì)。因此與Greedy相比，ACA的算法效率得到了很大提高。

此外，需要說明的是，當(dāng)結(jié)點(diǎn)激活貢獻(xiàn)估計(jì)的步長(zhǎng)l=1時(shí)，ACA算法其實(shí)是陳等人提出的基于閾值的啟發(fā)式影響力最大化算法（threshold-based heuristic algorithm for influence maximization，TBH）[5]針對(duì)CLT模型的擴(kuò)展。由文獻(xiàn)[5]結(jié)論可知，TBH算法證明選出種子集在傳播效果上接近Kempe[2]的貪心算法。

算法2ACA(G,SB,k,l)

輸入：網(wǎng)絡(luò)G(V,E),B影響種子集SB，A影響種子集大小k，激活貢獻(xiàn)值步長(zhǎng)l。

輸出：A影響種子集SA。

Fig.4 Example ofACAalgorithm execution圖4 ACA算法執(zhí)行示例

下面給出一個(gè)ACA算法執(zhí)行的示例。如圖4，開始時(shí)v1、v2均未被A激活，此時(shí)選取種子。根據(jù)定義3可得AC2(v1)=0.347，AC2(v2)=1.251，AC2(v3)=0.458，AC2(v4)=0.278，AC2(v5)=0，AC2(v6)=0.111。因此，選取激活貢獻(xiàn)值最大的結(jié)點(diǎn)v2作為種子。接下來，v2變?yōu)锳激活結(jié)點(diǎn)，v5、v6為B激活結(jié)點(diǎn)。由于v2對(duì)v4、v5的影響，當(dāng)v2被A激活后，其指向v4、v5的有向邊的激活貢獻(xiàn)發(fā)生改變。于是重新計(jì)算這些邊和未激活結(jié)點(diǎn)的激活貢獻(xiàn)，可得：AC2(v1)=0.875，AC2(v3)=0.934，AC2(v4)2=0.192，AC2(v5)=0，AC2(v6)=0.077。此時(shí)，選擇最大激活貢獻(xiàn)值的v3作為種子。由此，得到的兩個(gè)種子為{v2,v3}。

在ACA算法中，結(jié)點(diǎn)激活貢獻(xiàn)估計(jì)是整個(gè)算法的計(jì)算密集環(huán)節(jié)。注意到各個(gè)結(jié)點(diǎn)的激活貢獻(xiàn)的估計(jì)實(shí)際上是相互獨(dú)立的，允許進(jìn)行并行計(jì)算。因此，進(jìn)一步提出了基于并行圖計(jì)算框架Spark GraphX[15]的并行化ACA算法（parallel activation contribution based algorithm，PACA）。

PACA采用并行消息機(jī)制實(shí)現(xiàn)邊和結(jié)點(diǎn)激活貢獻(xiàn)值的計(jì)算，極大地提高了算法的執(zhí)行效率。在計(jì)算結(jié)點(diǎn)多步激活貢獻(xiàn)值時(shí)，可通過在圖上采用多次迭代實(shí)現(xiàn)。具體地，設(shè)u的出鄰居為v，首先計(jì)算u和v的1-步激活貢獻(xiàn)，通過GraphX中結(jié)點(diǎn)間的消息傳遞機(jī)制，將v的1-步激活貢獻(xiàn)發(fā)送給u。此時(shí)，u可以計(jì)算其2-步激活貢獻(xiàn)。算法3為PACA算法的描述。

算法3PACA(G,SB,k,n)

輸入：G(V,E)，圖G;SB，B信息種子集；k，待求A信息種子數(shù)；n，考慮n步鄰居。

輸出：SA，A信息種子集。

4 實(shí)驗(yàn)結(jié)果

4.1 實(shí)驗(yàn)環(huán)境設(shè)置

在3個(gè)真實(shí)的網(wǎng)絡(luò)數(shù)據(jù)集[17]HepTh、Web-Stan和Pokec上對(duì)本文提出的模型和算法進(jìn)行測(cè)試和驗(yàn)證。表1給出了實(shí)驗(yàn)數(shù)據(jù)集的具體信息。HepTh是電子出版物arXiv出版的高能物理領(lǐng)域論文間的引用關(guān)系網(wǎng)；Web-Stan是斯坦福大學(xué)網(wǎng)頁間的鏈接關(guān)系數(shù)據(jù)；Pokec是Pokec社交網(wǎng)絡(luò)數(shù)據(jù)。Market是超市購物數(shù)據(jù)集[18]，實(shí)驗(yàn)中傳播的超市Peanuts商品信息設(shè)為A，Beer為其關(guān)聯(lián)商品信息設(shè)為B。根據(jù)第2章方法得到pA|?=0.186 38，pA|B=0.570 96。針對(duì)以上數(shù)據(jù)集，在Spark平臺(tái)上，采用Scala語言實(shí)現(xiàn)相關(guān)算法。程序執(zhí)行環(huán)境為：浪潮服務(wù)器，共有40個(gè)Cores，每個(gè)Core的主頻為2.2 GHz，服務(wù)器的內(nèi)存為750 GB。

Table 1 Statistics of experimental data sets表1 實(shí)驗(yàn)數(shù)據(jù)集的統(tǒng)計(jì)信息

4.2 關(guān)聯(lián)影響傳播的有效性

首先對(duì)關(guān)聯(lián)影響傳播模型的有效性進(jìn)行驗(yàn)證，即比較不給定B影響源、給定B影響源兩種不同情況下，A影響力傳播的范圍。實(shí)驗(yàn)方案是：在3個(gè)網(wǎng)絡(luò)中，按結(jié)點(diǎn)度數(shù)排序，選取最大度的前10個(gè)結(jié)點(diǎn)作為B影響種子集。首先，不預(yù)先給定B影響源信息，用貪心算法[2]分別選取大小分別為4、8、12、16、20的A影響種子集，影響力按照經(jīng)典的LT模型傳播。其次給定B影響源信息，按照本文提出的的算法1選取大小分別為4、8、12、16、20的A影響種子集，影響力按照本文CLT模型傳播。其中|G |的個(gè)數(shù)取2 000。最終，在不考慮關(guān)聯(lián)影響與考慮關(guān)聯(lián)影響兩種情況下選出種子A影響力傳播范圍的實(shí)驗(yàn)結(jié)果如圖5～圖7所示。

由實(shí)驗(yàn)結(jié)果可知，相比較LT模型下A影響力的傳播結(jié)果，考慮B影響源，選取同樣大小的種子集在CLT模型下被A激活的結(jié)點(diǎn)更多。這說明借助關(guān)聯(lián)影響源B，可使得A影響力得到更好的傳播。這一事實(shí)在HepTh和Pokec實(shí)驗(yàn)結(jié)果得以充分體現(xiàn)。在Web-Stan網(wǎng)絡(luò)數(shù)據(jù)中，選取12個(gè)以上種子時(shí)，借助關(guān)聯(lián)影響源選擇種子，顯然傳播能力更強(qiáng)。

4.3 PACA算法

Fig.6 Range of information propagation under LT and CLT(Web)圖6 LT與CLT傳播范圍對(duì)比（Web）

Fig.7 Range of information propagation under LT and CLT(Pokec)圖7 LT與CLT傳播范圍對(duì)比（Pokec）

本節(jié)從種子集選取效果、鄰居選擇策略以及并行加速比三方面對(duì)本文提出的PACA算法進(jìn)行驗(yàn)證。

4.3.1 不同算法的傳播效果

在3個(gè)網(wǎng)絡(luò)數(shù)據(jù)集HepTh、Web-Stan和Pokec上，對(duì)PACA-1、PACA-2、PACA-3、MaxDegree、Random 5種算法的種子集選取效果進(jìn)行了比較。其中，PACA-l為采用l步長(zhǎng)進(jìn)行結(jié)點(diǎn)激活貢獻(xiàn)估計(jì)的PACA算法。由于PACA-1可看作文獻(xiàn)[5]提出的TBH算法針對(duì)CLT模型擴(kuò)展的并行實(shí)現(xiàn)，由文獻(xiàn)[5]結(jié)果可知，TBH算法與Greedy算法選出的種子集具有相當(dāng)?shù)膫鞑バЧ襎BH算法效率很高。因此，在對(duì)比實(shí)驗(yàn)中省去了同Greedy算法的對(duì)比。

實(shí)驗(yàn)選擇度最大的10個(gè)結(jié)點(diǎn)作為B種子集，關(guān)注A種子集的選取。每種算法選擇4、8、12、16、20個(gè)A的種子，在G中，以最終被A激活結(jié)點(diǎn)數(shù)的平均值作為傳播效果的指標(biāo)，分析算法種子集選取的優(yōu)劣。實(shí)驗(yàn)結(jié)果如圖8～圖10所示。

Fig.8 Propagation ability of seed sets selected by different algorithms(HepTh)圖8 不同算法的傳播范圍對(duì)比（HepTh）

Fig.9 Propagation ability of seed sets selected by different algorithms(Web)圖9 不同算法的傳播范圍對(duì)比（Web）

Fig.10 Propagation ability of seed sets selected by different algorithms(Pokec)圖10 不同算法的傳播范圍對(duì)比（Pokec）

由實(shí)驗(yàn)結(jié)果可知，PACA系列算法選取種子傳播效果較好，明顯優(yōu)于MaxDegree與Random算法。利用PACA-2選取種子在大多數(shù)時(shí)候得到的種子集要優(yōu)于PACA-1，甚至?xí)?yōu)于PACA-3。而PACA-3考慮了網(wǎng)絡(luò)中的更多信息，但選出種子集的傳播效果卻不穩(wěn)定。如在Pokec中選取16與20個(gè)種子時(shí)，其選出種子的效果甚至低于PACA-1。導(dǎo)致這一結(jié)果的原因是進(jìn)行激活貢獻(xiàn)估計(jì)的步長(zhǎng)越長(zhǎng)，結(jié)點(diǎn)間的關(guān)系越復(fù)雜，反而使估算效果時(shí)好時(shí)壞。

4.3.2 PACA算法的執(zhí)行效率

實(shí)驗(yàn)?zāi)康闹饕菍?duì)比串行的ACA和并行的PACA兩種算法的執(zhí)行時(shí)間。對(duì)ACA與PACA選取4、8、12、16、20個(gè)A的種子，對(duì)比選出種子耗費(fèi)的時(shí)間。兩種算法在進(jìn)行激活貢獻(xiàn)估計(jì)時(shí)，均考慮了估計(jì)步長(zhǎng)l=1,2,3這3種情況。PACA算法采用40核并行執(zhí)行。實(shí)驗(yàn)結(jié)果如圖11～圖13所示。

Fig.11 Execution time ofACAand PACAalgorithms(HepTh)圖11 ACA與PACA執(zhí)行時(shí)間比較（HepTh）

由實(shí)驗(yàn)結(jié)果知，PACA算法效率明顯優(yōu)于ACA算法。網(wǎng)絡(luò)規(guī)模越大，采用并行算法執(zhí)行效率優(yōu)勢(shì)更加明顯。

4.3.3 并行算法的并行加速比

在并行核數(shù)分別為1、8、16、24、32、40時(shí)，利用PACA算法選出20個(gè)種子耗費(fèi)的時(shí)間計(jì)算出并行的加速比與并行效率。實(shí)驗(yàn)結(jié)果如圖14、圖15所示。

加速比Sp用于表示利用并行與對(duì)應(yīng)的單核執(zhí)行算法比較，速度快了多少，計(jì)算公式為Sp=T1/Tp。其中，p為并行的CPU核數(shù)，T1為單核執(zhí)行算法的時(shí)間，Tp為當(dāng)有p個(gè)處理器時(shí)，并行算法的執(zhí)行時(shí)間。由圖14所示可知，并行核數(shù)增加時(shí)，加速比增加，但加速比增加的速率在減小。此外，并行效率用來說明當(dāng)并行核數(shù)增加時(shí)，相比通信和同步上的花費(fèi)，實(shí)際參與計(jì)算的處理器的利用程度，其計(jì)算公式為Ep=Sp/p。

Fig.12 Execution time ofACAand PACAalgorithms(Web)圖12 ACA與PACA執(zhí)行時(shí)間比較（Web）

Fig.13 Execution time ofACAand PACAalgorithms(Pokec)圖13 ACA與PACA執(zhí)行時(shí)間比較（Pokec）

Fig.14 Parallel speed-up ratio of PACA圖14 PACA算法的并行加速比比較

Fig.15 Parallel efficiency of PACA圖15 PACA算法的并行效率比較

對(duì)比3個(gè)數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果，可以發(fā)現(xiàn)處理較大規(guī)模的網(wǎng)絡(luò)時(shí)，并行的加速效果更顯著。當(dāng)并行數(shù)增加到一定程度后，并行所帶來的效率提升就將變得不明顯。

5 總結(jié)與展望

影響力傳播的建模和分析及其控制是當(dāng)前社會(huì)網(wǎng)絡(luò)研究的重要內(nèi)容。針對(duì)多個(gè)影響力同時(shí)進(jìn)行傳播，且影響力間存在傳播促進(jìn)的情況，提出關(guān)聯(lián)影響力傳播最大化問題，并給出了相應(yīng)的種子集挖掘算法。在實(shí)際社會(huì)網(wǎng)絡(luò)數(shù)據(jù)集上驗(yàn)證了算法，實(shí)驗(yàn)結(jié)果表明本文提出方法的有效性。

在本文研究的基礎(chǔ)上，未來可以在以下幾個(gè)方面繼續(xù)開展研究。本文給出的關(guān)聯(lián)影響力傳播模型，主要針對(duì)一方傳播促進(jìn)另一方的情況。但是現(xiàn)實(shí)網(wǎng)絡(luò)中存在關(guān)聯(lián)影響力兩者之間互相促進(jìn)的傳播情況。該情況下，傳播的收益函數(shù)是非子模的，無法保證貪心算法的近似度。因此，討論該情況下傳播模型的性質(zhì)，給出有效的種子選擇算法，成為亟待解決的問題。此外，PACA算法中激活貢獻(xiàn)估算時(shí)的步長(zhǎng)設(shè)置并非越大越好。如何針對(duì)網(wǎng)絡(luò)結(jié)構(gòu)設(shè)置合適的估算步長(zhǎng)，從而有效地提升種子集搜索的質(zhì)量也是需要進(jìn)一步討論的問題。