謝勝男，劉　勇，朱敬華，譚　龍

?

社會網(wǎng)中基于主題的局部影響最大化算法研究*

謝勝男，劉勇+，朱敬華，譚龍

黑龍江大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院，哈爾濱150080

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology

1673-9418/2016/10(05)-0646-11

E-mail: fcst@vip.163.com

http: //www.ceaj.org

Tel: +86-10-89056056

* The National Natural Science Foundation of China under Grant No. 81273649 (國家自然科學(xué)基金); the Natural Science Foundation of Heilongjiang Province under Grant No. F201430 (黑龍江省自然科學(xué)基金); the Scientific Research Fund of Heilongjiang Provincial Education Department under Grant Nos. 12531476, 12531498 (黑龍江省教育廳科學(xué)技術(shù)研究項目).

Received 2015-07,Accepted 2015-09.

CNKI網(wǎng)絡(luò)優(yōu)先出版: 2015-09-15, http://www.cnki.net/kcms/detail/11.5602.TP.20150915.1615.006.htm l

XIE Shengnan, LIU Yong, ZHU Jinghua, et al. Research on topic-based local in fluence m axim ization algorithm in social network. Journal of Frontiersof Com puter Science and Technology, 2016, 10(5): 646-656.

摘要：局部影響最大化問題是在社會網(wǎng)中尋找最能影響某個目標(biāo)節(jié)點(diǎn)的種集?，F(xiàn)有的研究只考慮對單一目標(biāo)節(jié)點(diǎn)的影響，忽略了傳播項上的主題分布以及用戶之間基于主題的影響概率。重點(diǎn)研究了在主題分布的條

件下，如何選取最能影響目標(biāo)節(jié)點(diǎn)集合的種集，提出了針對目標(biāo)節(jié)點(diǎn)集合的局部影響程度計算方法（topicbased local influence degree computational method，T-LID），在此基礎(chǔ)上提出了基于主題的局部影響最大化（topic-based local influence maxim ization，TLIM）問題，并證明了該問題為NP-hard問題。為求解TLIM問題，提出了基于主題的局部貪心算法（topic-based local greedy algorithm，TLGA）以及基于主題的局部傳播算法（topic-based local propagation algorithm，TLPA）。多個真實數(shù)據(jù)的實驗結(jié)果表明，所提算法可以有效并高效地求解基于主題的局部影響最大化問題。

關(guān)鍵詞：社會網(wǎng)；基于主題；局部影響最大化；目標(biāo)集合

1 引言

最近，許多大型社會網(wǎng)絡(luò)，例如Facebook和微博，變得越來越受歡迎，因為它們可以把人們聯(lián)系起來，方便人們進(jìn)行信息交流。社會網(wǎng)中一個重要問題就是影響最大化問題。影響最大化問題的任務(wù)是在社會網(wǎng)中尋找一個種集，使得從這個種集出發(fā)能影響到社會網(wǎng)中盡可能多的用戶。

Kempe等人[1]首次將影響最大化問題形式化為離散型優(yōu)化問題?，F(xiàn)已存在許多關(guān)于社會網(wǎng)影響最大化問題的研究[2-5]，其中大多數(shù)都集中于尋找在整個社會網(wǎng)中最具影響力的節(jié)點(diǎn)，通過這些節(jié)點(diǎn)可以使得影響范圍達(dá)到最大值。然而，這些研究至少忽略了以下兩方面問題：第一，在一些應(yīng)用中，例如個性化推薦、目標(biāo)廣告投放以及個人產(chǎn)品推廣等，尋找在整個網(wǎng)絡(luò)中最能影響目標(biāo)集合的種集顯得更為重要。第二，在真實影響傳播過程中，由于傳播主題的不同會使得用戶之間的影響差異很大，例如導(dǎo)師在研究方向上會對他的學(xué)生有極大的影響力，但在流行商品購買方面對他的學(xué)生很少具有影響力。

實際上，尋找最能影響目標(biāo)節(jié)點(diǎn)集合的種集，既不能直接選擇目標(biāo)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)，也不能簡單地選擇全局最具影響力的節(jié)點(diǎn)。首先分析以下現(xiàn)象來說明：新浪微博是近幾年特別受歡迎的一個社交軟件，利用一組從該網(wǎng)站爬取的數(shù)據(jù)[6]來做進(jìn)一步的解釋。該新浪微博數(shù)據(jù)集有602個節(jié)點(diǎn)，17 595條邊，分析新浪微博數(shù)據(jù)集的統(tǒng)計特征，結(jié)果如圖1和圖2所示。

由圖1可以觀察到，對于一個給定用戶，他通常有幾十甚至上百個鄰居。因此，對于目標(biāo)用戶集合，很難確定哪些鄰居是最能影響目標(biāo)集合的k個節(jié)點(diǎn)，尤其當(dāng)k比較小的時候。

