社會(huì)網(wǎng)中基于主題興趣的影響最大化算法

劉 勇 謝勝男 仲志偉 李金寶 任倩倩

(黑龍江大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院 哈爾濱 150080) (黑龍江省數(shù)據(jù)庫(kù)與并行計(jì)算重點(diǎn)實(shí)驗(yàn)室(黑龍江大學(xué)) 哈爾濱 150080) (acliuyong@sina.com)

近年來，隨著社交應(yīng)用的普及，人們信息獲取的方式發(fā)生了很大的改變.通過在線社交網(wǎng)絡(luò)轉(zhuǎn)發(fā)和分享消息逐漸成為了人們獲取信息的主要方式.很多在線社交網(wǎng)站允許用戶對(duì)信息進(jìn)行轉(zhuǎn)發(fā)、評(píng)論、標(biāo)記或其他一些類似的操作.如果能充分挖掘社交網(wǎng)絡(luò)中這些海量數(shù)據(jù)并發(fā)現(xiàn)傳播規(guī)律，將促進(jìn)新思想、新產(chǎn)品在社交網(wǎng)上快速傳播.

為了利用社交網(wǎng)進(jìn)行病毒式營(yíng)銷， Kempe等人[1]首次提出了影響最大化問題：選取一個(gè)大小為k的初始用戶集合，使得在給定傳播模型下最終被影響的用戶數(shù)量最大.文獻(xiàn)[1]同時(shí)在獨(dú)立級(jí)聯(lián)(independent cascade, IC)模型和線性閾值(linear threshold, LT)模型上給出了貪心算法.此后，影響最大化及其相關(guān)問題被廣泛研究.一方面，為了擴(kuò)展到大規(guī)模社交網(wǎng)絡(luò)上，經(jīng)典傳播模型上高效地影響最大化算法[2-5]相繼被提出；另一方面，為了更準(zhǔn)確地模擬信息傳播過程，一些新的傳播模型[6-8]相繼被提出.

現(xiàn)有的傳播模型幾乎都是利用朋友之間的影響來模擬傳播過程.例如：基于主題的獨(dú)立級(jí)聯(lián)(topic-aware independent cascade, TIC)模型[6]利用傳播項(xiàng)的主題分布和用戶在不同主題上的影響程度來計(jì)算朋友之間的影響概率.然而，在現(xiàn)實(shí)生活中，我們發(fā)現(xiàn)這樣一個(gè)現(xiàn)象：相對(duì)于朋友之間的影響，人們更容易被其感興趣的信息所吸引.例如：用戶使用新浪微博轉(zhuǎn)發(fā)好友發(fā)布的內(nèi)容時(shí)，用戶更多的是被內(nèi)容本身所吸引，被好友影響的可能性相對(duì)較小.即使一個(gè)不經(jīng)常聯(lián)系的好友發(fā)布了令用戶感興趣的內(nèi)容時(shí)，用戶也有很大可能性轉(zhuǎn)發(fā)該內(nèi)容.

根據(jù)上述分析，在求解社會(huì)網(wǎng)中的影響最大化問題時(shí)理應(yīng)考慮用戶對(duì)傳播項(xiàng)的興趣.使用用戶的興趣分布和傳播項(xiàng)的主題分布建立傳播模型，可以更精確地描述信息傳播過程，得到更準(zhǔn)確的預(yù)測(cè)結(jié)果，具有重要的理論意義和廣泛的應(yīng)用價(jià)值.

本文利用用戶興趣的主題分布和傳播項(xiàng)的主題分布，在傳統(tǒng)獨(dú)立級(jí)聯(lián)模型的基礎(chǔ)上，提出了基于主題-興趣的獨(dú)立級(jí)聯(lián)傳播(topic-interest independent cascade, TI-IC)模型，并在該模型的基礎(chǔ)上設(shè)計(jì)了基于主題興趣的影響最大化算法ACG-TIIM.通過在2個(gè)真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明：TI-IC模型在均方根誤差MSE，F(xiàn)1-score，ROC曲線下面積等多個(gè)指標(biāo)上均優(yōu)于傳統(tǒng)的IC模型和TIC模型.ACG-TIIM算法可以得到和傳統(tǒng)貪心算法幾乎一樣的種集，但比傳統(tǒng)貪心算法快2個(gè)數(shù)量級(jí)以上.本文主要貢獻(xiàn)有4個(gè)方面：

1) 提出了基于主題興趣的傳播模型TI-IC，并使用期望最大化(expectation maximization, EM)算法學(xué)習(xí)該模型的參數(shù).

2) 提出了新傳播項(xiàng)主題分布向量的學(xué)習(xí)算法.

3) 在TI-IC基礎(chǔ)上，提出了基于主題興趣的影響最大化問題(topic-interest based influence maxi-mization, TIIM)，并給出了高效啟發(fā)式算法ACG-TIIM.ACG-TIIM算法也可用于求解其他傳播模型上的影響最大化問題.

4) 多個(gè)真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，TI-IC模型比IC模型和TIC模型能更準(zhǔn)確地描述信息傳播規(guī)律， ACG-TIIM算法可高效求解影響最大化問題.

1 相關(guān)工作

Domingos等人[9]最先考慮社會(huì)網(wǎng)中具有影響力的結(jié)點(diǎn)選擇問題.2003年，Kempe等人[1]首次提出了影響最大化問題，證明了影響最大化問題在獨(dú)立級(jí)聯(lián)模型和線性閾值模型上都為NP-hard問題，并且設(shè)計(jì)出具有(1-1/e)近似比的貪心算法.貪心算法雖然簡(jiǎn)單，但是由于在每次迭代選擇種子結(jié)點(diǎn)的過程中都需要進(jìn)行大量的蒙特卡洛模擬來估計(jì)影響范圍，導(dǎo)致貪心算法的效率較低.為了擴(kuò)展到大規(guī)模社交網(wǎng)絡(luò)上，很多高效的影響最大化算法[2-5]被提出.例如Li等人[5]提出了在線廣告的實(shí)時(shí)影響最大化問題，對(duì)于一個(gè)給定關(guān)鍵字的廣告，在線尋找k個(gè)結(jié)點(diǎn)的種集，利用反向可達(dá)集的概念設(shè)計(jì)了一個(gè)基于采樣的算法，不僅有近似比保證，也提升了算法的效率.

