基于領(lǐng)域的影響力最大化與病毒營銷

劉 泉，張 銘

(北京大學 信息科學與技術(shù)學院，北京 100871)

基于領(lǐng)域的影響力最大化與病毒營銷

劉 泉，張 銘

(北京大學 信息科學與技術(shù)學院，北京 100871)

近年來隨著新浪微博、人人網(wǎng)等社交網(wǎng)絡(luò)新媒體的涌現(xiàn)，線上影響力傳播得到了越來越多企業(yè)和研究機構(gòu)的關(guān)注。如何在給定資源的約束下實現(xiàn)最大的傳播范圍(影響力最大化問題)，對病毒營銷等市場戰(zhàn)略的有效開展有著重要意義。如果能充分利用社交網(wǎng)絡(luò)上的異質(zhì)性信息來更準確地定位用戶所屬的領(lǐng)域，進而基于領(lǐng)域?qū)崿F(xiàn)影響力最大化，將對從整體角度出發(fā)的傳統(tǒng)研究和片面的結(jié)構(gòu)或內(nèi)容角度的研究形成很好的補充。該文同時利用新浪微博上用戶之間的社交關(guān)系和微博內(nèi)容的話題兩個維度的信息將用戶劃分為不同的領(lǐng)域；進而提出了一種基于貪心和動態(tài)規(guī)劃混合的改良算法實現(xiàn)基于領(lǐng)域的影響力最大化。實驗表明該文的領(lǐng)域影響力模型較好優(yōu)化了傳統(tǒng)影響力最大化的時間消耗，同時擁有相近的精度。

影響力最大化；領(lǐng)域發(fā)現(xiàn)；領(lǐng)域影響力

1 引言

隨著互聯(lián)網(wǎng)的發(fā)展逐漸進入Web2.0時代，越來越多的人們開始在在線社交網(wǎng)絡(luò)上分享信息、表達情感、進行互動。國外以Facebook、Twitter為代表的社交網(wǎng)絡(luò)最為活躍。而在中國，新浪微博和人人網(wǎng)則是眾多社交網(wǎng)站中的領(lǐng)頭羊。從2009年8月開始內(nèi)測至今，新浪微博已經(jīng)擁有超過五億用戶，日活躍用戶高達6 000多萬。社交網(wǎng)絡(luò)的流行給人們的生活方式和商業(yè)模式帶來了巨大改變。近年來也吸引了來自學術(shù)界和工業(yè)界人士的高度關(guān)注與探索。

社交網(wǎng)絡(luò)的分析是一個前沿交叉研究方向，用到了大量來自數(shù)據(jù)挖掘、機器學習、自然語言處理、信息檢索等領(lǐng)域的知識。主要的研究方向有社區(qū)發(fā)現(xiàn)、推薦系統(tǒng)、信息傳播、情感分析等。在這些不同的研究方向中，信息傳播，特別是影響力傳播對其他相關(guān)研究的開展起著基礎(chǔ)性的作用。影響力，顧名思義，是指一種為別人所樂于接受的方式，改變他人的思想和行動的能力。表現(xiàn)在社交網(wǎng)絡(luò)上，則是指用戶因為受到其他用戶的影響(比如看到對方的微博、評論、轉(zhuǎn)發(fā)等)而改變原有認識或情感，或者是對某個新鮮事物從不了解到開始關(guān)注。