在圖2中，通過總結(jié)全局影響力top-k節(jié)點(diǎn)的影響覆蓋率（k從1到30）可以觀察到，即使是影響力top-30的節(jié)點(diǎn)集合，在影響覆蓋率上也存在很大的空白，這也證明了尋找全局影響力top-k節(jié)點(diǎn)不能解決局部影響最大化問題。

Fig.1 User-neighbor distribution圖1 用戶-鄰居分布

Fig.2 Influence spread vs top-k influential users圖2 影響范圍和影響力top-k用戶

通過分析以上現(xiàn)象可證明，并不可以用現(xiàn)有的解決影響最大化問題的方法解決局部影響最大化問題。并且現(xiàn)有的多數(shù)影響最大化研究都忽略了用戶之間在不同主題上有不同影響力的情況。顯然，提出基于主題的局部影響最大化解決方法有重要的理論意義和廣泛的應(yīng)用價值。本文主要貢獻(xiàn)如下：

（1）提出了基于主題的局部影響程度計算方法（topic-based local influence degree computational method，T-LID），在此基礎(chǔ)上，提出了基于主題的局部影響最大化（topic-based localinfluencemaximization，TLIM）問題，并證明了該問題為NP-hard問題。

（2）為求解TLIM問題，提出了近似比為1-1/e的基于主題的局部貪心算法（topic-based local greedy algorithm，TLGA）。為支持大規(guī)模網(wǎng)絡(luò)上求解TLIM問題，又提出了一個基于主題的局部傳播算法（topicbased local propagation algorithm，TLPA）。

（3）多個真實數(shù)據(jù)集上的實驗結(jié)果表明，算法TLGA和TLPA可以有效地解決TLIM問題。盡管TLPA沒有近似比保證，但是TLPA比TLGA快近5個數(shù)量級，而且TLPA求得的局部影響程度非常接近TLGA。此外，實驗結(jié)果也證明了在解決局部影響最大化問題時，考慮主題因素可以使得影響程度計算更準(zhǔn)確。

本文組織結(jié)構(gòu)如下：第2章介紹了相關(guān)工作；第3章給出了基于主題的局部影響程度計算方法T-LID 及TLIM問題定義；第4章提出了基于主題的局部貪心算法TLGA及局部傳播算法TLPA；第5章給出了實驗結(jié)果及分析；第6章對本文工作進(jìn)行總結(jié)。

2 相關(guān)工作

Domingos等人[7]最先考慮社會網(wǎng)中具有影響力的節(jié)點(diǎn)選擇問題。2003年，Kempe等人[1]首次提出了影響最大化問題，證明了影響最大化問題在獨(dú)立級聯(lián)模型和線性閾值模型上都為NP-hard問題，并且設(shè)計出具有1-1/e近似比的貪心算法。貪心算法雖然簡單，但是由于在每次迭代選擇種子節(jié)點(diǎn)的過程中都需要進(jìn)行大量的蒙特卡洛模擬來估計影響范圍，導(dǎo)致貪心算法的效率較低。Leskovec等人[8]提出了一個CELF優(yōu)化的方法來改進(jìn)貪心算法的效率，在保持和簡單貪心算法一致的近似比的前提下，比簡單貪心算法快700倍。

許多研究通過設(shè)計高效的啟發(fā)式算法來改進(jìn)大規(guī)模網(wǎng)絡(luò)上影響最大化問題的計算效率。例如，Kimura等人[9]為了更高效地估計影響范圍提出了兩個基于最短路徑的影響級聯(lián)模型。Goyal等人[10]通過計算鄰居節(jié)點(diǎn)的簡單路徑估計影響范圍。啟發(fā)式算法通常沒有近似比保證，但具有很高的效率。

Guo等人[6]提出了局部影響最大化問題，即給定一個目標(biāo)節(jié)點(diǎn)w，選擇k個對w影響程度最大的節(jié)點(diǎn)。同時提出了具有近似比保證的局部影響最大化算法。然而Guo等人的研究中并沒有考慮針對目標(biāo)節(jié)點(diǎn)集合T，如何選擇最具影響力的k個節(jié)點(diǎn)。

以上的求解傳統(tǒng)影響最大化和局部影響最大化的研究中都忽略了主題因素。而一些考慮主題的研究也并沒有考慮局部影響最大化問題。如Liu等人[11]提出了一個概率模型用來學(xué)習(xí)主題分布以及主題感知的影響力度。Barbieri等人[12]擴(kuò)展了傳統(tǒng)IC模型，提出了主題感知的獨(dú)立級聯(lián)模型（topic-aware influence cascade, TIC），并利用用戶的歷史動作日志學(xué)習(xí)TIC模型參數(shù)。