任何影響最大化算法都依賴于特定的傳播模型.社交網(wǎng)傳播模型大致可以分為帶有拓?fù)浣Y(jié)構(gòu)的傳播模型和無拓?fù)浣Y(jié)的傳播模型兩大類.

帶有拓?fù)浣Y(jié)構(gòu)的傳播模型將社交網(wǎng)拓?fù)浣Y(jié)構(gòu)看作前置條件，要求信息沿著邊進(jìn)行傳播.經(jīng)典的IC模型和LT模型均屬于此類模型.Barbieri等人[6]擴(kuò)展了傳統(tǒng)IC模型，提出了主題感知的獨(dú)立級(jí)聯(lián)模型TIC.Aslay等人[10]在該模型的基礎(chǔ)上，提出了基于主題的影響最大化問題，設(shè)計(jì)了一個(gè)樹形框架，利用索引來減少新傳播項(xiàng)的計(jì)算量，使得算法效率得到很大提升.Chen等人[11]估計(jì)每個(gè)用戶的影響上界，利用該上界對(duì)影響力小的用戶進(jìn)行剪枝，并設(shè)計(jì)了高效的計(jì)算上界方法.文獻(xiàn)[12]考慮了時(shí)間因素的影響，在IC模型和LT模型基礎(chǔ)上提出了AsIC和AsLT模型.文獻(xiàn)[13]通過分析傳播內(nèi)容來構(gòu)造傳播模型.文獻(xiàn) [14]考慮內(nèi)在因素和外在因素的作用來模擬傳播過程.文獻(xiàn)[7]同時(shí)考慮外部影響、朋友影響和用戶興趣的聯(lián)合作用利用隨機(jī)過程構(gòu)建傳播模型CMPP.文獻(xiàn)[8]考慮結(jié)點(diǎn)和結(jié)點(diǎn)之間的交互作用，在IC模型基礎(chǔ)上提出了情感交互模型OI.

無拓?fù)浣Y(jié)構(gòu)的傳播模型假定社交網(wǎng)拓?fù)浣Y(jié)構(gòu)無法獲取，只根據(jù)觀察到的事件序列來推斷傳播軌跡，預(yù)測(cè)傳播趨勢(shì).文獻(xiàn)[15]推斷用戶之間的信息傳播速率，使得觀察事件序列出現(xiàn)概率最大.文獻(xiàn)[16]根據(jù)觀測(cè)的事件序列來推斷信息傳播路徑和網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，通過追蹤新聞?wù)军c(diǎn)之間的新聞流通路徑驗(yàn)證算法有效性.文獻(xiàn)[17]將用戶映射到一個(gè)連續(xù)隱藏空間中，根據(jù)與感染源的距離遠(yuǎn)近來計(jì)算每個(gè)用戶被感染的概率.通過從觀察到的事件序列中學(xué)習(xí)傳播核函數(shù)來預(yù)測(cè)信息傳播.文獻(xiàn)[18]使用表示學(xué)習(xí)的方式將用戶映射到連續(xù)潛在空間.如果2個(gè)用戶在潛在空間的距離越近，則這2個(gè)用戶的影響概率越大.通過這種方式來構(gòu)造傳播模型Embedded IC.

本文傳播模型是一種帶有拓?fù)浣Y(jié)構(gòu)的傳播模型.與現(xiàn)有模型的主要區(qū)別是，本文傳播模型只關(guān)注用戶的興趣，如果用戶對(duì)傳播項(xiàng)感興趣，則用戶接受傳播項(xiàng).本文傳播模型在預(yù)測(cè)效果方面優(yōu)于IC模型和TIC模型，因此更適合作為求解影響最大化問題的傳播模型.

2 傳播模型

本節(jié)介紹基于主題興趣的傳播模型TI-IC.該模型是IC模型的擴(kuò)展，假設(shè)每個(gè)傳播項(xiàng)存在一個(gè)主題分布，并且每個(gè)用戶存在一個(gè)興趣分布.例如，一個(gè)電影可能會(huì)包含：喜劇、愛情、動(dòng)作等基本的主題，一個(gè)用戶也會(huì)存在一個(gè)興趣分布，如對(duì)喜劇的喜愛程度是0.6，對(duì)愛情劇的喜愛程度是0.1，對(duì)動(dòng)作片的喜愛程度是0.3.

TI-IC模型的工作原理如下：每個(gè)結(jié)點(diǎn)僅有一次機(jī)會(huì)由不活躍狀態(tài)變?yōu)榛钴S狀態(tài)，并且該過程不可逆.在時(shí)刻t= 0，只有種集S?V中的結(jié)點(diǎn)為傳播項(xiàng)i上的活躍結(jié)點(diǎn)；在時(shí)刻t≥1，如果結(jié)點(diǎn)u的任何鄰居v在時(shí)刻t-1變得活躍，那么它有一次機(jī)會(huì)去激活它的鄰居結(jié)點(diǎn)u，激活的概率為θi·θu.那么，在結(jié)點(diǎn)u的多個(gè)鄰居同時(shí)活躍的條件下，結(jié)點(diǎn)u被激活的概率為

(1)

