劉業(yè)政 李玲菲 姜元春

?

社會(huì)化營銷績效最大化問題及其擴(kuò)展研究綜述

劉業(yè)政 李玲菲 姜元春*

(合肥工業(yè)大學(xué)管理學(xué)院 合肥 230009)

由于在線社交網(wǎng)絡(luò)上的信息傳播具有速度快、成本低、影響范圍大等優(yōu)勢，許多企業(yè)均試圖通過在線社交網(wǎng)絡(luò)進(jìn)行產(chǎn)品的促銷和推廣。然而，企業(yè)如何選擇種子結(jié)點(diǎn)來投放營銷信息，使得在給定成本下覆蓋或影響最多的用戶，實(shí)現(xiàn)營銷績效最大化是一項(xiàng)極具挑戰(zhàn)性的任務(wù)。該文通過文獻(xiàn)檢索和綜述方法，系統(tǒng)總結(jié)了社會(huì)化營銷中的信息傳播模型，從網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和用戶歷史數(shù)據(jù)、競爭條件與非競爭條件等不同視角總結(jié)了社會(huì)化營銷績效最大化的有關(guān)算法，最后對(duì)社會(huì)化營銷績效最大化問題進(jìn)行了總結(jié)與展望。

在線社交網(wǎng)絡(luò)；社會(huì)化營銷；績效最大化

1 引言

在線社交網(wǎng)絡(luò)中的信息一經(jīng)發(fā)布，便會(huì)自發(fā)地通過社交網(wǎng)絡(luò)中好友的瀏覽、轉(zhuǎn)發(fā)、評(píng)論等行為擴(kuò)散開來，其中部分信息還能夠迅速傳播，短時(shí)間內(nèi)覆蓋社交網(wǎng)絡(luò)中眾多用戶，從而成為討論的熱點(diǎn)。由于人們傾向于信任他們的朋友、家人、同事等親密的社會(huì)關(guān)系所發(fā)送的信息，與電視等傳統(tǒng)營銷平臺(tái)相比，在線社交網(wǎng)絡(luò)中的信息更容易被用戶所接受。這種傳播速度快、營銷成本低、影響范圍大的信息傳播模式極大地吸引著企業(yè)的關(guān)注。許多企業(yè)均試圖通過在線社交網(wǎng)絡(luò)進(jìn)行產(chǎn)品的促銷和推廣。他們希望通過某種激勵(lì)方式吸引一部分用戶(種子節(jié)點(diǎn))發(fā)布自己產(chǎn)品的營銷信息，利用個(gè)體間的口口相傳(word of mouth)，使產(chǎn)品的口碑在網(wǎng)絡(luò)中像病毒一樣迅速蔓延，達(dá)到產(chǎn)品推廣的效果。然而企業(yè)用于營銷的預(yù)算是有限的，如何選擇種子結(jié)點(diǎn)來投放營銷信息，使得在給定成本下覆蓋或影響最多的用戶實(shí)現(xiàn)社會(huì)化營銷績效最大化是一項(xiàng)極具挑戰(zhàn)性的任務(wù)。近年來，Nature 和Science 期刊以及管理科學(xué)、市場營銷等領(lǐng)域的國際頂級(jí)期刊上發(fā)表了眾多論文對(duì)此類問題進(jìn)行了探討，取得了大量有價(jià)值的成果，本文將對(duì)相關(guān)重要研究成果進(jìn)行系統(tǒng)地綜述，并在此基礎(chǔ)上對(duì)未來研究趨勢做進(jìn)一步展望。

社會(huì)化營銷績效最大化問題是Kempe等人[15]提出的影響力最大化問題在營銷領(lǐng)域的具體表現(xiàn)和延伸，目標(biāo)是要在給定成本下找到一個(gè)種子節(jié)點(diǎn)的集合來投放營銷信息，使其能影響的節(jié)點(diǎn)總數(shù)的期望最大?，F(xiàn)有研究均假定激活任意節(jié)點(diǎn)為種子節(jié)點(diǎn)所付出的代價(jià)相同，此時(shí)在給定成本約束下種子節(jié)點(diǎn)的數(shù)量就是一個(gè)常數(shù)，因此研究成果集中于信息傳播模型的構(gòu)建以及在不同的信息傳播模型下如何尋找這個(gè)種子節(jié)點(diǎn)，本文稱此類問題為社會(huì)化營銷績效最大化基本問題。近年來，一些研究對(duì)社會(huì)化營銷績效最大化基本問題進(jìn)行了延伸與擴(kuò)展，引入了用戶歷史數(shù)據(jù)、競爭關(guān)系、時(shí)間限制等條件。本文以社會(huì)化營銷績效最大化基本問題為切入點(diǎn)，逐步將問題延伸與擴(kuò)展，形成一個(gè)較完整的社會(huì)化營銷績效最大化問題研究體系。

社會(huì)化營銷績效最大化基本問題主要研究兩個(gè)內(nèi)容：構(gòu)建信息傳播模型與求解社會(huì)化營銷績效最大化基本問題。在信息傳播模型方面，最為經(jīng)典的是獨(dú)立級(jí)聯(lián)模型以及線性閾值模型[15]，隨后雖然有新的傳播模型被提出，但絕大多數(shù)模型都是在這兩個(gè)模型的基礎(chǔ)上進(jìn)行改進(jìn)或簡化。在問題求解方面，Domingos 和 Richardson[16,17]首先進(jìn)行了研究，隨后Kempe等人[15]將其看成是離散優(yōu)化問題，提出自然爬山的貪心算法求解。貪心算法能給出結(jié)果的近似度，但是它固有的局限性使其難以擴(kuò)展到大規(guī)模的網(wǎng)絡(luò)中去，由此引出了另一個(gè)研究分支：啟發(fā)式算法。啟發(fā)式算法雖然不能給出結(jié)果的近似度，但它計(jì)算上十分高效，且仿真實(shí)驗(yàn)的結(jié)果表明它與貪心算法具有基本相似的影響范圍[18]。

上述算法僅僅基于網(wǎng)絡(luò)結(jié)構(gòu)本身進(jìn)行求解，但在真實(shí)的社交網(wǎng)絡(luò)中，除了網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)外，還存在大量用戶產(chǎn)生的文本信息以及用戶交互信息。通過分析這些歷史數(shù)據(jù)，可以知道用戶的興趣偏好，了解用戶間聯(lián)系的緊密程度。這些信息一方面能幫助我們找出對(duì)產(chǎn)品感興趣的用戶，從而使產(chǎn)品的推廣更具有針對(duì)性及有效性；另一方面也能幫助我們更好地理解社交網(wǎng)絡(luò)中信息傳播機(jī)制，構(gòu)建更為精準(zhǔn)的信息傳播模型，從而求解社會(huì)化營銷績效最大化問題。

隨著研究的進(jìn)一步深入，社會(huì)化營銷績效最大化基本問題在描述真實(shí)營銷情況中的局限性也慢慢地顯露出來。首先，網(wǎng)絡(luò)中存在各種形式的競爭關(guān)系；其次，網(wǎng)絡(luò)中的營銷并不是無限制的，它要受到營銷時(shí)間等條件的約束。為了更好地模擬上述現(xiàn)象，一些研究人員從營銷的視角對(duì)社會(huì)化營銷績效最大化基本問題進(jìn)行了延伸與擴(kuò)展。本文從競爭與非競爭兩個(gè)角度對(duì)其進(jìn)行詳細(xì)闡述。

社會(huì)化營銷績效最大化問題包含豐富的研究內(nèi)容，本文從信息傳播的基本模型出發(fā)，總結(jié)了近年來相關(guān)研究成果。文章的結(jié)構(gòu)如下：第2節(jié)介紹基本的信息傳播模型；第3節(jié)介紹求解社會(huì)化營銷績效最大化基本問題的一些算法，包括貪心算法與啟發(fā)式算法；第4節(jié)介紹基于用戶歷史數(shù)據(jù)的社會(huì)化營銷績效最大化問題；第5、第6節(jié)分別介紹了競爭與非競爭條件下的社會(huì)化營銷績效最大化問題；最后對(duì)社會(huì)化營銷績效最大化問題進(jìn)行了總結(jié)與展望。