為解決上述研究忽略的問題，本文在解決局部影響最大化問題的同時考慮了主題因素。在TIC模型的基礎(chǔ)上設(shè)計了求解局部影響最大化問題的高效算法。

3 計算方法及問題定義

本文介紹了基于主題的影響傳播模型TIC，提出了基于主題的局部影響程度計算方法T-LID，并給出了基于主題的局部影響最大化問題的形式化定義。

3.1 TIC模型

本文使用在文獻(xiàn)[12]中提出的TIC模型，該模型是IC模型的擴(kuò)展，用來將主題混合在每一個傳播項中。例如，一個電影可能會包含如下基本的主題：喜劇、愛情、動作等?，F(xiàn)給定一個社會網(wǎng)G=(V, E)和用戶的歷史動作日志D(User, Item, Time)，其中元組(u, i, t)代表用戶u在時間t采納商品i。TIC模型要從以上兩個給定的數(shù)據(jù)集中學(xué)習(xí)參數(shù)。假設(shè)有Z個基本的主題，z∈[1,Z]代表一個主題。這里認(rèn)為每個傳播項i都存在一個主題分布，用表示，并且。定義概率pzu, v∈[0, 1]，代表用戶u在主題z上對用戶v的影響程度，對于所有的(u, v)?E 或u=v，pzu, v=0。這里可以得出傳播項i在邊(u, v)上的影響概率

TIC模型的工作原理與IC模型的工作原理相同：每個節(jié)點(diǎn)只有一次機(jī)會由不活躍狀態(tài)變?yōu)榛钴S狀態(tài)，并且該過程不可逆。在時刻t=0，只有種集S?V中的節(jié)點(diǎn)為活躍節(jié)點(diǎn)，在時刻t≥1，如果節(jié)點(diǎn)u在時刻t-1變得活躍，那么它有一次機(jī)會以概率p(u, v)激活它的鄰居節(jié)點(diǎn)v。每個活躍節(jié)點(diǎn)有且僅有一次激活其不活躍鄰居的機(jī)會，傳播過程一直持續(xù)到?jīng)]有再被激活的節(jié)點(diǎn)為止。

3.2 T-LID計算方法

在這一部分中，將給出基于主題的局部影響程度計算方法T-LID。

令DT(S)表示種集S對目標(biāo)節(jié)點(diǎn)集合T的影響程度。那么，基于主題的局部影響最大化問題的目標(biāo)就是找到一個集合S，使得DT(S)的值達(dá)到最大。因此TLIM問題可以形式化表示為下式：

令ΩS表示整個網(wǎng)絡(luò)中種集S可能激活的結(jié)果構(gòu)成的樣本空間，則DT(S)可以表示為如下形式：

下面利用一個例子簡單說明TLD計算過程。

例1利用T-LID方法計算圖3中的DT(S)，其中。

首先列出ΩS，如表1所示。以ID4為例，ΩS中的概率計算過程如下：

Fig.3 Graph G w ithout topics圖3 無主題的圖G

Table 1 P(X) of each X in ΩS表1 ΩS中每個樣本X的概率P(X)

Fig.4 Graph G w ith topics圖4 基于主題的圖G

3.3問題定義基于主題的局部影響最大化：給定有向圖G=(V,

E)，動作日志D(User, Item, Time)，目標(biāo)節(jié)點(diǎn)集合T，種集大小k，傳播項i以及傳播項的主題分布γzi。選擇大小為k的種集S，使得S對T的影響程度最大。

定理1基于主題的局部影響最大化問題是NP-hard問題。

證明通過將集合覆蓋問題規(guī)約為局部影響最大化問題來證明局部影響最大化問題是NP-hard。

集合覆蓋問題的定義如下：給定集合U={u1，u2,…, um}，U的部分子集構(gòu)成的子集族S={S1，S2,…, Sn}，以及正整數(shù)k，問是否存在S的一個大小為k的子集S′，使得S′能覆蓋U的所有元素。

給定集合覆蓋問題的實例，構(gòu)造一個節(jié)點(diǎn)數(shù)目為|V|+|T|的有向二分圖，如圖5所示。V代表不包含目標(biāo)節(jié)點(diǎn)T的圖中節(jié)點(diǎn)，每個節(jié)點(diǎn)vi∈V對應(yīng)集合Si。T代表目標(biāo)節(jié)點(diǎn)集合，每個節(jié)點(diǎn)wj∈T代表一個元素uj。如果uj∈Si，則邊上的概率pi, j=1。

Fig.5 Bipartite graph w ith |V|+|T| nodes圖5 節(jié)點(diǎn)數(shù)目為|V|+|T|的有向二分圖