IC模型和TI-IC模型最主要的區(qū)別在于：IC模型只考慮了活躍結(jié)點(diǎn)對(duì)相鄰目標(biāo)結(jié)點(diǎn)的影響概率，而不考慮傳播項(xiàng)的具體情況，IC模型假定對(duì)所有傳播項(xiàng)邊上的影響概率都是相同的；而TI-IC模型在描述信息傳播過程中關(guān)注目標(biāo)結(jié)點(diǎn)對(duì)傳播項(xiàng)的興趣，不同的傳播項(xiàng)對(duì)目標(biāo)結(jié)點(diǎn)會(huì)有不同的興趣，從而產(chǎn)生不同的影響概率.

TIC模型和TI-IC模型最主要的區(qū)別在于：TIC模型考慮了傳播項(xiàng)的主題分布和用戶在不同主題上對(duì)相鄰目標(biāo)用戶的影響，因此不同的朋友對(duì)目標(biāo)用戶會(huì)產(chǎn)生不同的影響；而TI-IC模型只關(guān)注目標(biāo)用戶對(duì)傳播項(xiàng)的興趣，而不考慮不同朋友對(duì)目標(biāo)用戶的影響.當(dāng)目標(biāo)用戶看到他的任何朋友接受傳播項(xiàng)時(shí)，目標(biāo)用戶都會(huì)以相同的概率被影響.

3 基于主題興趣的傳播模型的學(xué)習(xí)算法

本節(jié)使用EM算法求解基于主題興趣的傳播模型參數(shù).該學(xué)習(xí)算法的輸入是：社會(huì)網(wǎng)絡(luò)G(V,E)、用戶歷史動(dòng)作日志D(u,i,t)以及主題個(gè)數(shù)Z.在學(xué)習(xí)中我們假設(shè)每個(gè)用戶只能接受相同傳播項(xiàng)一次.另外，D中的u都屬于G中的結(jié)點(diǎn)集合V.我們令I(lǐng)代表傳播項(xiàng)集合，Di代表傳播項(xiàng)i的傳播軌跡.

學(xué)習(xí)算法的輸出結(jié)果是TI-IC模型的參數(shù)，我們記為Θ.現(xiàn)假設(shè)TI-IC傳播模型的每個(gè)傳播軌跡都是獨(dú)立的，則給定模型參數(shù)Θ的對(duì)數(shù)似然函數(shù)表示為

(2)

(3)

(4)

(5)

算法1. 學(xué)習(xí)興趣主題模型TI-IC參數(shù)的EM算法.

輸入：社會(huì)網(wǎng)G(V,E)、傳播軌跡D、主題個(gè)數(shù)Z；

輸出：TI-IC參數(shù)Θ={θu(?u∈V),θi(?i∈I)}.

② repeat

③ for alli∈Ido

④ for allz={1,2,…,Z} do

⑥ end for

⑧ for allz={1,2,…,Z} do

⑩ for allu∈Vdo

從歷史數(shù)據(jù)中學(xué)習(xí)TI-IC模型參數(shù)之后，在實(shí)際應(yīng)用之前還需要獲得傳播項(xiàng)的主題分布向量.如果傳播項(xiàng)是一個(gè)已經(jīng)存在的傳播項(xiàng)，TI-IC模型學(xué)習(xí)算法的輸出同時(shí)包含了傳播項(xiàng)的主題分布向量.然而，實(shí)際應(yīng)用中的任務(wù)通常是促銷新產(chǎn)品.如何針對(duì)新產(chǎn)品選擇合適的主題分布向量是一個(gè)關(guān)鍵問題.下面給出3種新產(chǎn)品的主題分布向量構(gòu)造方法：

1) 新產(chǎn)品的主題分布向量取自一個(gè)均分分布向量.這種方法顯然沒有考慮不同產(chǎn)品的特征，通常不能達(dá)到最佳的促銷效果.

2) 由領(lǐng)域?qū)＜覟樾庐a(chǎn)品選擇合適的主題分布向量.這種方法增加了人工的工作量，而且TI-IC模型中每個(gè)維度的具體含義，很難給出準(zhǔn)確的定義，使得領(lǐng)域?qū)＜液茈y做出合適的選擇.

(6)

對(duì)式(6)的優(yōu)化目標(biāo)，我們使用梯度下降算法求解.具體求解過程如算法2所示，其中λ是學(xué)習(xí)步長(zhǎng).

算法2. 學(xué)習(xí)新傳播項(xiàng)的算法.

輸出：新傳播項(xiàng)i的主題分布向量θi.

② repeat

④ until convergence

4 基于主題興趣的影響最大化算法

本節(jié)首先提出了基于主題興趣的影響傳播最大化問題，然后給出了求解該問題的一個(gè)新的啟發(fā)式算法.

4.1 問題定義

本節(jié)在基于主題興趣的傳播模型TI-IC基礎(chǔ)上，提出了基于主題興趣的影響最大化問題TIIM，并給出了該問題的形式化定義.

基于主題興趣的影響最大化問題TIIM：給定有向圖G(V,E)、用戶的歷史動(dòng)作日志D(u,i,t)、種集大小k、傳播項(xiàng)i.基于興趣主題的影響最大化問題是尋找大小為k的種集S，使得傳播項(xiàng)i的影響范圍最大.種集S形式化地表示為

(7)

其中，δi(S)表示種集S在傳播項(xiàng)i上的影響范圍.在TI-IC模型中，盡管邊上的影響概率需考慮主題和興趣，而傳播的機(jī)制并沒有發(fā)生變化.所以對(duì)于TI-IC模型而言，影響范圍函數(shù)δi(S)的單調(diào)性和子模性可直接由IC模型繼承而來.

4.2 基于主題興趣的啟發(fā)式算法

對(duì)TIIM問題，完全可以使用傳統(tǒng)貪心算法[1]求解.但是在大規(guī)模網(wǎng)絡(luò)上由于多次蒙特卡洛模擬而使得貪心算法復(fù)雜度太高變得實(shí)際上并不可行.