2 基本的信息傳播模型

研究者們從不同的視角提出了眾多模型來描述信息傳播過程，這些模型可以分為3類：基于網(wǎng)絡(luò)結(jié)構(gòu)的傳播模型，如獨(dú)立級(jí)聯(lián)模型[15]、線性閾值模型[19]；基于信息特性的傳播模型，如考慮外部影響的傳播模型[20]；以及基于群體狀態(tài)的傳播模型，如傳染病模型[21]、線性影響力模型[22]。由于社會(huì)化營銷績效最大化問題中構(gòu)建傳播模型是希望用該模型模擬信息的級(jí)聯(lián)以獲得種子節(jié)點(diǎn)發(fā)布的信息所影響的用戶數(shù)目，基于網(wǎng)絡(luò)結(jié)構(gòu)的傳播模型在該問題誕生之初被提出并得到了廣泛的運(yùn)用，時(shí)至今日仍然是社會(huì)化營銷績效最大化問題中信息傳播的主流模型。本文對(duì)其進(jìn)行簡單總結(jié)。

2.1獨(dú)立級(jí)聯(lián)模型(Independent Cascade model, IC模型)

IC模型最早由Goldenberg等人[23,24]在營銷的背景下提出，由Kempe等人[15]正式定義。IC模型與傳染病傳播模型SIR[21]類似，模型的具體描述如下：

2.2線性閾值模型(Linear Treshold model, LT模型)

IC模型認(rèn)為節(jié)點(diǎn)的影響是獨(dú)立的，但Watts等人[19]認(rèn)為影響力的作用應(yīng)該是累積的，即當(dāng)個(gè)體不斷被某條信息影響時(shí)，個(gè)體對(duì)該信息的接受度將逐漸增強(qiáng)，據(jù)此Watts等人[19]提出LT模型。LT模型的具體描述如下：

2.3其他模型

除了上述基本模型外，研究者們還提出了許多模型來描述社交網(wǎng)絡(luò)中信息的傳播。級(jí)聯(lián)模型[15]與閾值模型[15]是IC模型與LT模型的一般化，且這兩個(gè)模型是等價(jià)的；觸發(fā)模型[15]為每個(gè)節(jié)點(diǎn)引入觸發(fā)集來表示能夠成功影響該節(jié)點(diǎn)的鄰居節(jié)點(diǎn)的集合；加權(quán)級(jí)聯(lián)模型[15]定義任意節(jié)點(diǎn)的入度為，并假設(shè)節(jié)點(diǎn)被任意鄰居激活的概率為；遞減級(jí)聯(lián)模型[25]假設(shè)節(jié)點(diǎn)被感染的概率隨著嘗試感染但失敗的次數(shù)是遞減的；邊過濾模型[26]以及最短路徑模型[27]簡化了IC模型的部分操作；選舉模型[28]能夠模擬用戶觀點(diǎn)隨著交互不斷改變的現(xiàn)象；熱傳導(dǎo)模型[29]則將物理學(xué)中的熱傳導(dǎo)現(xiàn)象應(yīng)用于社交網(wǎng)絡(luò)的信息擴(kuò)散中。

上述模型大多是將解釋其他領(lǐng)域的擴(kuò)散現(xiàn)象的模型應(yīng)用在社交網(wǎng)絡(luò)信息傳播中，但信息本身的傳播規(guī)律可能與這些模型不同。許多學(xué)者試圖通過在真實(shí)網(wǎng)絡(luò)中進(jìn)行大規(guī)模的實(shí)驗(yàn)找出信息傳播與網(wǎng)絡(luò)結(jié)構(gòu)之間的關(guān)系。如何合理應(yīng)用這些研究成果，找出更好的模型來擬合真實(shí)的信息傳播現(xiàn)象仍是待解決的問題。

3 社會(huì)化營銷績效最大化基本問題求解

求解社會(huì)化營銷績效最大化基本問題的方法主要分為兩類：一類是貪心算法；另一類為啟發(fā)式算法。

3.1貪心算法

社會(huì)化營銷績效最大化基本問題在IC模型和LT模型下都是NP難的[15,33,34]，因此很難求得最優(yōu)解。但是在IC模型和LT模型下，目標(biāo)函數(shù)單調(diào)遞增且具有子模性，即若節(jié)點(diǎn)集，那么對(duì)于圖中任意節(jié)點(diǎn)，有

根據(jù)離散優(yōu)化問題的相關(guān)知識(shí)[35]，用貪心算法求解具有子模性的離散優(yōu)化問題所得的解以近似最優(yōu)解，即算法的精度能略高于63%。因此，Kempe等人[15]提出自然爬山的貪心算法。該算法以IC模型或LT模型作為信息傳播模型，設(shè)種子集初始為空集，在第輪迭代中計(jì)算每個(gè)節(jié)點(diǎn)的邊際營銷績效，并找出邊際營銷績效最大的節(jié)點(diǎn)作為種子節(jié)點(diǎn)。的計(jì)算是#P難的，Kempe采用MC方法對(duì)同一節(jié)點(diǎn)集多次模擬求平均值來近似該節(jié)點(diǎn)集的績效，這使得該算法時(shí)間復(fù)雜度很高。

為提高貪心算法的效率，Leskovec等人[36]提出使用“Lazy-Forward”優(yōu)化的CELF算法，該算法利用子模性在每輪迭代中只估計(jì)了部分最可能的候選節(jié)點(diǎn)的邊際營銷績效。Goyal等人[37]改進(jìn)了CELF算法，提出CELF++算法，實(shí)驗(yàn)表明，CELF++比CELF快35%~55%。Chen等人[18]為有效減少IC模型中邊的篩選次數(shù)提出NewGreedy與MixGreedy算法?？紤]到社交網(wǎng)絡(luò)中像社區(qū)這樣的特殊結(jié)構(gòu)[38]能夠影響信息的傳播，Wang等人[39]提出基于社區(qū)的貪心算法CGA。CGA算法使用標(biāo)簽傳播算法以及組合熵來發(fā)現(xiàn)社區(qū)，隨后用動(dòng)態(tài)規(guī)劃算法尋找種子節(jié)點(diǎn)。Song等人[40]則將CGA算法并行化處理提出PCA算法。

2014年，Borgs等人[41]在貪心算法的改進(jìn)上取得了突破性的進(jìn)展。Borgs等人基于IC模型提出先構(gòu)造超圖再構(gòu)造種子集的反向影響力抽樣算法RIS，該算法通過少量循環(huán)找到種子節(jié)點(diǎn)，實(shí)現(xiàn)了社會(huì)化營銷績效最大化基本問題的常系數(shù)近似。注意到RIS算法的時(shí)間復(fù)雜度中存在許多隱藏的常系數(shù)，Tang等人[42]提出TIM算法。該算法沿用了RIS的思想，只是在超圖構(gòu)造前計(jì)算出了超邊的數(shù)量。考慮到TIM算法中種子節(jié)點(diǎn)的可擴(kuò)展性差，Cohen等人[43]提出了SKIM算法，該算法改進(jìn)了算法構(gòu)造種子集階段，實(shí)驗(yàn)證明SKIM算法可以擴(kuò)展到存在數(shù)以億計(jì)的邊的網(wǎng)絡(luò)。

上述主要貪心算法的時(shí)間復(fù)雜度與算法的近似度如表1所示。

表1貪心算法的時(shí)間復(fù)雜度與近似度