這樣，集合覆蓋問題可以等價地看作：在這個二分圖中，是否能找到有k個節(jié)點(diǎn)的集合可以激活所有T中的節(jié)點(diǎn)。如果存在能達(dá)到這個目標(biāo)的k個節(jié)點(diǎn)的集合，那么集合覆蓋問題就得到了解決。□

4 基于主題的局部影響最大化算法

本文為解決TLIM問題，提出了兩個算法：基于主題的局部貪心算法（topic-based local greedy algorithm，TLGA）和基于主題的局部傳播算法（topic

based local propagation algorithm，TLPA）。

4.1基于主題的局部貪心算法

3.2節(jié)中提出的DT(S)具有子模性。如果當(dāng)A?B?V，對?v∈V有f(A?{v})-f(A)≥f(B?{v})-f(B)，則稱一個集合函數(shù)f具有子模性。

定理2 DT(S)具有子模性。

因為子模函數(shù)的非負(fù)線性組合也具有子模性[1]，所以DT(S)具有子模性?！?/p>

對于一個非負(fù)的單調(diào)且具有子模性的集合函數(shù)f，選擇貪心方法可提供1-1/e的近似比。令S初始化為空。接下來每次都選擇使f獲得最大增益的節(jié)點(diǎn)加入S。S為最終選擇的k個種集，則f(S)≥(1-1/e)× f(S*)。其中S*為最優(yōu)的k個種集。

因為DT(S)具有子模性，所以利用貪心方法設(shè)計了基于主題的局部貪心算法TLGA。算法的輸入為圖G，目標(biāo)節(jié)點(diǎn)集合T，正整數(shù)k表示種集中節(jié)點(diǎn)數(shù)目，正整數(shù)R表示蒙特卡洛模擬要進(jìn)行的次數(shù)。RanCas表示蒙特卡洛模擬中的一個隨機(jī)過程，TIC模型參數(shù)為pzv, u，該參數(shù)利用文獻(xiàn)[11]中EM算法學(xué)習(xí)獲得。算法首先計算基于主題的混合影響概率pi

算法1基于主題的局部貪心算法

輸入：G=(V, E)，目標(biāo)集合T，pzv, u，k，γzi，R。

4. S=?

5. while| | S

6. for each v∈V S do

7.DT(S?{v})=0

8.for r = 1 to R

9.RanCas DMT(v)

10.DT(S?{v})+=DMT(v)

11.end for

12.DT(S?{v})=DT(S?{v})/R

13. end for

14.S=S?argmaxv∈VT?SDT(S?{v})

15. return S

其中，DMT(v)表示節(jié)點(diǎn)v加入當(dāng)前種集后對集合T的影響程度。

接下來，討論TLGA的時間復(fù)雜度。算法第1～3行計算所有piv, u的復(fù)雜性為O(mZ)，m為圖中邊的數(shù)目，Z為主題個數(shù)。第9行使用一次蒙特卡洛模擬計算節(jié)點(diǎn)加入種集后對目標(biāo)集合的影響程度，時間復(fù)雜性為O(m)。估計某個節(jié)點(diǎn)的影響增益要進(jìn)行R次蒙特卡洛模擬，因此第8～11行的復(fù)雜性為O(mR)。因為每次選擇最大增益節(jié)點(diǎn)需要考察全部剩余節(jié)點(diǎn)，所以第6～12行的時間復(fù)雜性為O(mnR)，n為圖中節(jié)點(diǎn)個數(shù)。由于一共需要選擇k個種子節(jié)點(diǎn)，則TLGA的復(fù)雜性為O(mZ+kmnR)。

4.2基于主題的局部傳播算法

算法TLGA為了模擬估計節(jié)點(diǎn)的精確影響范圍。通常需要大量的蒙特卡洛（R值會設(shè)得較大）。TLGA的復(fù)雜性為O(mZ+kmnR)，如果網(wǎng)絡(luò)規(guī)模變大，算法的效率會很低。

本節(jié)提出了一個高效的啟發(fā)式算法，稱為基于主題的局部傳播算法TLPA。不同于簡單貪心算法，TLPA不采用蒙特卡洛模擬來估計圖中節(jié)點(diǎn)對目標(biāo)節(jié)點(diǎn)集合的影響程度，而是通過構(gòu)建網(wǎng)絡(luò)中節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)集合之間的最短路徑集合來減少計算量。

定義1（最短路徑集合）對于圖G=(V, E)，將節(jié)點(diǎn)u∈VT到目標(biāo)節(jié)點(diǎn)集合T的最短路徑集合定義為u 到T中每個節(jié)點(diǎn)的最大傳播概率路徑構(gòu)成的集合，記為PathP(u, T)。PathP(u, T)形式化表示為：