傳統(tǒng)的影響力研究大多集中在心理學等領(lǐng)域，研究人員通過線下實地調(diào)研取證來分析影響力的相關(guān)特征。近年來隨著社交網(wǎng)絡(luò)的興起，大量社交數(shù)據(jù)的積累為影響力的研究開辟了新的途徑。同時，整個社交網(wǎng)絡(luò)的普及也早已引起了商家的關(guān)注。如何在社交網(wǎng)絡(luò)這個新媒體上進行營銷和品牌推廣，成了當今商界一個重要新興問題。一些成功的網(wǎng)絡(luò)營銷案例逐漸形成了一個新的專有名詞“病毒營銷”，即通過用戶的口碑宣傳網(wǎng)絡(luò)，讓信息像病毒一樣傳播和擴散，利用快速復制的方式傳向數(shù)以千計、數(shù)以百萬計的受眾，實現(xiàn)杠桿遞增作用。從病毒營銷中抽象出來的影響力最大化(influence maximization)問題，最早由Kemple[1]等人提出，是指對于指定k值，尋找k個具有最大影響力范圍的節(jié)點集。雖然這個問題早已被證明是NP-完全的，但是眾多研究機構(gòu)卻并沒有放棄各種各樣優(yōu)化尋找過程的算法研究。更多相關(guān)工作的探討將在第二節(jié)予以介紹。

影響力最大化問題具有強烈的社會意義，尤其對于企業(yè)、商家利用最少營銷成本獲取盡可能大的目標客戶宣傳范圍具有重要指導意義。舉例來說，某公司推出了一款新飲料，為了能最大化地利用社交網(wǎng)絡(luò)中的口碑效應(yīng)進行宣傳，同時為了控制營銷成本預算，公司需要從消費人群中選取一小部分影響力較強的用戶，讓他們免費試飲或給予他們報酬，使他們愿意在各自的社交圈內(nèi)分析對這款飲料的感受。此時，如何優(yōu)化選取這些初始消費者(即種子用戶)就顯得至關(guān)重要。

傳統(tǒng)的影響力的研究大多是在整個社交網(wǎng)絡(luò)上的分析。然而實際生活經(jīng)驗啟示人們： 每個人都有各自的圈子和領(lǐng)域，某人在某個領(lǐng)域具有較高的影響力，并不代表他在其他領(lǐng)域也同樣具有較高的影響力。比如姚明對籃球?qū)w育很有發(fā)言權(quán)，他說的話可能會影響到很多粉絲的認知；然而對于計算機編程，他的話可能就不再那么具有說服力。最近的一些研究引入了從話題角度對影響力的分析，雖然一定程度上彌補了之前整體視角的漏洞，卻也未能對社交網(wǎng)絡(luò)的結(jié)構(gòu)屬性給予足夠的關(guān)注。

同樣對于影響力最大化的研究主要也集中在全局網(wǎng)絡(luò)下如何優(yōu)化Kemple[1]等人最初提出的貪心算法。近年來偶爾有文章致力于利用社區(qū)發(fā)現(xiàn)來在子網(wǎng)絡(luò)下最大化影響力，雖然簡化了問題規(guī)模但未對社交網(wǎng)絡(luò)的內(nèi)容維度進行充分利用；而另外一些基于話題的研究則只關(guān)注內(nèi)容維度忽略了潛在的社交關(guān)系信息。如果能夠同時利用好社交網(wǎng)絡(luò)上的結(jié)構(gòu)和內(nèi)容維度的信息，或許能夠為人們求解影響力最大化問題提供更好的精度和速度。

為了解決上述問題，本文將同時利用社交網(wǎng)絡(luò)用戶間相互關(guān)注的結(jié)構(gòu)維度信息和相似主題的內(nèi)容維度信息來進行領(lǐng)域劃分。模型首先對微博用戶的博文內(nèi)容進行預處理，并利用Twitter-LDA主題模型[12]無監(jiān)督地訓練出不同話題，再結(jié)合結(jié)構(gòu)維度的信息進行聚類；之后在各個子領(lǐng)域利用經(jīng)典的linear threshold模型來最大化各自領(lǐng)域的影響力，并與直接在全集上最大化影響力的結(jié)果進行比較。數(shù)據(jù)集源自中國流行的社交網(wǎng)站新浪微博(10多萬有效用戶及這些用戶的超過1千萬的微博內(nèi)容)。實驗效果顯示領(lǐng)域影響力最大化模型相比傳統(tǒng)影響力模型具有極低的時間代價，并具有很高的精度。

2 相關(guān)工作