貪心算法最大的優(yōu)勢是能給出算法的近似度，使得營銷效果有了保障。但是由于計(jì)算任意節(jié)點(diǎn)的績效本身就是#P難的，貪心算法的時(shí)間復(fù)雜度往往較高，難以擴(kuò)展到大規(guī)模的網(wǎng)絡(luò)中。

3.2啟發(fā)式算法

考慮到貪心算法固有局限性使得時(shí)間復(fù)雜度難以下降，研究者開始將目光轉(zhuǎn)向更為高效的啟發(fā)式算法。2009年Chen等人[18]提出度折扣的啟發(fā)式算法DegreeDiscountIC，認(rèn)為如果某一節(jié)點(diǎn)的鄰居節(jié)點(diǎn)為種子節(jié)點(diǎn)，在計(jì)算該點(diǎn)的營銷績效時(shí)應(yīng)該相應(yīng)地“打折”。該算法具有與貪心算法相似的效果，且時(shí)間復(fù)雜度要快近6個(gè)數(shù)量級(jí)。由此Chen等人指出雖然啟發(fā)式算法不能給出算法的精度，但在面對(duì)大規(guī)模網(wǎng)絡(luò)時(shí)，啟發(fā)式算法將會(huì)是更有希望的算法。

一般圖中由于環(huán)的存在，計(jì)算節(jié)點(diǎn)在IC及LT模型下的績效是#P難的，但在樹中計(jì)算節(jié)點(diǎn)的績效只需線性時(shí)間。為此Chen等人提出針對(duì)IC模型的最大子樹模型MIA[33]與PMIA[44]，以及針對(duì)LT模型的LDAG[34]算法。這些算法通過為每個(gè)節(jié)點(diǎn)構(gòu)造基于最大影響路徑的局部樹狀結(jié)構(gòu)或局部有向無環(huán)圖(LDAG)來近似節(jié)點(diǎn)的信息傳播區(qū)域，隨后使用貪心策略求解。

由于LDAG算法[34]存在有向無環(huán)圖構(gòu)造困難、忽略過多傳播路徑、內(nèi)存占用率大等問題，Goyal等人[45]在CELF算法的基礎(chǔ)上提出針對(duì)LT模型的SIMPATH算法。SIMPATH通過節(jié)點(diǎn)鄰域內(nèi)的簡單路徑估計(jì)節(jié)點(diǎn)信息傳播范圍，使用節(jié)點(diǎn)覆蓋最優(yōu)化減少算法第1輪迭代中的查詢次數(shù)，并提出前瞻優(yōu)化方法提高節(jié)點(diǎn)績效的估計(jì)速率。另一邊，IRIE算法[46]舍棄節(jié)點(diǎn)績效值的估計(jì)，轉(zhuǎn)而提出績效排序算法IR，并結(jié)合績效估計(jì)方法IE，通過求解一系列的線性方程組來估計(jì)節(jié)點(diǎn)的邊際營銷績效。

部分啟發(fā)式算法的時(shí)間復(fù)雜度見表2。

表2部分啟發(fā)式算法的時(shí)間復(fù)雜度

除了上述通過改進(jìn)貪心算法獲得啟發(fā)解的方法之外，構(gòu)建新的網(wǎng)絡(luò)結(jié)構(gòu)特征變量[10,47]、博弈論[48]、群體智能[49]、并行計(jì)算[50]等方法也被用于社會(huì)化營銷績效最大化問題的求解。

由于計(jì)算上的高效，啟發(fā)式算法在處理大規(guī)模網(wǎng)絡(luò)時(shí)具有極大的優(yōu)勢，但它的精度無法保證。然而對(duì)于企業(yè)來說，營銷方案的可靠性往往決定了企業(yè)是否會(huì)投入相應(yīng)的成本，這也成為啟發(fā)式算法真正應(yīng)用到實(shí)際中的一大瓶頸。

4 基于用戶歷史數(shù)據(jù)的社會(huì)化營銷績效最大化問題

上述方法都關(guān)注于網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，卻忽略了歷史數(shù)據(jù)，如個(gè)體間的交互情況、信息傳播記錄、信息的內(nèi)容等。利用用戶間交互的頻率預(yù)測用戶間親密程度，通過用戶發(fā)布的信息推斷用戶的偏好可以幫助我們更好地鎖定目標(biāo)客戶、模擬真實(shí)傳播行為，從而求得更為精確的解。

4.1基于用戶活動(dòng)日志的社會(huì)化營銷績效最大化問題

考慮這樣一個(gè)問題：如果兩個(gè)節(jié)點(diǎn)間信息傳播概率的估計(jì)與現(xiàn)實(shí)情況不同，那么算法的結(jié)果還可信嗎？模型穩(wěn)定性的相關(guān)研究[51,52]發(fā)現(xiàn)，影響概率的擾動(dòng)會(huì)導(dǎo)致明顯的不穩(wěn)定性，因此使傳播概率盡量貼合真實(shí)網(wǎng)絡(luò)就變得十分重要。傳統(tǒng)的信息傳播模型顯然沒能很好地解決這一問題，一個(gè)可行的辦法是結(jié)合用戶活動(dòng)日志定義節(jié)點(diǎn)間的傳播概率。

Saito等人[53]首先研究了這一問題，并將該問題轉(zhuǎn)化為最大似然問題，使用EM算法求解。但該算法不能適用于大型網(wǎng)絡(luò)。Goyal等人[54]通過用戶間相互影響的歷史數(shù)據(jù)，提出3種模型計(jì)算邊的傳播概率：靜態(tài)模型、連續(xù)時(shí)間模型以及離散時(shí)間模型。隨后Goyal等人[55]比較了不同概率學(xué)習(xí)方法下選擇出的種子節(jié)點(diǎn)，證實(shí)利用用戶活動(dòng)日志獲得的種子節(jié)點(diǎn)比傳統(tǒng)方法下獲得的種子節(jié)點(diǎn)質(zhì)量更高。進(jìn)一步地，Goyal等人[55]提出信用分布模型，利用用戶活動(dòng)日志計(jì)算節(jié)點(diǎn)間的影響信用，從而預(yù)測節(jié)點(diǎn)集的期望影響范圍，并據(jù)此求解社會(huì)化營銷績效最大化問題。

4.2基于信息內(nèi)容的社會(huì)化營銷績效最大化問題

用戶具有不同的興趣，產(chǎn)品具有不同的特征，而相似的商品更可能會(huì)吸引相同的用戶，這說明產(chǎn)品的推廣效果與產(chǎn)品本身的特征密切相關(guān)。社會(huì)學(xué)的研究已經(jīng)表明，不同的話題所產(chǎn)生的社會(huì)影響力的效果通常是不同的[56,57]，為此需要將產(chǎn)品特征以及用戶興趣相結(jié)合，有針對(duì)性地進(jìn)行社會(huì)化營銷。

研究人員通過用戶發(fā)布的信息內(nèi)容挖掘用戶的興趣，據(jù)此研究不同信息在網(wǎng)絡(luò)中的傳播情況，并求解基于話題的社會(huì)化營銷績效最大化問題。其中文獻(xiàn)[58-60]通過不同的方法獲得了用戶間基于話題的影響力強(qiáng)度，但沒有定義信息傳播模型，也沒有求解社會(huì)化營銷績效最大化問題。Barbieri等人[62]提出基于話題的獨(dú)立級(jí)聯(lián)模型TIC和線性閾值模型TLT，并使用極大似然估計(jì)方法來估計(jì)TIC模型的參數(shù)。隨后用主題建模的思想得到信息傳播模型AIR，并提出GEM方法學(xué)習(xí)AIR模型的參數(shù)。該模型在描述真實(shí)網(wǎng)絡(luò)方面更準(zhǔn)確。Aslay等人[63]與Chen等人[64]在Barbieri等人[62]的基礎(chǔ)上研究了基于話題的社會(huì)化營銷績效最大化問題。通過不同的預(yù)處理方法，在新的信息到達(dá)后快速求解相應(yīng)的種子節(jié)點(diǎn)。