PathP(u, T)={path(u→v)|v∈T}

令p(u→v)為u、v之間最短路徑path(u→v)上的傳播概率。顯然，節(jié)點(diǎn)u對目標(biāo)節(jié)點(diǎn)集合T的影響程度DT(v)可以近似地計算為DT(u)=∑v∈Tp(u→v)。因此，種集S對目標(biāo)集合T的影響程度DT(S)可以近似地計算為DT(S)=∑u∈S∑v∈Tp(u→v)。算法的偽代碼如算法2所示。

算法2基于主題的局部傳播算法

輸入：G=(V, E)，目標(biāo)集合T，pzv, u，k，γzi。

輸出：種集S，|S| = k。

接下來，討論TLPA的時間復(fù)雜度。計算所有piv, u的復(fù)雜性為O(mZ)，m為圖中邊的數(shù)目，Z為主題個數(shù)。構(gòu)造某個節(jié)點(diǎn)u到目標(biāo)節(jié)點(diǎn)集合T的最短路徑集合的復(fù)雜性為O(|T|L)，其中|T|為圖中節(jié)點(diǎn)個數(shù)，L為在所有PathP(u, T)路徑中邊的平均個數(shù)。因此，算法第6行的時間復(fù)雜性為O(n|T|L)，n為圖中節(jié)點(diǎn)個數(shù)。由于算法在最后選擇k個具有最大DT(v)的節(jié)點(diǎn)，則TLPA的復(fù)雜性為O(mZ+nL+k)。顯然，TLPA要比TLGA快很多。

5 實驗與結(jié)果分析

在兩個真實數(shù)據(jù)集上測試和評估了本文算法，并且與多個現(xiàn)有算法進(jìn)行了比較。

5.1實驗設(shè)置

實驗中使用了兩個真實數(shù)據(jù)集進(jìn)行測試和比較。兩個數(shù)據(jù)集都包含一個社會網(wǎng)G=(V, E)和一組動作日志D(User, Item, Time)。數(shù)據(jù)集分別是Digg[14]和Last.fm[15]。其中，Digg是一個社交新聞網(wǎng)站，用戶在網(wǎng)站上對文章進(jìn)行投票評論，D中包含的元組信息為(u, i, t)，代表用戶u在時刻t投票給了故事i。如果用戶u投票給故事i，u的朋友v在之后不久也投票給故事i，就認(rèn)為這個投票的動作從u傳播到了v。Last. fm是世界最大的社交音樂平臺，用戶可以在這個網(wǎng)站中搜索、收聽以及評論自己喜歡的音樂。D中包含的元組信息為(u, i, t)，代表用戶u在時刻t評論了歌手i。

從Digg數(shù)據(jù)集中提取了15 000個節(jié)點(diǎn)和395 513條邊以及相應(yīng)的動作日志。從Last.fm數(shù)據(jù)集中提取了5 100個節(jié)點(diǎn)和23 453條邊以及相應(yīng)的動作日志。在兩個數(shù)據(jù)集中，都不考慮斷開連接的節(jié)點(diǎn)，即在D中有動作記錄，但是在圖G中卻沒有朋友的節(jié)點(diǎn)。

實驗中所有算法均用C++編寫，在M icrosoft Visual Studio 2005環(huán)境下編譯。所有實驗都在Intel?CoreTM2 Duo CPU，2 GB主存的臺式機(jī)上運(yùn)行。

5.2對比方法描述

與下面幾個算法進(jìn)行實驗對比：（1）LND算法，選擇目標(biāo)集合的鄰居節(jié)點(diǎn)中度最大的k個節(jié)點(diǎn)作為種集。（2）LDegree算法，選擇全局具有最大度的k個節(jié)點(diǎn)作為種集。（3）LGA算法[7]，局部貪心算法。該算法在不考慮主題的前提下，采用貪心算法選擇k個對目標(biāo)節(jié)點(diǎn)影響程度最大的節(jié)點(diǎn)作為種集。（4）LGA+算法，LGA的改進(jìn)算法。先利用文獻(xiàn)[6]中提出的方法學(xué)習(xí)邊上概率，然后調(diào)用LGA算法。

所有對比算法在計算種集對目標(biāo)集合的影響程度時都使用10 000次蒙特卡洛模擬。對于不考慮主題的算法，除LGA+，均按照文獻(xiàn)[1]提出的WC模型設(shè)置邊上概率：p(u, v)=1/deg(v)，其中deg(v)表示節(jié)點(diǎn)v的入度。在學(xué)習(xí)TIC模型參數(shù)pzv, u的實驗中發(fā)現(xiàn)，在Digg數(shù)據(jù)集上的最佳主題數(shù)目為5，Last數(shù)據(jù)集上的最佳主題數(shù)為3。

