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

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

?

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

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

黑龍江大學計算機科學與技術學院，哈爾濱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 (國家自然科學基金); the Natural Science Foundation of Heilongjiang Province under Grant No. F201430 (黑龍江省自然科學基金); the Scientific Research Fund of Heilongjiang Provincial Education Department under Grant Nos. 12531476, 12531498 (黑龍江省教育廳科學技術研究項目).

Received 2015-07,Accepted 2015-09.

CNKI網絡優先出版: 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.

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

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

關鍵詞：社會網；基于主題；局部影響最大化；目標集合

1 引言

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

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

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

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

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

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

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

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

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

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

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

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

2 相關工作

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

許多研究通過設計高效的啟發式算法來改進大規模網絡上影響最大化問題的計算效率。例如，Kimura等人[9]為了更高效地估計影響范圍提出了兩個基于最短路徑的影響級聯模型。Goyal等人[10]通過計算鄰居節點的簡單路徑估計影響范圍。啟發式算法通常沒有近似比保證，但具有很高的效率。

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

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

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

3 計算方法及問題定義

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

3.1 TIC模型

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

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

3.2 T-LID計算方法

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

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

令ΩS表示整個網絡中種集S可能激活的結果構成的樣本空間，則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)，目標節點集合T，種集大小k，傳播項i以及傳播項的主題分布γzi。選擇大小為k的種集S，使得S對T的影響程度最大。

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

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

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

給定集合覆蓋問題的實例，構造一個節點數目為|V|+|T|的有向二分圖，如圖5所示。V代表不包含目標節點T的圖中節點，每個節點vi∈V對應集合Si。T代表目標節點集合，每個節點wj∈T代表一個元素uj。如果uj∈Si，則邊上的概率pi, j=1。

Fig.5 Bipartite graph w ith |V|+|T| nodes圖5 節點數目為|V|+|T|的有向二分圖

這樣，集合覆蓋問題可以等價地看作：在這個二分圖中，是否能找到有k個節點的集合可以激活所有T中的節點。如果存在能達到這個目標的k個節點的集合，那么集合覆蓋問題就得到了解決?！?/p>

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

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

based local propagation algorithm，TLPA）。

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

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

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

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

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

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

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

輸入：G=(V, E)，目標集合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)表示節點v加入當前種集后對集合T的影響程度。

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

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

算法TLGA為了模擬估計節點的精確影響范圍。通常需要大量的蒙特卡洛（R值會設得較大）。TLGA的復雜性為O(mZ+kmnR)，如果網絡規模變大，算法的效率會很低。

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

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

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

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

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

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

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

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

5 實驗與結果分析

在兩個真實數據集上測試和評估了本文算法，并且與多個現有算法進行了比較。

5.1實驗設置

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

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

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

5.2對比方法描述

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

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

5.3種集大小對目標集合影響程度的影響

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

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

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

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

5.4目標集合大小對影響程度的影響

本組實驗考察目標集合T的大小對影響程度的影響。實驗中設置。從圖8和圖9可以看出，當固定種集大小k時，隨著目標集合中節點數目的增加，影響程度也在增加。LDegree在不同目標節點數目的影響程度都比較差，因為LDegree在選擇種集的時候沒有考慮拓撲結構。LND在Digg數據集上|T|=1到4的時候結果最差，這也證明了該算法的實驗結果不穩定。LGA的影響程度好于LDegree和LND，因為LGA在計算影響程度的時候考慮了目標集合的局部拓撲結構，并且利用有近似比保證的貪心方法計算影響程度。LGA+、TLGA和TLPA算法的效果最優，因為利用真實數據計算節點間的影響概率。

Fig.8 Influence degree vs |T| in Last dataset圖8 在Last數據集上影響程度和目標集合T節點數目

Fig.9 Influence degree vs |T| in Digg dataset圖9 在Digg數據集上影響程度和目標集合T節點數目

5.5不同算法的運行時間的比較

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

Fig.10 Running time vs seeds number in Last dataset圖10 在Last數據集上運行時間和種集大小

5.6主題對目標集合影響程度的作用

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

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

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

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

Z，從而影響程度變化不明顯?？梢钥闯?，在Last數據集上，當Z=3時，影響程度最大。在Digg數據集上，當Z=5時，影響程度最大。這也證實了在學習TIC模型時得出的結論：Digg數據集上的最佳主題數目為5，Last數據集上的最佳主題數為3。

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

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

6 結束語

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

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—），女，黑龍江黑河人，黑龍江大學計算機科學與技術學院碩士研究生，主要研究領域為數據挖掘。

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年于哈爾濱工業大學計算機科學專業獲得博士學位，現為黑龍江大學計算機科學與技術學院副教授、碩士生導師，主要研究領域為數據挖掘，數據庫等。

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年于哈爾濱工業大學計算機科學專業獲得博士學位，現為黑龍江大學計算機科學與技術學院副教授、碩士生導師，主要研究領域為數據挖掘，數據庫等。

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—），男，黑龍江哈爾濱人，黑龍江大學計算機科學與技術學院副教授、碩士生導師，主要研究領域為無線認知傳感器網絡，數據挖掘等。

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

文獻標志碼：A

中圖分類號：TP311