基于用戶歷史數(shù)據(jù)研究社會(huì)化傳播績效最大化問題可以更好地模擬真實(shí)網(wǎng)絡(luò)中的情況，從而獲得更為精確的解，但數(shù)據(jù)的獲取并不容易，且計(jì)算更為復(fù)雜。

5 競爭條件下的社會(huì)化營銷績效最大化問題

無論是在線上營銷還是線下營銷，企業(yè)都會(huì)不可避免地遇到這樣一些問題：當(dāng)某些突發(fā)性事件給企業(yè)帶來負(fù)面新聞時(shí)企業(yè)該如何面對(duì)？當(dāng)不同企業(yè)在同一市場展開競爭時(shí)應(yīng)采取什么樣的策略以搶占市場？為解決這些問題，研究者們將競爭因素引入社會(huì)化營銷績效最大化基本問題中進(jìn)行研究，并根據(jù)不同的營銷需求，將其劃分為單博弈方社會(huì)化營銷績效最大化問題與影響力阻斷最大化問題。

5.1單博弈方社會(huì)化營銷績效最大化問題

當(dāng)多個(gè)廠商在社交網(wǎng)絡(luò)中使用病毒式營銷推廣競爭性商品時(shí)，每個(gè)廠商都希望自己的產(chǎn)品能獲得最大的市場占有率。這類問題稱為單博弈方社會(huì)化營銷績效最大化問題。

許多研究人員通過改進(jìn)現(xiàn)有的信息擴(kuò)散模型來模擬多重競爭下的信息傳播，并據(jù)此構(gòu)建了多種具有多重競爭的信息擴(kuò)散博弈模型，利用這些模型分析不同博弈方的策略選擇。Goyal等人[74]跳出傳統(tǒng)信息傳播模型的框架，假設(shè)節(jié)點(diǎn)被感染的概率與開關(guān)函數(shù)以及選擇函數(shù)有關(guān)，提出switching- selection模型。考慮到網(wǎng)絡(luò)的連通性對(duì)信息的普及以及潛在的消費(fèi)行為都有影響[75,76]，Draief等人[77]在Goyal等人[74]的研究基礎(chǔ)上將連通性加入目標(biāo)函數(shù)中，提出了連通性模型。內(nèi)生預(yù)算模型[77]則認(rèn)為如果公司認(rèn)為通過獲得更大的市場占有率可以抵消選擇種子節(jié)點(diǎn)的支出，種子節(jié)點(diǎn)的數(shù)量應(yīng)該是內(nèi)生的。

5.2影響力阻斷最大化問題(IBM)

企業(yè)在發(fā)展的過程中往往不能避免負(fù)面消息的影響，一旦負(fù)面消息被廣泛傳播，企業(yè)的形象將遭受極大損害，嚴(yán)重阻礙企業(yè)的生存與發(fā)展。當(dāng)社交網(wǎng)絡(luò)中負(fù)面消息出現(xiàn)時(shí)，企業(yè)應(yīng)如何應(yīng)對(duì)才能將傷害減到最小，有效控制輿論的發(fā)展？這種在社會(huì)網(wǎng)絡(luò)中策略性選擇一系列正向的節(jié)點(diǎn)以最小化負(fù)面影響擴(kuò)散的問題，被稱為影響力阻斷最大化問題(IBM)。

Budak等人[78]在IC模型的擴(kuò)展模型MCICM與COICM下研究了IBM問題。然而IBM問題只在受限制的MCICM模型下才具有子模性。He等人[79]提出競爭的線性閾值模型CLT，并證明IBM的目標(biāo)函數(shù)在CLT下仍具有子模性，隨后根據(jù)這一模型在LDAG算法的基礎(chǔ)上設(shè)計(jì)了CLDAG算法求解。假設(shè)負(fù)向觀點(diǎn)種子集并未給定，Tsai等人[80]將影響力阻斷最大化問題看成是一個(gè)零和博弈，利用最大最小策略交替尋找兩個(gè)博弈方最優(yōu)的種子節(jié)點(diǎn)。相應(yīng)的啟發(fā)式算法通過構(gòu)造多重影響者的最短路徑(LSMI)計(jì)算節(jié)點(diǎn)的邊際影響范圍以更好地增加算法的可擴(kuò)展性。

除此之外，負(fù)面消息還可能是用戶在購買該產(chǎn)品或服務(wù)后由于產(chǎn)品的質(zhì)量問題、用戶體驗(yàn)不佳等產(chǎn)品或服務(wù)的自身原因產(chǎn)生的，此時(shí)的負(fù)面消息是內(nèi)生的，一些學(xué)者對(duì)此進(jìn)行了研究[81,82]。

6 非競爭條件下社會(huì)化營銷績效最大化問題

社會(huì)化營銷績效最大化基本問題對(duì)實(shí)際問題進(jìn)行了簡化，這有利于問題的求解，但是卻不能很好地模擬真實(shí)的營銷案例。針對(duì)不同的營銷問題，社會(huì)化營銷績效最大化問題應(yīng)該有不同的約束條件和營銷目標(biāo)，為此研究者對(duì)社會(huì)化營銷績效最大化基本問題進(jìn)行相應(yīng)的延伸與擴(kuò)展?？紤]信息傳播問題的3個(gè)維度：初始節(jié)點(diǎn)個(gè)數(shù)、最終被激活節(jié)點(diǎn)數(shù)的期望以及傳播所需的時(shí)間[83]，通過控制1到2項(xiàng)，然后優(yōu)化第3項(xiàng)，可以將社會(huì)化營銷績效最大化基本問題延伸為許多不同的問題，其中研究最為廣泛的是時(shí)間閾值下的社會(huì)化營銷績效最大化問題和最小目標(biāo)集選擇問題[83,89,90]。

6.1時(shí)間閾值下的社會(huì)化營銷績效最大化問題

考慮這樣一個(gè)案例：某公司希望通過社會(huì)化營銷，以打折促銷的方式短時(shí)間內(nèi)賣出大量商品。這個(gè)打折促銷的時(shí)間不可能太長，此時(shí)，公司希望選擇的種子節(jié)點(diǎn)能夠在促銷期間內(nèi)吸引盡量多的用戶，種子節(jié)點(diǎn)應(yīng)如何選擇？這種問題稱為時(shí)間閾值下的社會(huì)化營銷績效最大化問題。

研究發(fā)現(xiàn)社交網(wǎng)絡(luò)中信息的傳播速度要比理論上慢[91,92]，而響應(yīng)時(shí)間的不一致性是擴(kuò)散緩慢的原因之一[91]。為了使信息擴(kuò)散過程中包含時(shí)間延遲，Chen等人[84]考慮會(huì)面概率，提出IC-M模型。在新模型下目標(biāo)函數(shù)仍具有單調(diào)性及子模性。隨后Chen基于MIA提出兩個(gè)啟發(fā)式算法：MIA-M與MIA-C求解時(shí)間閾值下社會(huì)化營銷績效最大化問題。Liu等人[85]提出存在延遲的另一種IC模型LAIC，并證明績效函數(shù)在LAIC上具有子模性，同時(shí)啟發(fā)式求解任意節(jié)點(diǎn)集的績效，最后提出并行化策略對(duì)算法進(jìn)一步加速。Kim等人[86]提出CT-IC模型，假設(shè)節(jié)點(diǎn)會(huì)以遞減的概率重復(fù)激活其鄰居。時(shí)間閾值下的社會(huì)化營銷績效最大化問題在該模型下仍具有子模性。啟發(fā)式算法CT-IPA通過構(gòu)建樹狀結(jié)構(gòu)能在比貪心算法快4個(gè)數(shù)量級(jí)的時(shí)間內(nèi)求解。