5.3種集大小對目標(biāo)集合影響程度的影響

本組實驗考察種集大小k對影響程度的影響。

Fig.6 Influence degree vs seeds number in Last dataset圖6 在Last數(shù)據(jù)集上影響程度和種集大小

Fig.7 Influence degree vs seeds number in Digg dataset圖7 在Digg數(shù)據(jù)集上影響程度和種集大小

這3個算法都采用了真實數(shù)據(jù)學(xué)習(xí)邊上概率。在后續(xù)實驗中將證明TLGA和TLPA選擇的種集要好于LGA+。

5.4目標(biāo)集合大小對影響程度的影響

本組實驗考察目標(biāo)集合T的大小對影響程度的影響。實驗中設(shè)置。從圖8和圖9可以看出，當(dāng)固定種集大小k時，隨著目標(biāo)集合中節(jié)點(diǎn)數(shù)目的增加，影響程度也在增加。LDegree在不同目標(biāo)節(jié)點(diǎn)數(shù)目的影響程度都比較差，因為LDegree在選擇種集的時候沒有考慮拓?fù)浣Y(jié)構(gòu)。LND在Digg數(shù)據(jù)集上|T|=1到4的時候結(jié)果最差，這也證明了該算法的實驗結(jié)果不穩(wěn)定。LGA的影響程度好于LDegree和LND，因為LGA在計算影響程度的時候考慮了目標(biāo)集合的局部拓?fù)浣Y(jié)構(gòu)，并且利用有近似比保證的貪心方法計算影響程度。LGA+、TLGA和TLPA算法的效果最優(yōu)，因為利用真實數(shù)據(jù)計算節(jié)點(diǎn)間的影響概率。

Fig.8 Influence degree vs |T| in Last dataset圖8 在Last數(shù)據(jù)集上影響程度和目標(biāo)集合T節(jié)點(diǎn)數(shù)目

Fig.9 Influence degree vs |T| in Digg dataset圖9 在Digg數(shù)據(jù)集上影響程度和目標(biāo)集合T節(jié)點(diǎn)數(shù)目

5.5不同算法的運(yùn)行時間的比較

本組實驗考察本文算法與其他算法運(yùn)行時間上的差異。實驗中設(shè)置k值分別為2、4、6、8、10， |T|=5，Z=2，γzi=(1/2, 1/2)。從圖10和圖11中可以看出，LND運(yùn)行時間最短，這是因為LND只是在目標(biāo)節(jié)點(diǎn)集合的鄰居集中選擇k個具有最大度的節(jié)點(diǎn)作為種集。LDegree運(yùn)行時間也很短，因為LDegree在整個網(wǎng)絡(luò)中尋找k個具有最大度的節(jié)點(diǎn)作為種集。TLPA的運(yùn)行時間比較接近LND和LDegree，并且由前面進(jìn)行的實驗可知，TLPA可以得到很好的影響程度結(jié)果，也證明了TLPA的有效性和高效性。TLGA、LGA以及LGA+的運(yùn)行效率要遠(yuǎn)低于其他3種算法，因為這3種算法都需要利用大量次數(shù)的蒙特卡洛模擬來保證得到精確的影響程度。

Fig.10 Running time vs seeds number in Last dataset圖10 在Last數(shù)據(jù)集上運(yùn)行時間和種集大小

5.6主題對目標(biāo)集合影響程度的作用

本組實驗考察主題對影響程度的影響，主要從兩個方面進(jìn)行考察：（1）有無主題因素對影響程度的作用；（2）主題數(shù)目變化對影響程度的影響。

第一組實驗中，比較了LGA+、TLGA和TLPA算法。在之前的實驗中可以發(fā)現(xiàn)，這3種算法計算的影響程度結(jié)果十分接近。本文進(jìn)行4次獨(dú)立的實驗，設(shè)置k=5，|T|=5。觀察實驗結(jié)果中種集節(jié)點(diǎn)的動作日志與目標(biāo)集合的動作日志得出結(jié)論，如表2所示。其中S1、S2和S+分別表示由TLGA、TLPA和LGA+計算的種集。、|和分別表示T中與3個種集節(jié)點(diǎn)執(zhí)行動作相同的節(jié)點(diǎn)個數(shù)。從表2中可以看出和比的值大，表示基于主題的算法TLGA和TLPA選出的種集要比LGA+選出的好，證實了在解決影響最大化問題時考慮主題的意義。

Table 2 |S1→T|，|S2→T| and |S+→T| in 5 experiments表2 5次實驗中|S1→T|、|S2→T|和|S+→T|