貪心算法每次從所有結(jié)點(diǎn)中選擇影響增益最大的結(jié)點(diǎn)直到達(dá)到k個(gè)結(jié)點(diǎn)為止.假設(shè)圖中有|V|個(gè)結(jié)點(diǎn)、|E|條邊，每次估計(jì)影響范圍使用R次蒙特卡洛模擬，則貪心算法時(shí)間復(fù)雜度為O(kR|V||E|).實(shí)驗(yàn)中我們發(fā)現(xiàn)影響增益大的結(jié)點(diǎn)基本上都是本身影響范圍大的結(jié)點(diǎn).如果我們有一個(gè)啟發(fā)式算法預(yù)先排序每個(gè)結(jié)點(diǎn)的影響范圍，從中選中少量影響范圍大的結(jié)點(diǎn)構(gòu)成候選集，再使用貪心算法從候選集中選擇結(jié)點(diǎn)，也可以獲得和貪心算法一樣的結(jié)果.下面給出候選集的選擇過程.

從社交網(wǎng)中每個(gè)結(jié)點(diǎn)v出發(fā)，進(jìn)行深度優(yōu)先搜索，尋找影響概率大于等于閾值ε的所有路徑，可構(gòu)造一棵以v為根的可達(dá)路徑樹，則結(jié)點(diǎn)v的影響范圍可以近似地估計(jì)為

(8)

其中，PATH(v,u)表示從結(jié)點(diǎn)v到結(jié)點(diǎn)u的可達(dá)路徑集合;p(path)表示沿著路徑path，結(jié)點(diǎn)v對(duì)結(jié)點(diǎn)u的影響概率.定義候選集合C，C中存儲(chǔ)δv值最大的前λk結(jié)點(diǎn)，我們僅對(duì)C中的結(jié)點(diǎn)利用蒙特卡洛模擬計(jì)算影響范圍，貪心選擇k個(gè)結(jié)點(diǎn)作為種集.實(shí)驗(yàn)中λ=3就取得了和傳統(tǒng)貪心算法幾乎一樣的實(shí)驗(yàn)結(jié)果.例1給出了生成候選集合的一個(gè)實(shí)例.

例1. 如圖1(a)，給定有向圖G(V,E)，邊上概率已學(xué)習(xí)獲得，期望選擇2個(gè)種子結(jié)點(diǎn)進(jìn)行影響最大化，設(shè)置閾值ε=0.03.構(gòu)造結(jié)點(diǎn)a的可達(dá)路徑樹T(a)，如圖1(b)所示.由式(8)可得δa=0.878 5(沒有包括對(duì)自身結(jié)點(diǎn)a的影響).以此類推，可以計(jì)算出圖1(a)中所有結(jié)點(diǎn)的影響范圍，δb=0.1，δc=0.9， 其余結(jié)點(diǎn)的影響范圍都為0，因此C={a,c,b}，再通過蒙特卡洛模擬方法貪心選擇2個(gè)具有最大影響范圍的結(jié)點(diǎn)作為種集.

Fig. 1 An example for reachable paths圖1 可達(dá)路徑的例子

在生成候選集之后，使用帶有CELF優(yōu)化的貪心算法選擇種集，可得到有效解決TIIM問題的啟發(fā)式算法ACG-TIIM.算法的偽代碼如算法3所示.

算法3. 求解TIIM問題的啟發(fā)式算法ACG-TIIM.

輸入：圖G(V,E)、用戶興趣向量集合{θu|u∈V}、傳播項(xiàng)i的主題分布θi、種集大小k、主題個(gè)數(shù)Z、模擬次數(shù)R；

輸出：種集S.

①S=?,C=?；

② for (u,v)∈E

④ end for

⑤ for eachv∈V

⑥ CreateT(v)；

⑧ end for

⑨Sort(V,δv)；

⑩ fori=1 toλkdo

算法3的輸入是一個(gè)有向圖G(V,E)、由TI-IC模型學(xué)習(xí)得到的用戶興趣向量集合(其中向量θu表示用戶u的興趣分布)、傳播項(xiàng)i的主題分布θi、一個(gè)正整數(shù)k、代表蒙特卡洛模擬次數(shù)的正整數(shù)R.輸出具有最大影響范圍的種集S(|S|=k).

步驟②～④利用由TI-IC模型學(xué)習(xí)得到的用戶興趣分布向量及傳播項(xiàng)的主題分布向量來計(jì)算結(jié)點(diǎn)間的影響概率.步驟⑤～⑧預(yù)先估計(jì)每個(gè)結(jié)點(diǎn)本身的影響范圍，實(shí)際上這種估計(jì)只需要保證排序正確即可.步驟⑨～按照每個(gè)結(jié)點(diǎn)的估計(jì)范圍進(jìn)行排序，將λk個(gè)結(jié)點(diǎn)放入候選集合C.步驟～將候選集合C的結(jié)點(diǎn)(連同當(dāng)前增益、當(dāng)前迭代次數(shù))放入優(yōu)先級(jí)隊(duì)列Q.步驟～使用CELF優(yōu)化[19]的貪心算法選擇大小為k的種集S.

步驟②～④的復(fù)雜度為O(Z|E|).步驟⑤～⑧的復(fù)雜度為O(|V||E|).步驟⑨的復(fù)雜度為O(|V|log|V|).步驟～是傳統(tǒng)貪心過程，復(fù)雜度為O(kR|C||E|).所以ACG-TIIM算法總的復(fù)雜度為O(|V||E|+kR|C||E|).傳統(tǒng)貪心算法時(shí)間復(fù)雜度為O(kR|V||E|).因?yàn)閨C|?|V|，所以ACG-TIIM算法要比傳統(tǒng)貪心算法快很多.

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