由于用連續(xù)時(shí)間模型模擬信息擴(kuò)散比離散時(shí)間模型更精確，Rodriguez等人[93]提出連續(xù)時(shí)間獨(dú)立級(jí)聯(lián)模型并證明了目標(biāo)函數(shù)具有子模性，據(jù)此提出基于連續(xù)時(shí)間Markov鏈的INFLUMAX算法[87]。Du等人[88]同樣也在連續(xù)時(shí)間獨(dú)立級(jí)聯(lián)模型下提出CONTINEST算法限制信息傳播區(qū)域，并使用簡單抽樣估計(jì)影響范圍。將該算法作為貪心算法的子程序，能夠得到時(shí)間閾值下社會(huì)化營銷績效最大化問題具有一定近似度的解。Xie等人[94]則考慮網(wǎng)絡(luò)的動(dòng)態(tài)演化，提出動(dòng)態(tài)擴(kuò)散網(wǎng)絡(luò)中連續(xù)時(shí)間信息擴(kuò)散模型DYNADIFFUSE，并基于該模型提出時(shí)間閾值下社會(huì)化營銷績效最大化貪心算法FASTMARGIN。

6.2最小目標(biāo)集選擇問題

在一些在線社交網(wǎng)絡(luò)中，當(dāng)某一話題參與度達(dá)到一定的水平，將會(huì)成為熱門話題，激發(fā)更大的話題討論量，這無疑是企業(yè)所希望達(dá)到的營銷效果。如果企業(yè)要在社交網(wǎng)絡(luò)中對(duì)某新產(chǎn)品進(jìn)行推廣，并希望以最小的代價(jià)使該話題成為“熱門”，那么考慮每個(gè)種子節(jié)點(diǎn)的激活成本相同，在達(dá)到給定效果的前提下，為盡量減少成本，應(yīng)該怎樣尋找初始節(jié)點(diǎn)使其數(shù)量盡可能的?。窟@種選擇傳播某一信息的最小的初始節(jié)點(diǎn)集合，使得討論該信息的人數(shù)能達(dá)到給定的閾值的問題被稱為最小目標(biāo)集選擇問題[83,89,90]。

Long等人[89]利用抽樣策略近似計(jì)算節(jié)點(diǎn)影響范圍，隨后利用圖劃分求解全覆蓋的最小目標(biāo)集選擇問題。由于最小目標(biāo)集選擇問題的目標(biāo)函數(shù)具有子模性，Goyal等人[83]提出一個(gè)雙準(zhǔn)則近似的貪心算法Greedy-MINTSS，該算法在每次迭代時(shí)尋找單位成本下邊際績效最大的節(jié)點(diǎn)作為種子節(jié)點(diǎn)。

Zhang等人[90]則對(duì)該問題進(jìn)行了進(jìn)一步的約束，討論應(yīng)該如何選擇最少的初始節(jié)點(diǎn)，使得在給定的概率下討論該話題的人數(shù)能達(dá)到給定的閾值，并將該問題定義為具有覆蓋度概率保證的種子節(jié)點(diǎn)最小化問題(SM-PCG)。該問題在IC模型下不具有子模性，將SM-PCG問題與具有子模性的最小目標(biāo)集選擇問題結(jié)合，利用貪心算法可得到SM-PCG問題的具有給定精度的近似解。

7 總結(jié)與展望

受病毒式營銷背后巨大的商業(yè)利益驅(qū)動(dòng)，社會(huì)化營銷自提出以來就吸引著眾多研究者的目光。經(jīng)過十幾年的研究與發(fā)展，社會(huì)化營銷績效最大化問題已逐漸形成體系并延伸出大量的相關(guān)研究問題。本文系統(tǒng)地介紹了社會(huì)化營銷績效最大化問題的產(chǎn)生與發(fā)展過程，總結(jié)了社交網(wǎng)絡(luò)中基本的信息傳播模型以及基于網(wǎng)絡(luò)結(jié)構(gòu)的貪心算法與啟發(fā)式算法；介紹了基于用戶歷史數(shù)據(jù)的社會(huì)化營銷績效最大化問題；并從競爭與非競爭兩個(gè)角度對(duì)社會(huì)化營銷績效最大化問題進(jìn)行了延伸與擴(kuò)展。雖然社會(huì)化營銷績效最大化問題已經(jīng)取得了大量的理論成果，但仍然有部分問題需要進(jìn)一步的研究和探索：

第一，現(xiàn)有的研究都假設(shè)激活任意節(jié)點(diǎn)為種子節(jié)點(diǎn)需付出的代價(jià)是相同的，但事實(shí)上根據(jù)節(jié)點(diǎn)在網(wǎng)絡(luò)中的地位、節(jié)點(diǎn)本身的特性的不同，激活節(jié)點(diǎn)為種子節(jié)點(diǎn)需要的代價(jià)也不相同。在營銷成本的限制下，并不是所有企業(yè)都能找到理論上最好的節(jié)點(diǎn)為其營銷推廣，種子節(jié)點(diǎn)的數(shù)量也是在相應(yīng)變化的。這一點(diǎn)在未來的研究中必須要考慮到。

第二，建立信息傳播模型的目標(biāo)是模擬真實(shí)網(wǎng)絡(luò)中的信息傳播，模型與真實(shí)網(wǎng)絡(luò)的近似度是決定其是否有效的主要因素?，F(xiàn)有的信息傳播模型多以IC模型與LT模型為基礎(chǔ)，雖然已有方法對(duì)傳統(tǒng)模型進(jìn)行了改進(jìn)，但仍然不能很好地描述真實(shí)網(wǎng)絡(luò)中的信息傳播。許多學(xué)者試圖通過在真實(shí)網(wǎng)絡(luò)中進(jìn)行大規(guī)模的實(shí)驗(yàn)找出信息傳播的規(guī)律，發(fā)現(xiàn)網(wǎng)絡(luò)中的信息擴(kuò)散不僅與節(jié)點(diǎn)本身的影響力、同質(zhì)性[9,31]、敏感性有關(guān)[32]，也與網(wǎng)絡(luò)中連接關(guān)系的強(qiáng)弱[5,6]、網(wǎng)絡(luò)的結(jié)構(gòu)[30]有關(guān)。如何合理應(yīng)用上述研究，考慮社交網(wǎng)絡(luò)中的其他特性，找出更好的模型來擬合真實(shí)網(wǎng)絡(luò)的信息傳播現(xiàn)象仍是待解決的問題[18,34]。進(jìn)一步地，可以跳出IC模型與LT模型的約束，用其他模型，特別是不符合子模性的模型來研究這一問題[34,79]。

第三，多數(shù)研究僅僅基于網(wǎng)絡(luò)結(jié)構(gòu)求解社會(huì)化營銷績效最大化問題，但利用用戶產(chǎn)生的歷史數(shù)據(jù)能使結(jié)果更準(zhǔn)確、更具有針對(duì)性。雖然已有部分研究進(jìn)行了相應(yīng)的嘗試，但該領(lǐng)域仍有廣泛的研究空間。考慮到用戶只有登錄后才能被其他用戶影響，但每個(gè)用戶登錄的頻率是不同的，在信息傳播模型中使用用戶登錄數(shù)據(jù)來模擬具有時(shí)間限的信息擴(kuò)散將是一項(xiàng)極具挑戰(zhàn)工作[84]。而隨著移動(dòng)互聯(lián)網(wǎng)的發(fā)展與普及，考慮移動(dòng)用戶的空間位置信息，構(gòu)建基于位置的社會(huì)網(wǎng)絡(luò)，從中選擇有影響力的節(jié)點(diǎn)[39,40]能夠?yàn)榛谖恢玫臓I銷提供良好的支持。此外，如何進(jìn)一步改進(jìn)現(xiàn)有方法[59,60,62]也值得進(jìn)一步地研究。

