社會化營銷績效最大化問題及其擴展研究綜述

劉業政 李玲菲 姜元春

?

社會化營銷績效最大化問題及其擴展研究綜述

劉業政 李玲菲 姜元春*

(合肥工業大學管理學院 合肥 230009)

由于在線社交網絡上的信息傳播具有速度快、成本低、影響范圍大等優勢，許多企業均試圖通過在線社交網絡進行產品的促銷和推廣。然而，企業如何選擇種子結點來投放營銷信息，使得在給定成本下覆蓋或影響最多的用戶，實現營銷績效最大化是一項極具挑戰性的任務。該文通過文獻檢索和綜述方法，系統總結了社會化營銷中的信息傳播模型，從網絡拓撲結構和用戶歷史數據、競爭條件與非競爭條件等不同視角總結了社會化營銷績效最大化的有關算法，最后對社會化營銷績效最大化問題進行了總結與展望。

在線社交網絡；社會化營銷；績效最大化

1 引言

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

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

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

上述算法僅僅基于網絡結構本身進行求解，但在真實的社交網絡中，除了網絡拓撲結構外，還存在大量用戶產生的文本信息以及用戶交互信息。通過分析這些歷史數據，可以知道用戶的興趣偏好，了解用戶間聯系的緊密程度。這些信息一方面能幫助我們找出對產品感興趣的用戶，從而使產品的推廣更具有針對性及有效性；另一方面也能幫助我們更好地理解社交網絡中信息傳播機制，構建更為精準的信息傳播模型，從而求解社會化營銷績效最大化問題。

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

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

2 基本的信息傳播模型

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

2.1獨立級聯模型(Independent Cascade model, IC模型)

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

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

IC模型認為節點的影響是獨立的，但Watts等人[19]認為影響力的作用應該是累積的，即當個體不斷被某條信息影響時，個體對該信息的接受度將逐漸增強，據此Watts等人[19]提出LT模型。LT模型的具體描述如下：

2.3其他模型

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

上述模型大多是將解釋其他領域的擴散現象的模型應用在社交網絡信息傳播中，但信息本身的傳播規律可能與這些模型不同。許多學者試圖通過在真實網絡中進行大規模的實驗找出信息傳播與網絡結構之間的關系。如何合理應用這些研究成果，找出更好的模型來擬合真實的信息傳播現象仍是待解決的問題。

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

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

3.1貪心算法

社會化營銷績效最大化基本問題在IC模型和LT模型下都是NP難的[15,33,34]，因此很難求得最優解。但是在IC模型和LT模型下，目標函數單調遞增且具有子模性，即若節點集，那么對于圖中任意節點，有

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

為提高貪心算法的效率，Leskovec等人[36]提出使用“Lazy-Forward”優化的CELF算法，該算法利用子模性在每輪迭代中只估計了部分最可能的候選節點的邊際營銷績效。Goyal等人[37]改進了CELF算法，提出CELF++算法，實驗表明，CELF++比CELF快35%~55%。Chen等人[18]為有效減少IC模型中邊的篩選次數提出NewGreedy與MixGreedy算法。考慮到社交網絡中像社區這樣的特殊結構[38]能夠影響信息的傳播，Wang等人[39]提出基于社區的貪心算法CGA。CGA算法使用標簽傳播算法以及組合熵來發現社區，隨后用動態規劃算法尋找種子節點。Song等人[40]則將CGA算法并行化處理提出PCA算法。

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

上述主要貪心算法的時間復雜度與算法的近似度如表1所示。

表1貪心算法的時間復雜度與近似度

貪心算法最大的優勢是能給出算法的近似度，使得營銷效果有了保障。但是由于計算任意節點的績效本身就是#P難的，貪心算法的時間復雜度往往較高，難以擴展到大規模的網絡中。

3.2啟發式算法

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

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

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

部分啟發式算法的時間復雜度見表2。

表2部分啟發式算法的時間復雜度

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

由于計算上的高效，啟發式算法在處理大規模網絡時具有極大的優勢，但它的精度無法保證。然而對于企業來說，營銷方案的可靠性往往決定了企業是否會投入相應的成本，這也成為啟發式算法真正應用到實際中的一大瓶頸。

4 基于用戶歷史數據的社會化營銷績效最大化問題

上述方法都關注于網絡的拓撲結構，卻忽略了歷史數據，如個體間的交互情況、信息傳播記錄、信息的內容等。利用用戶間交互的頻率預測用戶間親密程度，通過用戶發布的信息推斷用戶的偏好可以幫助我們更好地鎖定目標客戶、模擬真實傳播行為，從而求得更為精確的解。

4.1基于用戶活動日志的社會化營銷績效最大化問題

考慮這樣一個問題：如果兩個節點間信息傳播概率的估計與現實情況不同，那么算法的結果還可信嗎？模型穩定性的相關研究[51,52]發現，影響概率的擾動會導致明顯的不穩定性，因此使傳播概率盡量貼合真實網絡就變得十分重要。傳統的信息傳播模型顯然沒能很好地解決這一問題，一個可行的辦法是結合用戶活動日志定義節點間的傳播概率。

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

4.2基于信息內容的社會化營銷績效最大化問題

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

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

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

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

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

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

當多個廠商在社交網絡中使用病毒式營銷推廣競爭性商品時，每個廠商都希望自己的產品能獲得最大的市場占有率。這類問題稱為單博弈方社會化營銷績效最大化問題。