本節(jié)在2個(gè)真實(shí)數(shù)據(jù)集上測(cè)試和評(píng)估本文提出的模型和算法，并且與多個(gè)現(xiàn)有的模型及算法進(jìn)行比較.

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

我們使用2個(gè)真實(shí)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn).2個(gè)數(shù)據(jù)集都包含社會(huì)網(wǎng)G(V,E)和一組動(dòng)作日志D(u,i,t).數(shù)據(jù)集分別是Digg[6]和Last.fm[6].其中，Digg數(shù)據(jù)集是一個(gè)社交新聞網(wǎng)站，用戶在網(wǎng)站上對(duì)文章進(jìn)行投票評(píng)論，D中包含的元組(u,i,t)代表用戶u在時(shí)刻t投票給了故事i.如果用戶u投票給故事i，用戶u的朋友v在之后不久也投票給了故事i，采用與文獻(xiàn)[6]相同的處理方式，認(rèn)為這個(gè)投票的動(dòng)作從用戶u傳播到了朋友v.數(shù)據(jù)集Last.fm是世界最大的社交音樂平臺(tái)，用戶可以在這個(gè)網(wǎng)站中搜索、收聽以及評(píng)論自己喜歡的音樂.D中包含的元組(u,i,t)代表用戶u在時(shí)刻t評(píng)論了歌手i.

我們從Digg數(shù)據(jù)集中提取了15 000個(gè)結(jié)點(diǎn)和395 513條邊以及相應(yīng)的動(dòng)作日志.從Last.fm數(shù)據(jù)集中提取了5 100個(gè)結(jié)點(diǎn)和23 453條邊以及相應(yīng)的動(dòng)作日志.在2個(gè)數(shù)據(jù)集的動(dòng)作日志上各選擇了1 000個(gè)傳播項(xiàng)，并且每個(gè)傳播項(xiàng)的傳播范圍都超過50.在2個(gè)數(shù)據(jù)集中，我們都不考慮孤立結(jié)點(diǎn)，即在D中有動(dòng)作記錄，但是在圖G中卻沒有朋友的結(jié)點(diǎn).

實(shí)驗(yàn)中所有算法均用C++編寫，在Microsoft Visual Studio 2005環(huán)境下編譯.所有實(shí)驗(yàn)都在Intel Core i7 6700 3.4 GHz-主頻 CPU、8 GB主存的臺(tái)式機(jī)上運(yùn)行.

5.2 對(duì)比模型和對(duì)比指標(biāo)

本文模型主要與下面6個(gè)模型進(jìn)行對(duì)比.

1) 獨(dú)立級(jí)聯(lián)模型(IC模型).傳統(tǒng)的獨(dú)立級(jí)聯(lián)模型工作原理如下.網(wǎng)絡(luò)中結(jié)點(diǎn)共有2個(gè)狀態(tài)，活躍結(jié)點(diǎn)與不活躍結(jié)點(diǎn)，每個(gè)活躍結(jié)點(diǎn)有且僅有一次機(jī)會(huì)去激活未活躍的結(jié)點(diǎn)，并且該過程不可逆，傳播的停止條件是當(dāng)前時(shí)刻沒有再被激活的結(jié)點(diǎn).該模型的參數(shù)為結(jié)點(diǎn)間的影響傳播概率，由文獻(xiàn)[20]中的EM算法學(xué)習(xí)而來.

2) 基于主題的獨(dú)立級(jí)聯(lián)模型(TIC模型[6]).TIC模型工作原理與IC模型一致，與IC模型不同的是，活躍結(jié)點(diǎn)激活不活躍結(jié)點(diǎn)的概率為基于主題的影響傳播概率.該模型的參數(shù)為結(jié)點(diǎn)間基于主題的影響傳播概率，由文獻(xiàn)[6]中的EM算法學(xué)習(xí)而來.

3) 固定傳播概率的IC模型(NIC).固定邊上影響概率為0.02(多次實(shí)驗(yàn)測(cè)試最佳的影響概率值)，工作原理與IC模型一致.

3個(gè)模型共同需要設(shè)置的參數(shù)是延遲閾值Δ，通常的做法是設(shè)置Δ在3～5之間，但是通過實(shí)驗(yàn)我們發(fā)現(xiàn)Δ的變化對(duì)3個(gè)模型的影響不大，為了減少模型的計(jì)算量，在實(shí)驗(yàn)中我們都把Δ的值設(shè)置為無窮大.

4) 使用混合泊松過程建模社交影響、外部影響和內(nèi)部影響的CMPP模型[7].取社交影響權(quán)重為0.3，內(nèi)部影響權(quán)重為0.7，不考慮外部影響，這種配置是CMPP模型在本文實(shí)驗(yàn)數(shù)據(jù)上的最好效果.

5) 本文基于興趣主題的傳播模型TI-IC-UN.在模擬傳播之前，對(duì)新傳播項(xiàng)的特征向量直接取均勻分布.

6) 本文基于興趣主題的傳播模型TI-IC.在模擬傳播之前，對(duì)新傳播項(xiàng)的特征向量使用梯度下降算法(算法2)進(jìn)行學(xué)習(xí).

對(duì)于新的傳播項(xiàng)i，我們通過限制條件選取感染源集合：首先找到傳播項(xiàng)i的所有活躍結(jié)點(diǎn)；然后依次檢查這些活躍結(jié)點(diǎn)，如果活躍結(jié)點(diǎn)v的任何鄰點(diǎn)在傳播項(xiàng)i上都沒有在v之前活躍，就把活躍結(jié)點(diǎn)v加入到感染源集合中.

對(duì)于TIC模型和TI-IC模型，如果沒有明確說明，我們?cè)O(shè)置傳播項(xiàng)主題分布個(gè)數(shù)Z=10.TIC模型也使用算法2學(xué)習(xí)了新傳播項(xiàng)的主題分布向量.