Kempe[1]等人首先提出兩種隨機的影響力傳播模型，即independent cascade模型和linear threshold模型，并證明了兩種模型下的影響力最大化問題是一個NP完全的難題，他們提出的貪心算法為后來諸多的研究提供了基礎(chǔ)的框架和參照。然而貪心算法在大規(guī)模數(shù)據(jù)量面前卻問題重重，自此以后很多相關(guān)研究都在試圖解決這個問題。Leskovec[2]等人利用子模性，提出了一種基于lazy-forward改進的CELF算法來優(yōu)化種子選取的過程，相較之前的貪心算法有了近700倍的速度提升。Chen[3]等人提出了最大影響力路徑來有效限制影響力的計算到局部網(wǎng)絡(luò)，并在IC和LT模型下分別驗證了自己模型的效果。更多相關(guān)工作集中在優(yōu)化影響力函數(shù)和延展性上，或者結(jié)合整體網(wǎng)絡(luò)的新特性，比如潛在的傳播網(wǎng)絡(luò)等[4-6]。

Yu[7]等人在2010年首次提出引入社區(qū)發(fā)現(xiàn)來優(yōu)化影響力最大化的種子選取過程： 首先將整個社交網(wǎng)絡(luò)劃分成不同的子社區(qū)，然后利用一種動態(tài)規(guī)劃算法基于前k-1步選取的種子集來動態(tài)計算第k步應(yīng)當選取種子所在的社區(qū)。Barbieri[8]等人在2013年亦首次提出從話題的角度分析影響力最大化，并將傳統(tǒng)的Independent cascade模型和Linear threshold模型擴展到不同的話題下(TIC, TLT)。之后緊隨的[9-10]兩篇基于話題影響力最大化文獻分別從引入必要的預處理和在線實時計算的角度進行優(yōu)化。

近期以來的相關(guān)工作，或從社區(qū)發(fā)現(xiàn)，或從話題分類，對之前的影響力最大化問題有了進一步的研究。然而，它們都沒有充分利用社交網(wǎng)絡(luò)潛在的豐富信息。前者只利用了網(wǎng)絡(luò)的社區(qū)屬性，而忽略了內(nèi)容屬性，比如話題；而后者只利用了內(nèi)容屬性，忽略了用戶相互交流的社交屬性。社交網(wǎng)絡(luò)本質(zhì)上是一個不同緯度網(wǎng)絡(luò)組成的異質(zhì)性網(wǎng)絡(luò)(heterogeneous networks)，如果能夠充分利用其潛在的這些不同緯度的信息特征，將對研究人們影響力提供更深入的視角。本文作者發(fā)表的論文[11]正是從異質(zhì)性網(wǎng)絡(luò)切入分析不同領(lǐng)域的影響力的特征，本文則從基于領(lǐng)域的影響力最大化角度來進行研究。

3 模型

3.1 異質(zhì)性網(wǎng)絡(luò)

在新浪微博等社交網(wǎng)絡(luò)中，用戶可以通過不同的媒介形式進行交互。例如，一個用戶可以關(guān)注另一個用戶，或者轉(zhuǎn)發(fā)他的微博。為了便于后文的分析，這里將介紹一些必要的定義與標記符。

本文的異質(zhì)性網(wǎng)絡(luò)同時利用了結(jié)構(gòu)信息和內(nèi)容信息，即判別給定的兩個用戶是否應(yīng)當劃分到同一個領(lǐng)域中，主要可以根據(jù)以下兩點判別。

(1) 是否具有相似的社交圈；

(2) 是否在博文中討論相似的話題。

3.2 話題維網(wǎng)絡(luò)

隱含狄利克雷分布(latent dirichlet allocation,LDA)，是一種主題模型，它可以將文檔集中每篇文檔的主題按照概率分布的形式給出。同時它是一種無監(jiān)督學習算法，在訓練時不需要手工標注的訓練集，需要的僅僅是文檔集以及指定主題的數(shù)量k。此外LDA還可以對每一個主題均可找出一些詞語來描述它。自Blei等人于2003年提出后在文本挖掘等領(lǐng)域產(chǎn)生了深遠的影響。

