基于領域的影響力最大化與病毒營銷

劉 泉，張 銘

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

基于領域的影響力最大化與病毒營銷

劉 泉，張 銘

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

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

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

1 引言

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

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

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

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

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

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

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

2 相關工作

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

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

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

3 模型

3.1 異質性網絡

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

本文的異質性網絡同時利用了結構信息和內容信息，即判別給定的兩個用戶是否應當劃分到同一個領域中，主要可以根據以下兩點判別。

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

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

3.2 話題維網絡

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

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

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

圖1 話題維向量網絡計算偽代碼

3.3 劃分領域

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

令W表示每維社交網絡X1、X2相似度矩陣的加權鄰接矩陣，D表示相應的度數矩陣，I表示原矩陣，Laplacian矩陣L被定義為式(1)。

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

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

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

3.4 領域影響力最大化

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

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

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

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

圖2 單個領域內影響力最大化的貪心算法

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

(1)n=k。

領域個數與種子個數相等，則直接在各個領域尋找影響力函數σ(S)增量最大的節(jié)點。

(2)n>k

領域個數比種子個數多，則直接在規(guī)模最大的前k個領域尋找影響力函數σ(S)增量最大的節(jié)點。

(3)n

領域個數比種子個數少，則首先在各個領域尋找影響力函數σ(S)增量最大的節(jié)點。剩余的k-n個節(jié)點套用文獻[7]中的動態(tài)規(guī)劃算法求解。遞推如式(5)所示。

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

4 實驗

4.1 數據集

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

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

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

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

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

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

4.2 話題維網絡

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

圖3 話題維網絡結果

4.3 劃分領域

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

圖4 10領域占比圖

4.4 影響力最大化

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

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

圖5 三種模型的時間消耗

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

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

5 結論

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

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

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

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

[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—)，學士，主要研究領域為數據挖掘和社交計算。

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

1003-0077(2017)03-0118-07

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

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

TP391

： A