我們將所有傳播項(xiàng)按照8∶2的比例分成訓(xùn)練集和測(cè)試集，保證一個(gè)傳播項(xiàng)的傳播軌跡或者全在訓(xùn)練集或者全在測(cè)試集.顯然測(cè)試集中的每個(gè)傳播項(xiàng)都是新傳播項(xiàng).首先在訓(xùn)練集上學(xué)習(xí)模型中的參數(shù)，然后根據(jù)學(xué)習(xí)得到的模型預(yù)測(cè)測(cè)試集中每個(gè)新傳播項(xiàng)的傳播結(jié)果.具體預(yù)測(cè)過程為：對(duì)每個(gè)傳播項(xiàng)i，首先確定它的感染源集合(如果結(jié)點(diǎn)v接受了傳播項(xiàng)i，但是v的任何鄰居沒有在v之前接受傳播項(xiàng)i，則結(jié)點(diǎn)v是感染源)；然后讓感染源中的結(jié)點(diǎn)為初始活躍結(jié)點(diǎn)，使用2 000次蒙特卡洛模擬模擬傳播項(xiàng)i的傳播過程，計(jì)算每個(gè)結(jié)點(diǎn)被激活的概率，最后根據(jù)預(yù)測(cè)的概率值計(jì)算如下10個(gè)指標(biāo).

1) 均方誤差(mean squared error,MSE).計(jì)算每個(gè)結(jié)點(diǎn)預(yù)測(cè)的概率值與真實(shí)值(被激活是1，沒被激活是0)差的平方，然后求平均值.

2) 準(zhǔn)確率(Accuracy).給定一個(gè)激活閾值τ，如果預(yù)測(cè)的概率值大于等于τ，則預(yù)測(cè)該結(jié)點(diǎn)活躍；否則預(yù)測(cè)該結(jié)點(diǎn)不活躍.對(duì)每個(gè)傳播項(xiàng)i，計(jì)算預(yù)測(cè)正確的結(jié)點(diǎn)數(shù)占所有結(jié)點(diǎn)數(shù)的百分比.

3) 真正例(true positive,TP).預(yù)測(cè)為活躍實(shí)際為活躍的結(jié)點(diǎn)數(shù).

4) 假正例(false positive,FP).預(yù)測(cè)為活躍實(shí)際為不活躍的結(jié)點(diǎn)數(shù).

5) 真負(fù)例(true negative,TN).預(yù)測(cè)為不活躍實(shí)際為不活躍的結(jié)點(diǎn)數(shù).

6) 假負(fù)例(false negative,FN).預(yù)測(cè)為不活躍實(shí)際為活躍的結(jié)點(diǎn)數(shù).

7) 精確率(precision,P)：

8) 召回率(recall,R)：

9)F1分?jǐn)?shù)(F1-score)：

10) ROC曲線下面積AUC.按照預(yù)測(cè)的概率值對(duì)所有結(jié)點(diǎn)排序，計(jì)算ROC曲線下面積.

注意：對(duì)每個(gè)傳播項(xiàng)，都按照上述公式先計(jì)算MSE,Accuracy,F1-score,AUC;然后在所有傳播項(xiàng)上求均值.

5.3 不同模型上的對(duì)比結(jié)果

5.3.1 在MSE上的對(duì)比

表1和表2分別給出了不同模型在2個(gè)數(shù)據(jù)集合上的MSE.可以看出，NIC模型的誤差最大，因?yàn)镹IC模型使用了固定的影響概率，使得預(yù)測(cè)效果較差.CMPP模型明顯優(yōu)于NIC模型，但是比IC模型和TIC模型要差.在Digg數(shù)據(jù)集上，IC模型明顯優(yōu)于TIC模型；而在Last.fm數(shù)據(jù)集上，IC模型與TIC模型差別不大.TI-IC-UN模型由于沒有學(xué)習(xí)新傳播項(xiàng)的主題分布向量，使得MSE要大于IC模型.但是當(dāng)學(xué)習(xí)了新傳播項(xiàng)的分布向量后得到的TI-IC模型要明顯優(yōu)于IC模型和TIC模型.這說明不同的傳播項(xiàng)有不同的特征，在傳播之前學(xué)習(xí)其特征是必要的.

Table 1 Mean Squared Error of Different Models in Digg表1 Digg上不同模型的均方誤差

Table 2 Mean Squared Error of Different Models in Last.fm表2 Last.fm上不同模型的均方誤差

5.3.2 在準(zhǔn)確率和F1分?jǐn)?shù)上的對(duì)比

圖2和圖3分別給出了不同模型在數(shù)據(jù)集Digg和Last.fm上在不同激活閾值τ下的準(zhǔn)確率.由圖2和圖3可知，在準(zhǔn)確率性能的度量上設(shè)置激活閾值τ>0.1時(shí)，我們新提出的模型TI-IC都明顯高于其他模型.其中NIC模型性能最差，IC模型和TIC模型次于TI-IC模型，但是明顯高于其他模型；TI-IC-UN模型由于沒有考慮新傳播項(xiàng)的主題分布，與IC模型和TIC模型相比，在準(zhǔn)確率方面仍然處于劣勢(shì).

Fig. 2 Accuracy of different models in Digg dataset圖2 Digg數(shù)據(jù)集上不同模型下的準(zhǔn)確率

Fig. 3 Accuracy of different models in Last.fm dataset圖3 Last.fm數(shù)據(jù)集上不同模型下的準(zhǔn)確率

圖4和圖5分別給出了不同模型在數(shù)據(jù)集Digg和Last.fm 上在不同激活閾值τ下的F1-score.從圖4和圖5可以看出，TI-IC模型的F1-score始終高于其他模型；TI-IC-UN模型由于沒有考慮新傳播項(xiàng)的主題分布，在F1-score上也不具有優(yōu)勢(shì).