然而社交網(wǎng)絡(luò)上大量的碎片信息使得LDA英雄無用武之地。就新浪微博而言，用戶的每條微博不超過140字，短小、簡練、口語化是微博內(nèi)容的顯著特征。為了能夠從短小的微博內(nèi)容中發(fā)現(xiàn)主題，北大網(wǎng)絡(luò)所博士研究生趙鑫等人[12]提出的Twitter-LDA主題模型，對社交網(wǎng)絡(luò)上短小、高頻的文本更加友好。

為了構(gòu)建本文的話題維網(wǎng)絡(luò)，爬取了十萬微博用戶每人最近的100條微博，共計1 000余萬條微博內(nèi)容，經(jīng)過分詞等預處理，輸入至Twitter-LDA模型中通過無監(jiān)督式學習發(fā)現(xiàn)共同的話題，并指定話題個數(shù)為20(經(jīng)驗值)；根據(jù)輸出的每個單詞在給定話題上的概率分布值，可以遍歷每個用戶的每條微博中的詞語，為用戶產(chǎn)生一個20維的話題向量，即在20個話題中每個話題的總概率值，由此形成話題維網(wǎng)絡(luò)X2。具體的計算過程如圖1偽代碼所示。

圖1 話題維向量網(wǎng)絡(luò)計算偽代碼

3.3 劃分領(lǐng)域

為了計算領(lǐng)域影響力最大化，首先需要從異質(zhì)性社交網(wǎng)絡(luò)X1、X2中發(fā)現(xiàn)不同的領(lǐng)域。眾多聚類算法中，有關(guān)實驗表明譜聚類在社交網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)中具有較穩(wěn)定和高效的表現(xiàn)。譜聚類算法源于圖形分割問題，主要工具是圖像的Laplacian矩陣。

令W表示每維社交網(wǎng)絡(luò)X1、X2相似度矩陣的加權(quán)鄰接矩陣，D表示相應(yīng)的度數(shù)矩陣，I表示原矩陣，Laplacian矩陣L被定義為式(1)。

本文使用normalizedcut并計算L矩陣的前k個特征向量，從而將維度由n維降至k維。社交關(guān)系維X1，話題維X2分別產(chǎn)生一個Laplacian矩陣L1, L2。進一步，使用Lei等人[13]提出的utility integration方法將這三維網(wǎng)絡(luò)加和，平均效用矩陣可由式(2)獲得。

其中對譜聚類算法而言，效用矩陣M等價于Laplacian矩陣，即

由式(1)～式(3)可以推導出平均Laplacian矩陣

3.4 領(lǐng)域影響力最大化

如前文所述，病毒營銷已經(jīng)成為信息時代常見的營銷手段之一。它的低成本和高覆蓋率已經(jīng)得到越來越多人的關(guān)注。然而成本再低終歸是有成本的，比如一家食品公司為了推廣某項新產(chǎn)品準備先給一部分客戶免費品嘗或體驗，如何優(yōu)化選取這批初始用戶，使得總成本落在預算以內(nèi)同時盡可能最大化人們口耳相傳的覆蓋面，就是典型的影響力最大化問題。為了便于后文討論，首先來形式化地定義影響力最大化問題。

給定社交網(wǎng)絡(luò)G和種子數(shù)目k,對于給定的一種影響力傳播模型，選取k個節(jié)點構(gòu)成的初始活躍節(jié)點集S使得σ(S)最大。其中σ()是給定的影響力函數(shù)。

Kempe等人[1]最早提出了兩種基礎(chǔ)的影響力傳播模型： 獨立級聯(lián)(independent cascade)和線性閾值(linear threshold)。為便于與同類工作比較，本文采用線性閾值模型，其核心特點在于對每個節(jié)點用一個閾值來表示該用戶被影響的難易程度。當它的鄰居節(jié)點累計給這個節(jié)點的影響概率之后超過閾值后，該節(jié)點即被激活(認為被影響到)。其傳播過程如下所述。