第四，上述研究都是針對(duì)于靜態(tài)網(wǎng)絡(luò)的，但社交網(wǎng)絡(luò)本身是一個(gè)動(dòng)態(tài)網(wǎng)絡(luò)[95]，網(wǎng)絡(luò)中每時(shí)每刻都有新的連接在建立，也有舊的連接在斷開，我們獲取的只是在某一時(shí)間點(diǎn)上的截面數(shù)據(jù)。因此，仍需要進(jìn)一步研究動(dòng)態(tài)網(wǎng)絡(luò)上的社會(huì)化營銷績效最大化問題[29,39,40]。

最后，隨著在線社交網(wǎng)絡(luò)規(guī)模的指數(shù)型增長，社交網(wǎng)絡(luò)中用戶數(shù)量達(dá)到了數(shù)以億計(jì)，現(xiàn)有的方法不能處理如此大規(guī)模的數(shù)據(jù)。一種可行的辦法是利用分布式計(jì)算將已有算法并行化處理[33,42,44,49]；另一個(gè)研究方向是結(jié)合不同算法的優(yōu)勢得到新的算法，以進(jìn)一步提高社會(huì)化營銷績效最大化算法的有效性[33,44]?，F(xiàn)在，尋找更加高效、精確的算法仍是社會(huì)化營銷績效最大化問題研究的核心。

[1] DENRELL J. SOCIOLOGY: Indirect social influence[J]., 2008, 321(5885): 47-48. doi: 10.1126/science. 1157667.

[2] MUCHNIK L, ARAL S, and TAYLOR S J. Social influence bias: A randomized experiment[J]., 2013, 341(6146): 647-651. doi: 10.1126/science.1240466.

[3] SUN Tao, CHEN Wei, LIU Zhenming,Participation maximization based on social influence in online discussion forums[C]. The 5th International AAAI Conference on Web and Social Media (ICWSM), Barcelona, 2011: 361-368.

[4] BANERJEE A, CHANDRASEKHAR A G, DUFLO E,The diffusion of microfinance[J]., 2013, 341(6144): 1236498. doi: 10.1126/science.1236498.

[5] BOND R M, FARISS C J, JONES J J,A 61- million-person experiment in social influence and political mobilization[J]., 2012, 489(7415): 295-298. doi: 10. 1038/nature11421.

[6] ARAL S. Social science: poked to vote[J]., 2012, 489(7415): 212-214. doi: 10.1038/489212a.

[7] ARAL S and WALKER D. Tie strength, embeddedness, and social influence: A large-scale networked experiment[J]., 2014, 60(6): 1352-1370. doi: 10.1287/ mnsc.2014.1936.

[8] LEE Youngjin, HOSANAGAR K, and TAN Y. Do I follow my friends or the crowd? information cascades in online movie ratings[J]., 2015, 61(9): 2241-2258. doi: 10.1287/mnsc.2014.2082.

[9] LEWIS K, GONZALEZ M, and KAUFMAN J. Social selection and peer influence in an online social network[J]., 2012, 109(1): 68-72. doi: 10.1073/pnas.1109739109.

[10] MORONE F and MAKSE H A. Influence maximization in complex networks through optimal percolation[J]., 2015, 524(7563): 65-68. doi: 10.1038/nature14604.

[11] MOE W W and SCHWEIDEL D A. Online product opinions: incidence, evaluation, and evolution[J]., 2012, 31(3): 372-386. doi: 10.1287/mksc.1110.0662.

[12] TUCKER C E. The reach and persuasiveness of viral video ads[J]., 2014, 34(2): 281-296. doi: 10.1287/ mksc.2014.0874.

[13] GODINHO DE MATOS M, FERREIRA P, and KRACKHARDT D. Peer influence in the diffusion of the iPhone 3G over a large social network[J].(), 2014, 38(4): 1103-1133. doi: 10.2139/ssrn.2053420.

[14] GU Bin, KONANA P, RAGHUNATHAN R,Research note-the allure of homophily in social media: Evidence from investor responses on virtual communities[J]., 2014, 25(3): 604-617. doi: 10.1287/isre. 2014.0531.

[15] KEMPE D, KLEINBERG J, and TARDOS é. Maximizing the spread of influence through a social network[C]. Proceedings of the ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York, 2003: 137-146. doi: 10.1145/956750.956769.

[16] DOMINGOS P and RICHARDSON M. Mining the network value of customers[C]. Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York, 2001: 57-66. doi: 10.1145/ 502512.502525.

[17] RICHARDSON M and DOMINGOS P. Mining knowledge- sharing sites for viral marketing[C]. Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York, 2002: 61-70. doi: 10.1145/775047.775057.

[18] CHEN Wei, WANG Yajun, and YANG Siyu. Efficient influence maximization in social networks[C]. Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York, 2009: 199-208. doi: 10.1145/1557019.1557047.

[19] WATTS D J. A simple model of global cascades on random networks[J]., 2002, 99(9): 5766-5771. doi: 10.1073/pnas.082090499.

[20] MYERS S A, ZHU Chenguang, and LESKOVEC J. Information diffusion and external influence in networks[C]. Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York, 2012: 33-41. doi: 10.1145/2339530.2339540.

[21] NEWMAN M E J. The structure and function of complex networks[J]., 2003, 45(2): 167-256. doi: 10.1137 /S003614450342480.

[22] YANG J and LESKOVEC J. Modeling information diffusion in implicit networks[C]. 2010 IEEE International Conference on Data Mining, Sydney, 2010: 599-608. doi: 10.1109/ICDM. 2010.22.

[23] GOLDENBERG J, LIBAI B, and MULLER E. Talk of the network: A complex systems look at the underlying process of word-of-mouth[J]., 2001, 12(3): 211-223. doi: 10.1023/A:1011122126881.

[24] GOLDENBERG J, LIBAI B, and MULLER E. Using complex systems analysis to advance marketing theory development: Modeling heterogeneity effects on new product growth through stochastic cellular automata[J]., 2001, 9(3): 1-18.

[25] KEMPE D, KLEINBERG J, and TARDOS é. Influential Nodes in a Diffusion Model for Social Networks[M]. Lisbon: Springer, 2005: 1127-1138.

[26] KIMURA M, SAITO K, NAKANO R,Extracting influential nodes on a social network for information diffusion[J]., 2010, 20(1): 70-97. doi: 10.1007/s10618-009-0150-5.

[27] KIMURA M and SAITO K. Tractable Models for Information Diffusion in Social Networks[M]. Berlin: Springer, 2006: 259-271.

[28] EVEN-DAR E and SHAPIRA A. A Note on Maximizing the Spread of Influence in Social Networks[M]. San Diego: Springer, 2007: 281-286.

[29] MA Hao, YANG Haixuan, LYU M R,Mining social networks using heat diffusion processes for marketing candidates selection[C]. Proceedings of the 17th ACM Conference on Information and Knowledge Management, New York, 2008: 233-242. doi: 10.1145/1458082.1458115.

[30] CENTOLA D. The spread of behavior in an online social network experiment[J]., 2010, 329(5996): 1194-1197. doi: 10.1126/science.1189910.

[31] ARAL S, MUCHNIK L, and SUNDARARAJAN A. Distinguishing influence-based contagion from homophily- driven diffusion in dynamic networks[J]., 2009, 106(51): 21544-21549. doi: 10.1073/pnas.0908800106.

[32] ARAL S and WALKER D. Identifying influential and susceptible members of social networks[J]., 2012, 337(6092): 337-341. doi: 10.1126/science.1215842.

[33] CHEN Wei, WANG Chi, and WANG Yajun. 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, 2010: 1029-1038. doi: 10.1145/ 1835804.1835934.

[34] CHEN Wei, YUAN Yifei, and ZHANG Li. Scalable influence maximization in social networks under the linear threshold model[C]. 2010 IEEE 10th International Conference on Data Mining (ICDM), Sydney, 2010: 88-97. doi: 10.1109/ICDM. 2010.118.