Fig. 4 F1-score of different models in Digg dataset圖4 Digg數(shù)據(jù)集上不同模型下的F1-score

Fig. 5 F1-score of different models in Last.fm dataset圖5 Last.fm數(shù)據(jù)集上不同模型下的F1-score

綜上所述，我們新提出的模型TI-IC在準(zhǔn)確率和F1-score上均好于現(xiàn)有的IC模型和TIC模型，并且TI-IC，IC，TIC模型的預(yù)測(cè)效果明顯好于CMPP模型和固定影響概率的NIC模型.

5.3.3 在ROC曲線上的對(duì)比

我們對(duì)比了不同模型的ROC曲線，如圖6和圖7所示.在數(shù)據(jù)集Digg上TI-IC模型與IC模型、TIC模型在ROC曲線上有多處重疊，但是TI-IC模型在ROC曲線下面積仍然大于IC模型和TIC模型.在數(shù)據(jù)集Last.fm上，TI-IC模型的優(yōu)勢(shì)更明顯.在2個(gè)數(shù)據(jù)集上，TI-IC-UN模型的ROC曲線下面積仍然低于IC模型和TIC模型，再次說明學(xué)習(xí)新傳播項(xiàng)自身特征的重要性.

Fig. 6 ROC curve of different models in Digg dataset圖6 Digg數(shù)據(jù)集上不同模型下的ROC曲線

Fig. 7 ROC curve of different models in Last.fm dataset圖7 Last.fm數(shù)據(jù)集上不同模型下的ROC曲線

綜合5.3.1～5.3.3節(jié)中的實(shí)驗(yàn)結(jié)果和分析，我們可以得出如下結(jié)論：TI-IC模型相比于其他現(xiàn)有模型能更有效地模擬傳播過程，更準(zhǔn)確地預(yù)測(cè)傳播結(jié)果.

5.4 不同主題個(gè)數(shù)對(duì)結(jié)果的影響

本節(jié)實(shí)驗(yàn)主要驗(yàn)證不同主題個(gè)數(shù)對(duì)實(shí)驗(yàn)結(jié)果的影響.圖8和圖9分別給出了數(shù)據(jù)集Digg和Last.fm上TI-IC模型和TIC模型在不同主題數(shù)下的ROC面積,其他模型沒有主題個(gè)數(shù)選項(xiàng).從實(shí)驗(yàn)圖中可以看出：當(dāng)主題個(gè)數(shù)是10時(shí)，基本達(dá)到了理想的實(shí)驗(yàn)結(jié)果;當(dāng)主題個(gè)數(shù)大于10時(shí)，實(shí)驗(yàn)效果沒有明顯改善.考慮到學(xué)習(xí)效率，本文設(shè)置主題個(gè)數(shù)為10.

Fig. 8 ROC area vs topic number in Digg dataset圖8 Digg數(shù)據(jù)集上主題個(gè)數(shù)對(duì)ROC面積的影響

Fig. 9 ROC area vs topic number in Last.fm dataset圖9 在Last.fm數(shù)據(jù)集上主題個(gè)數(shù)對(duì)ROC面積的影響

5.5 影響最大化算法對(duì)比

本文提出的啟發(fā)式算法ACG-TIIM，主要與如下影響最大化算法進(jìn)行比較.

1) LDegree算法.在這個(gè)算法中，我們簡(jiǎn)單選擇具有最大度的k個(gè)結(jié)點(diǎn)作為種集，再使用蒙特卡洛模擬估計(jì)影響范圍.

2) CELF-Gre算法.使用帶有CELF優(yōu)化[19]的貪心算法選擇k個(gè)結(jié)點(diǎn)作為種集，該算法在影響最大化問題中被廣泛應(yīng)用.

3) ACG-TIIM-UN算法.本文提出啟發(fā)式算法ACG-TIIM，但是不學(xué)習(xí)新傳播項(xiàng)的主題分布，直接取均勻分布.

本節(jié)實(shí)驗(yàn)中，涉及蒙特卡洛模擬估計(jì)影響范圍時(shí)都將設(shè)置模擬次數(shù)R=2 000.CELF-Gre算法和ACG-TIIM算法在應(yīng)用到TI-IC模型之前，都用本文EM算法獲取用戶的興趣分布以及新傳播項(xiàng)的主題分布，然后轉(zhuǎn)換成邊上的影響概率.新傳播項(xiàng)取自測(cè)試集合，并對(duì)所有傳播項(xiàng)的結(jié)果計(jì)算均值.CELF-Gre算法和ACG-TIIM算法在應(yīng)用到IC模型之前，都用文獻(xiàn)[20]中算法直接獲取邊上的影響概率.CELF-Gre算法和ACG-TIIM算法在應(yīng)用到TIC模型之前，都用文獻(xiàn)[6]中算法獲取邊上分主題的影響概率，再用本文算法學(xué)習(xí)新傳播項(xiàng)的主題分布,轉(zhuǎn)換成邊上的影響概率.在實(shí)驗(yàn)中，我們將統(tǒng)一設(shè)置算法中的主題數(shù)目Z=10，選擇候選集合時(shí)設(shè)置λ=3.

5.5.1 種集大小與影響范圍的關(guān)系

本節(jié)實(shí)驗(yàn)主要驗(yàn)證種影響范圍與種集大小的關(guān)系.首先在TI-IC模型下，運(yùn)行上述對(duì)比算法選擇不同大小的種集，在數(shù)據(jù)集Digg和Last.fm上的影響范圍如實(shí)驗(yàn)圖10和圖11所示.

Fig.10 Influence spread vs seeds number in Digg dataset圖10 Digg數(shù)據(jù)集上種集大小對(duì)影響范圍的影響

Fig. 11 Influence spread vs seeds number in Last.fm dataset圖11 Last.fm數(shù)據(jù)集上種集大小對(duì)影響范圍的影響