在討論全局影響力最大化之前，首先來看在一個領(lǐng)域內(nèi)的影響力最大化。其實這個問題跟之前眾多研究關(guān)注的全局網(wǎng)絡(luò)的影響力最大化是同一個問題?？梢圆捎闷渲腥我庖粋€現(xiàn)成的算法。為了便于后續(xù)討論同時有效地說明問題，本文即采用最基礎(chǔ)的貪心算法來尋找待求的K個種子。貪心近似算法(greedy approximation algorithm)[1]借用子模函數(shù)的性質(zhì)，重復k次每次選取使得函數(shù)σ(S)增量最大的節(jié)點，并將它放入解集中。具體的偽代碼如圖2所示。

圖2 單個領(lǐng)域內(nèi)影響力最大化的貪心算法

Yu[7]等人在基于社區(qū)發(fā)現(xiàn)的影響力最大化研究中提出了一種動態(tài)規(guī)劃算法來計算第i步(0

(1)n=k。

領(lǐng)域個數(shù)與種子個數(shù)相等，則直接在各個領(lǐng)域?qū)ふ矣绊懥瘮?shù)σ(S)增量最大的節(jié)點。

(2)n>k

領(lǐng)域個數(shù)比種子個數(shù)多，則直接在規(guī)模最大的前k個領(lǐng)域?qū)ふ矣绊懥瘮?shù)σ(S)增量最大的節(jié)點。

(3)n

領(lǐng)域個數(shù)比種子個數(shù)少，則首先在各個領(lǐng)域?qū)ふ矣绊懥瘮?shù)σ(S)增量最大的節(jié)點。剩余的k-n個節(jié)點套用文獻[7]中的動態(tài)規(guī)劃算法求解。遞推如式(5)所示。

實驗表明，這種貪心選取領(lǐng)域的算法結(jié)合基于領(lǐng)域的影響力最大化計算模型極大地降低了運算時間，同時與直接在全局網(wǎng)絡(luò)上求解結(jié)果的差異性很小。具體實驗結(jié)果將在4.4節(jié)進行討論。

4 實驗

4.1 數(shù)據(jù)集