第二組實驗中，通過改變主題的個數(shù)來觀察影響程度的變化。在利用TIC模型學(xué)習(xí)參數(shù)pzv, u時，可通過合并同類主題減少主題數(shù)目，將主題拆分為更細(xì)類別子目來增加主題數(shù)目。實驗過程中設(shè)置k=5， |T|=5。對于主題分布本文簡單設(shè)置γzi的每一個分量都為1/Z，即當(dāng)Z=2時，。在本組實驗中僅觀察基于主題的兩個算法TLGA和TLPA。從圖12和圖13可以看出，在兩個網(wǎng)絡(luò)上主題個數(shù)的變化對影響程度的影響并不明顯，這是因為計算傳播項上的影響概率公式為

Z，從而影響程度變化不明顯?？梢钥闯觯贚ast數(shù)據(jù)集上，當(dāng)Z=3時，影響程度最大。在Digg數(shù)據(jù)集上，當(dāng)Z=5時，影響程度最大。這也證實了在學(xué)習(xí)TIC模型時得出的結(jié)論：Digg數(shù)據(jù)集上的最佳主題數(shù)目為5，Last數(shù)據(jù)集上的最佳主題數(shù)為3。

Fig.12 Influence degree vs topics number in Last dataset圖12 在Last數(shù)據(jù)集上影響程度和主題數(shù)目

Fig.13 Influence degree vs topics number in Digg dataset圖13 在Digg數(shù)據(jù)集上影響程度和主題數(shù)目

6 結(jié)束語

本文提出了基于主題的局部影響程度計算方法和基于主題的局部影響最大化問題。為解決局部影響最大化問題，提出了一個基于主題的局部貪心算法和一個基于主題的局部傳播算法。多個數(shù)據(jù)集上的實驗結(jié)果驗證了本文算法的有效性和高效性。未來將研究用戶自身的主題分布，從而能更準(zhǔn)確地求解局部影響最大化問題。

References:

[1] Kempe D, K leinberg J, Tardos é. Maxim izing the spread of

influence through a social network[C]//Proceedings of the 9th ACM SIGKDD International Conference on Know l-edge Discovery and Data M ining, Washington, USA, Aug 24-27, 2003. New York, USA:ACM, 2003: 137-146.

[2] Chen Wei. Time-critical influence maxim ization in social networks w ith time- delayed diffusion process[C]//Proceedings of the 28th AAAI Conference on Artificial Intelligence, Québec, Canada, Jul 27-31, 2014. Menlo Park, USA: AAAI, 2014: 73-84.

[3] Li Yanhua, Chen Wei, Wang Yajun. Influence diffusion dynamics and influence maximization in social networks w ith friend and foe relationships[C]//Proceedings of the 6th ACM International Conference on Web Search and Data M ining, Rome, Italy, Feb 6-8, 2013. New York, USA: ACM, 2013: 657-666.

[4] Aslay C, Baribieri N, Barbieri N. Online topic-aware influence maxim ization queries[C]//Proceedings of the 17th International Conference on Extending Database Technology, Athens, Greece, Mar 24-28, 2014. New York, USA: ACM, 2014: 279-291.

[5] Kutzkov K, Bifet A, Bonchi F. Strip: stream learning of influence probabilities[C]//Proceedings of the 19th ACM SIGKDD International Conference on Know ledge Discovery and Data M ining, Chicago, USA, Aug 11- 14, 2013. New York, USA:ACM, 2013: 275-283.

[6] Guo Jing, Zhang Peng, Zhou Chuan. Personalized influence maximization on social networks[C]//Proceedings of the 2013 ACM Conference on Information and Know ledge Management, Burlingame, USA, Oct 27-Nov 1, 2013. New York, USA:ACM, 2013: 199-208.

[7] Domingos P, Richardson M. M ining the network value of customers[C]//Proceedings of the 7th ACM SIGKDD International Conference on Know ledge Discovery and Data M ining, San Francisco, USA, Aug 26- 29, 2001. New York, USA: ACM, 2001: 57-66.

[8] Leskovec J, Krause A, Guestrin C, et al. Cost-effective outbreak detection in networks[C]//Proceedings of the 13th ACM SIGKDD International Conference on Know ledge Discovery and Data M ining, San Jose, USA, Aug 12-15, 2007. New York, USA:ACM, 2007: 420-429.

[9] Kimura M, Saito K. Tractable models for information diffusion in social networks[C]//LNCS 4213: Proceedings of the 10th European Conference on Principles and Practice of Know ledge Discovery in Databases, Berlin, Germany, Sep 18-22, 2006. Berlin, Heidelberg: Springer, 2006: 259-271.

[10] Goyal A, Bonchi F, Lakshmanan L. Learning influence probabilities in social networks[C]//Proceedings of the 3rd ACM International Conference on Web Search and Data M ining, New York, USA, Feb 3-6, 2010. New York, USA: ACM, 2010: 241-250.