[35] NEMHAUSER G L, WOLSEY L A, and FISHER M L. An analysis of approximations for maximizing submodular set functionsI[J]., 1978, 14(1): 265-294. doi: 10.1007/BF01588971.

[36] LESKOVEC J, KRAUSE A, GUESTRIN C,Cost- effective outbreak detection in networks[C]. Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York, 2007: 420-429. doi: 10.1145/1281192.1281239.

[37] GOYAL A, LU Wei, and LAKSHMANAN L V S. Celf++: Optimizing the greedy algorithm for influence maximization in social networks[C]. Proceedings of the 20th International Conference Companion on World Wide Web, New York, 2011: 47-48. doi: 10.1145/1963192.1963217.

[38] GIRVAN M and NEWMAN M E J. Community structure in social and biological networks[J]., 2002, 99(12): 7821-7826. doi: 10.1073/ pnas.122653799.

[39] WANG Yu, CONG Gao, SONG Guojie,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, 2010: 1039-1048. doi: 10.1145/ 1835804.1835935.

[40] SONG Guojie, ZHOU Xiabing, WANG Yu,Influence maximization on large-scale mobile social network: A divide-and-conquer method[J]., 2015, 26(5): 1379-1392. doi: 10.1109/TPDS.2014.2320515.

[41] BORGS C, BRAUTBAR M, CHAYES JMaximizing social influence in nearly optimal time[C]. Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, Philadelphia, 2014: 946-957. doi: 10.1137/ 1.9781611973402.70.

[42] TANG Youze, XIAO Xiaokui, and SHI Yanchen. Influence maximization: Near-optimal time complexity meets practical efficiency[C]. Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data, New York, 2014: 75-86. doi: 10.1145/2588555.2593670.

[43] COHEN E, DELLING D, PAJOR T,Sketch-based influence maximization and computation: Scaling up with guarantees[C]. Proceedings of the 23rd ACM International Conference on Information and Knowledge Management, New York, 2014: 629-638. doi: 10.1145/2661829.2662077.

[44] WANG Chi, CHEN Wei, and WANG Yajun. Scalable influence maximization for independent cascade model in large-scale social networks[J]., 2012, 25(3): 545-576. doi: 10.1007/s10618-012- 0262-1.

[45] GOYAL A, LU W, and LAKSHMANAN L V S. Simpath: An efficient algorithm for influence maximization under the linear threshold model[C]. 2011 IEEE 11th International Conference on Data Mining (ICDM), Vancouver, 2011: 211-220. doi: 10.1109/ICDM.2011.132.

[46] JUNG K, HEO W, and CHEN Wei. IRIE: Scalable and robust influence maximization in social networks[C]. 2012 IEEE 12th International Conference on Data Mining, Brussels, 2012: 918-923. doi: 10.1109/ICDM.2012.79.

[47] KITSAK M, GALLOS L K, HAVLIN S,Identification of influential spreaders in complex networks[J]., 2010, 6(11): 888-893. doi: 10.1038/nphys1746.

[48] NARAYANAM R and NARAHARI Y. A shapley value-based approach to discover influential nodes in social networks[J]., 2011, 8(1): 130-147. doi: 10.1109/TASE.2010.2052042.

[49] JIANG Qingye, SONG Guojie, GAO Cong,Simulated annealing based influence maximization in social networks[C]. Twenty-fifth AAAI Conference on Artificial Intelligence, San Francisco, USA, 2011, 11: 127-132.

[50] LIU Xiaodong, LI Mo, LI Shanshan,IMGPU: GPU- accelerated influence maximization in large-scale social networks[J].,2014, 25(1): 136-145. doi: 10.1109/TPDS.2013.41.

[51] HE Xinran and KEMPE D. Stability of influence maximization[C]. Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York, 2014: 1256-1265. doi: 10.1145/2623330. 2623746.

[52] ADIGA A, KUHLMAN C J, MORTVEIT H S,Sensitivity of diffusion dynamics to network uncertainty[J]., 2014, 51: 207-226. doi: 10.1613/jair.4330.

[53] SAITO K, NAKANO R, and KIMURA M. Prediction of information diffusion probabilities for independent cascade model[C]. Knowledge-Based Intelligent Information and Engineering Systems, Zagreb, 2008: 67-75. doi: 10.1007/978- 3-540-85567-5_9.

[54] GOYAL A, BONCHI F, and LAKSHMANAN L V S. Learning influence probabilities in social networks[C]. Proceedings of the Third ACM International Conference on Web Search and Data Mining, New York, 2010: 241-250. doi: 10.1145/1718487.1718518.

[55] GOYAL A, BONCHI F, and LAKSHMANAN L V S. A data-based approach to social influence maximization[J]., 2011, 5(1): 73-84. doi: 10.14778/2047485.2047492.

[56] GRANOVETTER M S. The strength of weak ties[J]., 1973, 78(6): 1360-1380.

[57] KRACKHARDT D. The strength of strong ties: The importance of philos in organizations[J].:,,, 1992, 216-239.

[58] LIN C X, MEI Qiaozhu, HAN Jiawei,The joint inference of topic diffusion and evolution in social communities[C]. 2011 IEEE 11th International Conference on Data Mining (ICDM), Vancouver, 2011: 378-387. doi: 10. 1109/ICDM.2011.144.

[59] LIU Lu, TANG Jie, HAN Jiawei,Mining topic-level influence in heterogeneous networks[C]. Proceedings of the 19th ACM International Conference on Information and Knowledge Management, New York, 2010: 199-208. doi: 10.1145/1871437.1871467.

[60] TANG Jie, SUN Jimeng, WANG Chi,Social influence analysis in large-scale networks[C]. Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York, 2009: 807-816. doi: 10.1145/1557019.1557108.

[61] LI Yungming and SHIU Yalin. A diffusion mechanism for social advertising over microblogs[J]., 2012, 54(1): 9-22. doi: 10.1016/j.dss.2012.02.012.

[62] BARBIERI N, BONCHI F, and MANCO G. Topic-aware social influence propagation models[J]., 2013, 37(3): 555-584. doi: 10.1007/ s10115-013-0646-6.

[63] ASLAY C, BARBIERI N, BONCHI F,Online topic- aware influence maximization queries[C]. 17th International Conference on Extending Database Technology, Athens, 2014: 295-306.

[64] CHEN Wei, LIN Tian, and YANG Cheng. Real-time topic-aware influence maximization using preprocessing[C]. International Conference on Computational Social Networks. Beijing, 2015: 1-13. doi: 10.1007/978-3-319-21786-4_1.

[65] CHEN Shuo, FAN Ju, LI Guoliang,Online topic-aware influence maximization[J]., 2015, 8(6): 666-677. doi: 10.14778/2735703. 2735706.

[66] LI Yuchen, ZHANG Dongxiang, and TAN Kianlee. Real-time targeted influence maximization for online advertisements[J]., 2015, 8(10): 1070-1081. doi: 10.14778/2794367.2794376.

[67] DUBEY P, GARG R, and DE MEYER B. Competing for Customers in a Social Network: The Quasi-linear Case[M]. Patras: Springer, 2006: 162-173.

[68] CARNES T, NAGARAJAN C, WILD S M,Maximizing influence in a competitive social network: A follower's perspective[C]. Proceedings of the Ninth International Conference on Electronic Commerce, New York, 2007: 351-360. doi: 10.1145/1282100.1282167.

[69] BHARATHI S, KEMPE D, and SALEK M. Competitive Influence Maximization in Social Networks[M]. San Diego: Springer, 2007: 306-311.

[70] KOSTKA J, OSWALD Y A, and WATTENHOFER R. Word of Mouth: Rumor Dissemination in Social Networks[M]. Villars-sur-Ollon, Switzerland: Springer, 2008: 185-196.

