社会化营销绩效最大化问题及其扩展研究综述

刘业政 李玲菲 姜元春



社会化营销绩效最大化问题及其扩展研究综述

刘业政 李玲菲 姜元春*

(合肥工业大学管理学院 合肥 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年生，副研究员，硕士生导师，主要研究方向为电子商务与商务智能、个性化营销.