從圖10和圖11可得出如下結(jié)論：LDegree算法的運(yùn)行效果最差，是由于該算法只考慮社會(huì)網(wǎng)中的拓?fù)浣Y(jié)構(gòu)，選擇了全局具有最大度的結(jié)點(diǎn)，既沒有考慮用戶之間的影響，也沒有考慮用戶對(duì)傳播項(xiàng)的興趣.ACG-TIIM-UN算法得到的影響范圍遠(yuǎn)遠(yuǎn)好于LDegree算法，是由于該算法在真實(shí)的數(shù)據(jù)上學(xué)習(xí)了用戶的興趣，轉(zhuǎn)換成了影響概率，使得影響范圍計(jì)算更準(zhǔn)確.然而，ACG-TIIM-UN算法獲得的影響范圍仍舊小于CELF-Gre算法和ACG-TIIM算法，這是因?yàn)镃ELF-Gre算法和ACG-TIIM算法除了學(xué)習(xí)用戶的興趣分布，還學(xué)習(xí)了新傳播項(xiàng)的主題分布，從而使得影響范圍更廣.而且，我們進(jìn)一步檢查了算法ACG-TIIM-UN和算法ACG-TIIM返回的種集，在所有傳播項(xiàng)上，算法ACG-TIIM-UN返回的種集幾乎都一樣；但是算法ACG-TIIM在不同的傳播項(xiàng)上返回的種子集合差異很大，這再次說明在促銷新產(chǎn)品時(shí)，應(yīng)該針對(duì)特定的產(chǎn)品選擇特定的用戶.CELF-Gre算法和ACG-TIIM算法得到幾乎相同的影響范圍.我們進(jìn)一步檢查了這2個(gè)算法返回的種集，發(fā)現(xiàn)在不同的種集大小條件下，這2個(gè)算法返回的種集幾乎全完一樣.這是因?yàn)檫@2個(gè)算法在計(jì)算種集之前，學(xué)習(xí)了相同的參數(shù)(包括用戶興趣分布和新傳播項(xiàng)的主題分布).但是ACG-TIIM算法只考察了部分候選結(jié)點(diǎn)，而CELF-Gre算法需要考察全部候選結(jié)點(diǎn)，這使得這2個(gè)算法的運(yùn)行效率會(huì)差別很大，具體差別見5.5.2節(jié)的實(shí)驗(yàn).

在IC模型和TIC模型下，我們也運(yùn)行了上述對(duì)比算法.在IC模型下，ACG-TIIM算法和CELF-Gre算法的影響范圍幾乎完全一樣.在TIC模型下，ACG-TIIM-UN的影響范圍稍微低于ACG-TIIM算法和CELF-Gre算法，ACG-TIIM算法和CELF-Gre算法的影響范圍幾乎完全一樣.

5.5.2 種集大小與運(yùn)行時(shí)間的關(guān)系

本節(jié)主要對(duì)影響最大化算法的運(yùn)行時(shí)間進(jìn)行比較.在TI-IC模型上，運(yùn)行上述對(duì)比算法選擇不同大小的種集，在數(shù)據(jù)集Digg和Last.fm上的運(yùn)行時(shí)間如實(shí)驗(yàn)圖12和圖13所示：

Fig.12 Running time vs seeds number in Digg dataset圖12 Digg數(shù)據(jù)集上種集大小對(duì)運(yùn)行時(shí)間的影響

Fig. 13 Running time vs seeds number in Last.fm dataset圖13 Last.fm數(shù)據(jù)集上種集大小對(duì)運(yùn)行時(shí)間的影響

從實(shí)驗(yàn)圖中可得出如下結(jié)論：LDegree算法的運(yùn)行時(shí)間是最短的，由于該算法只是從整個(gè)網(wǎng)絡(luò)中選擇具有最大度的k個(gè)結(jié)點(diǎn)作為種集.ACG-TIIM算法和ACG-TIIM-UN算法的運(yùn)行效率較為接近，ACG-TIIM算法在選擇種集之前需要學(xué)習(xí)新傳播項(xiàng)的主題分布，所以ACG-TIIM算法比ACG-TIIM-UN算法稍慢.但是ACG-TIIM算法比CELF-Gre算法快2個(gè)數(shù)量級(jí)，這是因?yàn)锳CG-TIIM算法在選擇種集之前，先生成候選結(jié)點(diǎn)，僅對(duì)候選結(jié)點(diǎn)進(jìn)行蒙特卡洛模擬估計(jì)影響范圍.候選結(jié)點(diǎn)數(shù)要遠(yuǎn)遠(yuǎn)小于所有結(jié)點(diǎn)數(shù)，所以ACG-TIIM算法效率比CELF-Gre算法高很多，這與4.2節(jié)算法復(fù)雜性分析結(jié)果基本一致.

在IC模型和TIC模型下，我們也運(yùn)行了上述對(duì)比算法，ACG-TIIM算法效率遠(yuǎn)遠(yuǎn)優(yōu)于CELF-Gre算法.

6 結(jié)束語

本文提出了基于用戶興趣和傳播項(xiàng)主題分布的傳播模型TI-IC，并給出了基于TI-IC模型的影響最大化算法ACG-TIIM.實(shí)驗(yàn)結(jié)果表明，本文提出的模型TI-IC在多個(gè)測(cè)試指標(biāo)上都優(yōu)于現(xiàn)有的模型，能更準(zhǔn)確地預(yù)測(cè)傳播結(jié)果.ACG-TIIM算法可高效求解TI-IC模型的影響最大化問題，而且ACG-TIIM算法也適用于IC模型和TIC模型上的影響最大化問題.

未來的研究工作擬對(duì)用戶的興趣分布和用戶之間的影響進(jìn)行聯(lián)合建模，希望能獲得更有效的社交網(wǎng)傳播模型.