許多研究人員通過改進現有的信息擴散模型來模擬多重競爭下的信息傳播，并據此構建了多種具有多重競爭的信息擴散博弈模型，利用這些模型分析不同博弈方的策略選擇。Goyal等人[74]跳出傳統信息傳播模型的框架，假設節點被感染的概率與開關函數以及選擇函數有關，提出switching- selection模型。考慮到網絡的連通性對信息的普及以及潛在的消費行為都有影響[75,76]，Draief等人[77]在Goyal等人[74]的研究基礎上將連通性加入目標函數中，提出了連通性模型。內生預算模型[77]則認為如果公司認為通過獲得更大的市場占有率可以抵消選擇種子節點的支出，種子節點的數量應該是內生的。

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

企業在發展的過程中往往不能避免負面消息的影響，一旦負面消息被廣泛傳播，企業的形象將遭受極大損害，嚴重阻礙企業的生存與發展。當社交網絡中負面消息出現時，企業應如何應對才能將傷害減到最小，有效控制輿論的發展？這種在社會網絡中策略性選擇一系列正向的節點以最小化負面影響擴散的問題，被稱為影響力阻斷最大化問題(IBM)。

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

除此之外，負面消息還可能是用戶在購買該產品或服務后由于產品的質量問題、用戶體驗不佳等產品或服務的自身原因產生的，此時的負面消息是內生的，一些學者對此進行了研究[81,82]。

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

社會化營銷績效最大化基本問題對實際問題進行了簡化，這有利于問題的求解，但是卻不能很好地模擬真實的營銷案例。針對不同的營銷問題，社會化營銷績效最大化問題應該有不同的約束條件和營銷目標，為此研究者對社會化營銷績效最大化基本問題進行相應的延伸與擴展。考慮信息傳播問題的3個維度：初始節點個數、最終被激活節點數的期望以及傳播所需的時間[83]，通過控制1到2項，然后優化第3項，可以將社會化營銷績效最大化基本問題延伸為許多不同的問題，其中研究最為廣泛的是時間閾值下的社會化營銷績效最大化問題和最小目標集選擇問題[83,89,90]。

6.1時間閾值下的社會化營銷績效最大化問題

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

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

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

6.2最小目標集選擇問題

在一些在線社交網絡中，當某一話題參與度達到一定的水平，將會成為熱門話題，激發更大的話題討論量，這無疑是企業所希望達到的營銷效果。如果企業要在社交網絡中對某新產品進行推廣，并希望以最小的代價使該話題成為“熱門”，那么考慮每個種子節點的激活成本相同，在達到給定效果的前提下，為盡量減少成本，應該怎樣尋找初始節點使其數量盡可能的小？這種選擇傳播某一信息的最小的初始節點集合，使得討論該信息的人數能達到給定的閾值的問題被稱為最小目標集選擇問題[83,89,90]。

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

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

7 總結與展望

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

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

第二，建立信息傳播模型的目標是模擬真實網絡中的信息傳播，模型與真實網絡的近似度是決定其是否有效的主要因素。現有的信息傳播模型多以IC模型與LT模型為基礎，雖然已有方法對傳統模型進行了改進，但仍然不能很好地描述真實網絡中的信息傳播。許多學者試圖通過在真實網絡中進行大規模的實驗找出信息傳播的規律，發現網絡中的信息擴散不僅與節點本身的影響力、同質性[9,31]、敏感性有關[32]，也與網絡中連接關系的強弱[5,6]、網絡的結構[30]有關。如何合理應用上述研究，考慮社交網絡中的其他特性，找出更好的模型來擬合真實網絡的信息傳播現象仍是待解決的問題[18,34]。進一步地，可以跳出IC模型與LT模型的約束，用其他模型，特別是不符合子模性的模型來研究這一問題[34,79]。

第三，多數研究僅僅基于網絡結構求解社會化營銷績效最大化問題，但利用用戶產生的歷史數據能使結果更準確、更具有針對性。雖然已有部分研究進行了相應的嘗試，但該領域仍有廣泛的研究空間。考慮到用戶只有登錄后才能被其他用戶影響，但每個用戶登錄的頻率是不同的，在信息傳播模型中使用用戶登錄數據來模擬具有時間限的信息擴散將是一項極具挑戰工作[84]。而隨著移動互聯網的發展與普及，考慮移動用戶的空間位置信息，構建基于位置的社會網絡，從中選擇有影響力的節點[39,40]能夠為基于位置的營銷提供良好的支持。此外，如何進一步改進現有方法[59,60,62]也值得進一步地研究。

第四，上述研究都是針對于靜態網絡的，但社交網絡本身是一個動態網絡[95]，網絡中每時每刻都有新的連接在建立，也有舊的連接在斷開，我們獲取的只是在某一時間點上的截面數據。因此，仍需要進一步研究動態網絡上的社會化營銷績效最大化問題[29,39,40]。

最后，隨著在線社交網絡規模的指數型增長，社交網絡中用戶數量達到了數以億計，現有的方法不能處理如此大規模的數據。一種可行的辦法是利用分布式計算將已有算法并行化處理[33,42,44,49]；另一個研究方向是結合不同算法的優勢得到新的算法，以進一步提高社會化營銷績效最大化算法的有效性[33,44]。現在，尋找更加高效、精確的算法仍是社會化營銷績效最大化問題研究的核心。

[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

國家自然科學基金重大項目(71490725)，國家973規劃項目(2013CB329603)，國家自然科學基金(71371062, 91546114, 71302064, 71501057)，國家科技支撐計劃項目(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

劉業政： 男，1965年生，教授，博士生導師，主要研究方向為電子商務與商務智能、決策理論與方法、社會技術系統下的組織行為.

李玲菲： 女，1992年生，博士生，研究方向為在線社交網絡分析.

姜元春： 男，1980年生，副研究員，碩士生導師，主要研究方向為電子商務與商務智能、個性化營銷.