[71] PATHAK N, BANERJEE A, and SRIVASTAVA J. A generalized linear threshold model for multiple cascades[C]. 2010 IEEE 10th International Conference on Data Mining (ICDM), Sydney, 2010: 965-970. doi: 10.1109/ICDM.2010. 153.

[72] TRPEVSKI D, TANG W K S, and KOCAREV L. Model for rumor spreading over networks[J]., 2010, 81(5): 056102. doi: 10.1103/PhysRevE.81.056102.

[73] LI Hui, BHOWMICK S S, CUI Jiangtao,GetReal: Towards realistic selection of influence maximization strategies in competitive networks[C]. Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, New York, 2015: 1525-1537. doi: 10.1145/2723372.2723710.

[74] GOYAL S, HEIDARI H, and KEARNS M. Competitive contagion in networks[J]., 2014. doi: 10.1016/j.geb.2014.09.002.

[75] CHAOJI V, RANU S, RASTOGI R,Recommendations to boost content spread in social networks[C]. Proceedings of the 21st International Conference on World Wide Web, New York, 2012: 529-538. doi: 10.1145/2187836.2187908.

[76] KATONA Z, ZUBCSEK P P, and SARVARY M. Network effects and personal influences: The diffusion of an online social network[J]., 2011, 48(3): 425-443. doi: 10.1509/jmkr.48.3.425.

[77] DRAIEF M, HEIDARI H, and KEARNS M. New models for competitive contagion[C]. Twenty-eighth AAAI Conference on Artificial Intelligence, Québec, 2014: 637-644.

[78] BUDAK C, AGRAWAL D, and EL ABBADI A. Limiting the spread of misinformation in social networks[C]. Proceedings of the 20th International Conference on World Wide Web, New York, 2011: 665-674. doi: 10.1145/1963405.1963499.

[79] HE Xinran, SONG Guojie, CHEN Wei,Influence blocking maximization in social networks under the competitive linear threshold model[C]. 9th VLDB Workshop on Secure Data Management, Istanbul, 2012: 463-474. doi: 10.1137/1.9781611972825.40.

[80] TSAI J, NGUYEN T H, and TAMBE M. Security games for controlling contagion[C]. Twenty-sixth AAAI Conference on Artificial Intelligence, Toronto, 2012: 1241-1248.

[81] CHEN Wei, COLLINS A, CUMMINGS R,Influence maximization in social networks when negative opinions may emerge and propagate[C]. SIAM Conference on Data Mining, Mesa, Arizona, USA, 2011: 379-390. doi: 10.1137/1. 9781611972818.33.

[82] LI Yanhua, CHEN Wei, WANG Yajun,Influence diffusion dynamics and influence maximization in social networks with friend and foe relationships[C]. Proceedings of the Sixth ACM International Conference on Web Cearch and Data Mining, New York, 2013: 657-666. doi: 10.1145/2433396. 2433478.

[83] GOYAL A, BONCHI F, LAKSHMANAN L V S,On minimizing budget and time in influence propagation over social networks[J]., 2013, 3(2): 179-192. doi: 10.1007/s13278-012-0062-z.

[84] CHEN Wei, LU Wei, and ZHANG Ning. Time-critical influence maximization in social networks with time-delayed diffusion process[C]. The Twenty-sixth AAAI Conference on Artificial Intelligence, Toronto, 2012: 592-598.

[85] LIU Bo, CONG Gao, ZENG Yifeng,Influence spreading path and its application to the time constrained social influence maximization problem and beyond[J]., 2014, 26(8): 1904-1917. doi: 10.1109/TKDE.2013.106.

[86] KIM J, LEE W, and YU H. CT-IC: Continuously activated and time-restricted independent cascade model for viral marketing[J]., 2014, 62: 57-68. doi: 10.1016/j.knosys.2014.02.013.

[87] RODRIGUEZ M G and SCH LKOPF B. Influence maximization in continuous time diffusion networks[C]. Proceeding of the Twenty-ninth International Conference on Machine Learning, Edinburgh, 2012: 313-320. doi: 10.1145/ 2824253.

[88] DU Nan, SONG Le, GOMEZ-RODRIGUEZ Manuel,Scalable influence estimation in continuous-time diffusion networks[C]. Advances in Neural Information Processing Systems, Harrahs and Harveys, 2013: 3147-3155.

[89] LONG Cheng and WONG R C W. Minimizing seed set for viral marketing[C]. 2011 IEEE 11th International Conference on Data Mining (ICDM), Vancouver, 2011: 427-436. doi: 10.1109/ICDM.2011.99.

[90] ZHANG Peng, CHEN Wei, SUN Xiaoming,Minimizing seed set selection with probabilistic coverage guarantee in a social network[C]. Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York, 2014: 1306-1315. doi: 10.1145/2623330. 2623684.

[91] IRIBARREN J L and MORO E. Impact of human activity patterns on the dynamics of information diffusion[J]., 2009, 103(3): 038702. doi: 10.1103/PhysRev Lett.103.038702.

[92] KARSAI M, KIVEL M, PAN R K,Small but slow world: how network topology and burstiness slow down spreading[J]., 2011, 83(2): 025102. doi: 10.1103/Phys RevE.83.025102.

[93] RODRIGUEZ M G, BALDUZZI D, and SCH LKOPF B. Uncovering the temporal dynamics of diffusion networks[C]. Proceeding of the Twenty-eighth International Conference on Machine Learning, Bellevue, 2011: 561-568.

[94] XIE Miao, YANG Qiusong, WANG Qing,DynaDiffuse: A dynamic diffusion model for continuous time constrained influence maximization[C]. Twenty-ninth AAAI Conference on Artificial Intelligence, Austin, Texas, 2015: 346-352.

[95] GOMEZ RODRIGUEZ M, LESKOVEC J, and KRAUSE A. Inferring networks of diffusion and influence[C]. Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York, 2010: 1019-1028. doi: 10.1145/1835804.1835933.

Review of Social Marketing Performance Maximization Problem and Its Extension

LIU Yezheng LI Lingfei JIANG Yuanchun

(School of Management, Hefei University of Technology, Hefei 230009, China)

Many enterprises try to promote their products in online social network since information propagation in this network have several advantages such as fast transmission speed, low marketing costs, and large influence area. However, it is a challenging task for enterprises to select suitable seed nodes to publish marketing information so that marketing information can influence or cover most users under a given cost and realize performance maximization. By means of literature search and review, this paper systematically summarizes information propagation models in social marketing, introduces algorithms for social marketing performance maximization problem with respect to network topology, user historical data, compete and non-compete condition. Finally, this paper concludes an exploration of future directions of this research filed.

Online social network; Social marketing; Performance maximization

F270.3; TP311

A

1009-5896(2016)09-2130-11

10.11999/JEIT160517

2016-07-18；

2016-08-09

國家自然科學(xué)基金重大項(xiàng)目(71490725)，國家973規(guī)劃項(xiàng)目(2013CB329603)，國家自然科學(xué)基金(71371062, 91546114, 71302064, 71501057)，國家科技支撐計(jì)劃項(xiàng)目(2015BAH26F00)

The Major Program of the National Natural Science Foundation of China (71490725), The National 973 Program of China (2013CB329603), The National Natural Science Foundation of China (71371062, 91546114, 71302064, 71501057), The National Key Technology Support Program (2015BAH26F00)

姜元春 ycjiang@hfut.edu.cn

劉業(yè)政： 男，1965年生，教授，博士生導(dǎo)師，主要研究方向?yàn)殡娮由虅?wù)與商務(wù)智能、決策理論與方法、社會(huì)技術(shù)系統(tǒng)下的組織行為.

李玲菲： 女，1992年生，博士生，研究方向?yàn)樵诰€社交網(wǎng)絡(luò)分析.

姜元春： 男，1980年生，副研究員，碩士生導(dǎo)師，主要研究方向?yàn)殡娮由虅?wù)與商務(wù)智能、個(gè)性化營銷.