本實驗基于中國流行的社交網(wǎng)站——新浪微博(http://weibo.com)。首先從不同行業(yè)人工選取了大約50個中層用戶(約幾千粉絲數(shù))，并爬取他們的1層關(guān)注列表和粉絲列表，去重后得到185 504個用戶，并爬取每個用戶最近的100條微博。為了避免來自僵尸用戶和極端不活躍用戶帶來的噪聲，本文對數(shù)據(jù)集進行了五層過濾，最終得到108 204個用戶構(gòu)成的穩(wěn)定社區(qū)和超過一千萬條的微博信息。這五層過濾是：

(1) 個人信息頁面當時無法獲取的用戶；

(2) 擁有少于10個關(guān)注對象的用戶；

(3) 擁有少于30個粉絲的用戶；

(4) 擁有少于5條微博的用戶；

(5) 在截取的社區(qū)中擁有過少聯(lián)系人的用戶(即孤立點)。

4.2 話題維網(wǎng)絡(luò)

經(jīng)過Twitter-LDA對微博內(nèi)容的處理，得到了20個話題的常見代表詞和每個詞語在每個話題上的概率分布值。圖3是節(jié)選的一部分話題詞表。容易看到話題1主要圍繞做飯，話題2主要關(guān)于藝術(shù)，話題3關(guān)于軟件，話題4關(guān)于經(jīng)濟。

圖3 話題維網(wǎng)絡(luò)結(jié)果

4.3 劃分領(lǐng)域

整合社交關(guān)系維度和話題維的網(wǎng)絡(luò)后，本文對該異質(zhì)性網(wǎng)絡(luò)分別按5類、10類、15類進行聚類。比較后采用10類(即10個領(lǐng)域)的結(jié)果進行后續(xù)分析。圖4為10類聚類結(jié)果中每類用戶總數(shù)占總體的百分比即10領(lǐng)域占比圖。

圖4 10領(lǐng)域占比圖

4.4 影響力最大化

本文分別選取不同的種子用戶集合大小k，來測量不同模型下的影響力傳播范圍和時間消耗。第一個模型是經(jīng)典的全網(wǎng)絡(luò)貪心算法(簡稱貪心模型)[1]，第二個是Yu[7]等人提出的基于社區(qū)發(fā)現(xiàn)的影響力最大化模型(簡稱社會發(fā)現(xiàn)模型)，最后一個就是本文的領(lǐng)域影響力最大化模型(簡稱領(lǐng)域模型)。

圖5展示了三種模型在不同初始集合大小k取值情況下的時間消耗，經(jīng)典的貪心模型由于其指數(shù)時間復雜度的特點，從k=10的數(shù)據(jù)點起已超過坐標軸的范圍，相比之下，社區(qū)發(fā)現(xiàn)模型和領(lǐng)域模型具有較好的時間表現(xiàn)，除k=20這組實驗外，領(lǐng)域模型均小范圍領(lǐng)先社區(qū)發(fā)現(xiàn)模型的時間代價。

圖5 三種模型的時間消耗

圖6 三種模型的覆蓋節(jié)點數(shù)

圖6展示了LT模型下種子集最終覆蓋的用戶群體大小，經(jīng)典的貪心模型以極高的時間復雜度為代價換來了更大的覆蓋量，不過社區(qū)發(fā)現(xiàn)模型與領(lǐng)域模型最終覆蓋的用戶與之相差并不大。領(lǐng)域模型以更低的時間代價獲取了與社區(qū)發(fā)現(xiàn)模型基本一致的覆蓋范圍。

5 結(jié)論

影響力研究一直是社會計算領(lǐng)域的一項基礎(chǔ)性研究，除了影響力本身的特征吸引了大量關(guān)注外，對信息傳播和病毒營銷有重要參考意義的影響力最大化研究也同樣備受關(guān)注。然而傳統(tǒng)的IM問題研究工作大多局限在對Kempe等人[1]最早提出的貪心算法的改良，從更少的時間代價換取更高的精度。近年來也有個別研究者另辟蹊徑，有的從結(jié)構(gòu)角度通過社交關(guān)系的社區(qū)發(fā)現(xiàn)來在子社區(qū)最大化影響力傳播，另一個思路則是從內(nèi)容維度分析話題影響力的傳播。雖然都有顯著的效果，但也缺乏對社交網(wǎng)絡(luò)中豐富的結(jié)構(gòu)和內(nèi)容維度的異質(zhì)性信息的充分利用。

本文提出一種基于領(lǐng)域的影響力最大化模型，首先對社交網(wǎng)絡(luò)中的結(jié)構(gòu)信息和內(nèi)容信息進行預處理： 前者轉(zhuǎn)換成一個由“是否關(guān)注對方”構(gòu)成的0/1矩陣；后者則首先對用戶微博內(nèi)容進行分詞和Twitter-LDA主題模型處理，從而得到每個用戶在無監(jiān)督學習出的20個話題上的向量維度值。隨后使用效用整合方法將兩個矩陣結(jié)合，并調(diào)用譜聚類算法將用戶劃分到不同的領(lǐng)域。最后，利用一種貪心-動態(tài)規(guī)劃混合的算法來選取IM問題中的第k個初始節(jié)點應(yīng)當選取的領(lǐng)域并確定實際的對象。

基于新浪微博10萬多用戶社交關(guān)系與微博內(nèi)容構(gòu)成的新浪微博數(shù)據(jù)集的實驗效果表明，領(lǐng)域影響力最大化模型相比傳統(tǒng)影響力模型具有極低的時間代價，并具有很高的精度。

雖然劃分領(lǐng)域的做法符合人們社會生活中和網(wǎng)上社交中的行為特點，然而另一方面由于人們興趣和專業(yè)知識的多樣性，一個用戶歸屬于一個領(lǐng)域的實驗假設(shè)難免有違實際。如何將本文的領(lǐng)域影響力最大化模型推廣到有重疊領(lǐng)域的情況將會是一個非常有趣的研究方向。

[1] D Kempe, J Kleinberg, E Tardos. Maximizing the spread of influence through a social network[C]//Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York: ACM, 2003: 137-146 .

[2] J Leskovec, et al. Cost-effective outbreak detection in networks[C]//Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York: ACM, 2007: 420-429.

[3] W Chen, C Wang, Y Wang. Scalable influence maximization for prevalent viral marketing in large-scale social networks[C]//Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York: ACM, 2010: 1029-1038.

[4] M Gomez Rodriguez, B Scholkopf. Influence Maximization in Continuous Time Diffusion Networks[C]//Proceedings of the 29th International Conference on Machine Learning, New York: Omnipress , 2012.

[5] Y Li, W Chen, Y Wang, Z Zhang. Influence Diffusion Dynamics and Influence Maximization in Social Networks with Friend and Foe Relationships[C]//Proceedings of the 6th ACM International Conference on Web Search and Data Mining, New York: ACM,2013.

[6] W Chen, Y Wang, S Yang. Efficient influence maximization in social networks[C]//Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York: ACM,2009: 199-208.

[7] Y Wang, G Cong, G Song, K Xie. Community-based Greedy Algorithm for Mining Top-K Influential Nodes in Mobile Social Networks.[C]//Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York: ACM, 2010: 1039-1048.

[8] N Barbieri, F Bonchi, G Manco. Topic-aware social influence propagation models[J]. Knowledge and information systems,2013,37(3):555-584.

[9] C Aslay, N Barbieri, F Bonchi, R Baeza-Yates. Online topic-aware influence maximization queries[C]//Proceedings of the 17th International Conference on Extending Database Technology,2014.

[10] W Chen, T Lin, C Yang. Efficient Topic-aware Influence Maximization Using Preprocessing[J].The Computing Research Repository, volume abs/1403.0057, 2014 .

[11] Q Liu, C Wang, M Zhang. Measuring Domain Influence in Heterogeneous Networks[C]//Proceedings of the of the 7th ACM International Conference on Web Search and Data Mining works, New York: ACM,2014.

[12] W Zhao, J Jiang, J Weng, et al. Comparing twitter and traditional media using topic models[C]//Proceedings of the 32nd European Conference on IR Research, Heidelberg: Springerpages,2011 , 338-349.

[13] L Tang, X Wang, H Liu. Community detection via heterogeneous interaction analysis[J]. Data Mining and Knowledge Discovery, 2012,25(1):1-33.

DomainBasedInfluenceMaximizationandViralMarketing

LIU Quan, ZHANG Ming

(School of EECS,Peking University, Beijing 100871,China)

With the evolvement of social media like Sina Weibo and Renren, online influence maximization has attracted more and more attention from both industry and research institutions. It’s very crucial for the healthy development of marketing strategies like viral marketing to maximize the influence scope given the constraints of resources. If we can specify the domain that a user belongs to more accurately with the heterogeneous information from social networks, and further maximize influence spread based on domains, traditional influence research from the general perspective as well as single perspective of structure or content will be hugely benefitted. In this paper we proposed a domain influence maximization model, which first divided users into different domains utilizing users’ social relations and weibo contents, and then maximized domain influence based on a greedy-dp hybrid algorithm. Experiments on Sina Weibo show that our model greatly improved the time cost of traditional models, with little errors.

influence maximization; domain discovery; domain influence

劉泉(1992—)，學士，主要研究領(lǐng)域為數(shù)據(jù)挖掘和社交計算。

張銘(1966—)，通信作者，教授，博士生導師，主要研究領(lǐng)域為文本挖掘、社會網(wǎng)絡(luò)分析、大規(guī)模在線教育研究等。

1003-0077(2017)03-0118-07

2014-12-27定稿日期： 2015-02-24

國家自然科學基金(61472006，91646202)

TP391

： A