[11] Liu Lu, Tang Jie, Han Jiawei, et al. M ining topic-level influence in heterogeneous networks[C]//Proceedings of the 2010 ACM Conference on Information and Know ledge Management, Toronto, Canada, Oct 26-30, 2010. New York, USA: ACM, 2010: 545-576.

[12] Barbieri N, Bonchi F, Manco G. Topic-aware social influence propagation models[C]//Proceedings of 5th ACM International Conference on Web Search and Data M ining, Brussels, Belgium, Dec 10-13, 2012. New York, USA: ACM, 2012: 81-90.

[13] Chen Wei, Wang Yajun, Yang Siyu. Efficient influence maximization in social networks[C]//Proceedings of the 15th ACM SIGKDD International Conference on Know ledge Discovery and Data M ining, Paris, France, Jun 28-Jul 1, 2009. New York, USA:ACM, 2009: 199-208.

[14] Barbieri N, Bonchi F, Manco G. Cascade-based community detection[C]//Proceedings of the 6th ACM International Conference on Web Search and Data M ining, Rome, Italy, Feb 6-8, 2013. New York, USA:ACM, 2013: 33-42.

[15] Cantador I, Brusilovsky P, Kuflik T. Second workshop on information heterogeneity and fusion in recommender systems (HetRec2011)[C]//Proceedings of the 5th ACM Conference on Recommender Systems, Chicago, USA, Oct 23-27, 2011. New York, USA:ACM, 2011: 387-388.

XIE Shengnan was born in 1991. She is an M.S. candidate at School of Computer Science and Technology, Heilongjiang University. Her research interest is data mining.

謝勝男（1991—），女，黑龍江黑河人，黑龍江大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院碩士研究生，主要研究領(lǐng)域為數(shù)據(jù)挖掘。

LIU Yong was born in 1975. He received the Ph.D. degree in computer science from Harbin Institute of Technology in 2010. Now he is an associate professor and M.S. supervisor at School of Computer and Science Technology, Heilongjiang University. His research interests include data m ining and database, etc.

劉勇（1975—），男，河北昌黎人，2010年于哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)專業(yè)獲得博士學(xué)位，現(xiàn)為黑龍江大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院副教授、碩士生導(dǎo)師，主要研究領(lǐng)域為數(shù)據(jù)挖掘，數(shù)據(jù)庫等。

ZHU Jinghua was born in 1976. She received the Ph.D. degree in computer science from Harbin Institute of Technology in 2009. Now she is an associate professor and M.S. supervisor at Heilongjiang University. Her research interests include data mining and database, etc.

朱敬華（1976—），女，黑龍江齊齊哈爾人，2009年于哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)專業(yè)獲得博士學(xué)位，現(xiàn)為黑龍江大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院副教授、碩士生導(dǎo)師，主要研究領(lǐng)域為數(shù)據(jù)挖掘，數(shù)據(jù)庫等。

TAN Long was born in 1971. He is an associate professor and M.S. supervisor at School of Computer and Science Technology, Heilongjiang University. His research interests include cognitive radio network and data m ining, etc.

譚龍（1971—），男，黑龍江哈爾濱人，黑龍江大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院副教授、碩士生導(dǎo)師，主要研究領(lǐng)域為無線認(rèn)知傳感器網(wǎng)絡(luò)，數(shù)據(jù)挖掘等。

Research on Topic-Based Local InfluenceMaxim ization Algorithm in Social Network?

XIE Shengnan, LIU Yong+, ZHU Jinghua, TAN Long
School of Computer Science and Technology, Heilongjiang University, Harbin 150080, China + Corresponding author: E-mail: acliuyong@sina.com

Key words:social network; topic-based; local influence maxim ization; target set

Abstract:Local influence maximization is the problem of finding a small set of seed nodes in a social network that maximizes the influence on a target node. Existing works only consider the influence on a single target node, and also ignore the topic distribution of diffusion items and the influence probabilities between users based on topics. This paper focuses on how to select a seed set that has the maximum influence on a given target set based on the topic distribution, and proposes a new topic-based local influence degree computational method (T-LID). Based on T-LID, this paper also proposes a topic-based local influence maxim ization (TLIM) problem and proves that TLIM is NP-hard. In order to solve TLIM, this paper proposes a topic-based local greedy algorithm (TLGA) and a topic-based local propagation algorithm (TLPA). The experimental results on several real datasets show that the proposed algorithms can solve the TLIM problem effectively and efficiently.

doi:10.3778/j.issn.1673-9418.1507073

文獻(xiàn)標(biāo)志碼：A

中圖分類號：TP311