基于社会网络的广告投放优化决策研究文献综述

文献综述（或调研报告）：

本文主要研究的是广告投放优化决策问题，换而言之，就是在考虑成本因素的情况下，如何在社会网络中选择具有影响力的节点用户，实现影响力的最大化。关于这个问题，已经有很多的学者从不同角度进行了研究。

早在1996年，Danaher与Rust^[1]就已经证明广告商想要获得最大的投资回报并不是将广告预算投入到所有的媒体广告中，而是选择其中的重点媒体进行投放广告。对于影响力最大化问题，Domingos和Richardson等人^[2]首次将影响力最大化问题当作一个算法问题引入到社会网络领域进行研究，他们假设需要在一个社会网络中销售一种新产品，则可以先让一部分有影响力的人免费使用该产品，然后通过网络效应，能够使更多的邻用户去购买该产品，从而形成级联，达到营销效果。对于这类影响力最大化问题，后面的研究者们分别提出了多种优化算法，其中主要是贪心爬山算法和启发式算法。

（一）贪心爬山算法

Kempe、Kleinberg等人^[3]第一次将影响力最大化问题建模为在特定传播模型上寻找影响力最大的k个节点上的离散优化问题，并证明在多种传播模型下，影响力最大化问题是一个NP-hard问题，并他们在这个理论基础上提出了性能近似达到最优解63%的贪心爬山算法（即每次从当前解的临近解空间中选择一个最优解作为当前解，直到达到一个局部最优解），但缺点是此方法较为耗时，不适合大规模网络；Leskovec等人^[4]提出了CELF算法，是贪心爬山算法的改进版，利用影响传播函数的子模特性，延迟边际收益计算，时间效率提高了数百倍；后来Chen、Wang等人^[5]进一步优化了贪心算法，提出了NewGreedy和MixedGreedy算法，在独立级联模型下，NewGreedy算法以1-p的概率去掉原图中的每条边，从而得到一个更小的子图，然后在子图中考虑影响力最大化问题，另一种MixedGreedy算法是混合采用NewGreedy算法和CELF算法，实验表明MixedGreedy性能更优。然而，改进后的贪心算法时间复杂度依然较高，并不适合大规模的社会网络。

（二）启发式算法

为了克服贪心算法的低效性，人们提出了启发式算法来解决影响力最大化问题。Chen等人^[5]在度基础上提出了DegreeDiscount算法，其思想为当一个节点v有邻居节点被选为种子节点时，就要在计算它的度时打一定折扣；Esteacute;vez Pablo A等人^[6]为避免选取度数最大的节点而产生邻居重叠现象，提出了SCG算法，来做到尽可能把种子节点分散；后来Chen等人^[7]又提出了PMIA算法，通过计算每个节点的本地树结构，加快影响传播的计算和更新，有比较稳定的影响范围而且运行速度比贪心算法提高了三个数量级，但这一算法也有一个缺点，就是需要占用大量内存；在此之后Jung等人^[8]提出了一种被认为是在运行时间、耗费内存以及影响范围等三个方面综合排名第一的算法：IRIE算法，该算法的思想是通过全局影响力排名算法计算每个节点的全局影响力排名，根据排名次序选择影响力节点，为避免节点影响力重叠问题，在选择一个种子节点之后，利用影响力评估算法估计网络中剩余节点的影响力变化，再根据节点变化后的影响力更新节点影响力排名，如此循环直至找到k个影响力节点。

上面介绍的两种算法是当今在影响力最大化这个问题上最常用到的方法，在这个问题上国内的学者们也有很多的研究。曹玖新、董丹等人^[17]在考虑节点影响区域的重叠问题的基础上，提出了一种基于k-核的CCA（核覆盖）算法，取得比一般启发式算法更优的影响效果，且运行时间更少；朱玉婷、李雷等人^[18]充分考虑主题对主题对影响力节点挖掘的影响而导致特定主题下节点集合的影响范围不大这一问题，提出了一种基于主题的影响力最大化算法TIM，利用个节点间主题相似度来计算节点影响概率，从而提高影响力评价的准确度；孙子力、彭舰等人^[19]则考虑到网络传播模型信息传播过程中的信息衰减问题，提出了基于社群衰减的影响力最大化算法IMID，首先对整个社会网络进行社群结构划分，在信息传播过程中增加节点间信息传播衰减度计算；曹玖新、崔桂旗等人^[21]考虑到成本问题的影响力最大化问题，利用影响力不同的节点被选择代价不同这一条件，并结合节点主题相似度，提出了一种基于平均概率的种子节点选择算法AvePA；李敏佳等人^[22]提出了基于结构洞的社会网络影响力最大化算法，引入效率值这一概念作为结构洞节点的评价标准，从而找到结构洞节点，并通过贪心算法找出其中影响力值较大的k个节点作为种子节点；胡庆成等人^[20]考虑到重叠社区划分问题，根据在现实社会网络中跨越多个社交圈子的节点能把信息传播到不同领域，提出了K-clique Heuristic算法。

总的来说，在广告投放优化研究方面，特别是该课题所包含的主体部分社会网络中的影响力最大化问题已经有了很多比较成熟的结论，但有些算法较为复杂，并不适合大型社会网络分析，而且更多的研究是在算法研究上，综合考虑各个实际因素（如成本、节点主题相似度、重叠影响区域等）来进行研究的较少，本课题将围绕影响力最大化与实际条件结合的问题来进行研究，建立广告投放优化决策模型。

四、方案（设计方案、或研究方案、研制方案）论证：

本课题的研究过程主要是通过阅读相关文献，总结社会网络影响力最大化方法，结合实际条件建立一个广告投放优化决策模型，并最终通过真实数据予以验证，方案主要如下：

首先运用文献综述法，总结得到当前主要的社会网络影响力最大化算法；其次结合实际，比较独立级联模型和线性阈值模型，建立合适的信息传播模型；然后根据信息传播模型的需求获取相关数据，并建立起相应的社会网络；接着在考虑成本的情况下，建立节点主题相似度算法；之后由相似度来计算节点间影响概率，建立影响力最大化模型，最终得到广告投放优化决策模型；在得到优化决策模型后，再次运用数据予以运算，以验证模型性能，从而得到最终结论。

五、进度安排：

2月25日-3月3日 完成任务书

3月4日-3月30日 收集资料及完成开题报告和详细大纲

3月31日-4月15日 收集并处理相关数据

4月16日-5月13日 完成论文初稿

5月14日-5月27日 修改论文，定稿

5月28日-6月10日 准备论文答辩，上传各种答辩资料

参考文献：

[1] Danaher P J,Rust R T.Determining the optimal return on investment for an advertising campaign[J].European Journal of Operational Research,1996, 95(3):511-521.

[2] Pedro Domingos,Matt Richardson.Mining the network value of customers [C].//Proceedings of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco,USA,2001:57-66.

[3] Kempe D,Kleinberg J,Tardos eacute;va.Maximizing the spread of influence through a social network[C].//Acm Sigkdd International Conference on Knowledge Discovery amp; Data Mining. ACM, 2003:137.

[4] Jure Leskovec,Andreas Krause,Carlos Guestrin,et al. Cost-effective outbreak detection in networks[C].// Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining.San Jose,USA,2007:420-429.

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

[6] Esteacute;vez, Vera, Saito.Selecting the Most Influential Nodes in Social Networks [C]// International Joint Conference on Neural Networks.IEEE,2007:2397-2402.

[7] Chen W , Wang C , Wang Y . 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, Washington, DC,USA,2010:1029-1038.

[8] Jung K,Heo W,Chen W.IRIE:Scalable and Robust Influence Maximization in Social Networks[J].//Proceedings of the 12th IEEE International Conference on Data Mining.Brussels,Belgium,2012:918-923

[9] Shai Carmi,Eran Shir,Yuval Shavitt, et al.A model of Internet topology using k-shell decomposition[C].Proceedings of the National Academy of Sciences of the United States of America.,2007,104(27):11150-11154.

[10]Lee, Wookey,Leung, Carson Kai-Sang,Song, Justin Jongsu, et al.A Network-Flow Based Influence Propagation Model for Social Networks[C].//2012 Second international conference on cloud and green computing.2012:601-608.

[11]Narayanam, R.,Narahari, Y..A Shapley Value-Based Approach to Discover Influential Nodes in Social Networks[J].IEEE transactions on automation science and engineering: a publication of the IEEE Robotics and Automation Society,2011,8(1):130-147.

[12]Zhan Q , Yang H , Wang C , et al. CPP-SNS: A Solution to Influence Maximization Problem under Cost Control[C].// 2013 IEEE 25th International Conference on Tools with Artificial Intelligence. IEEE, 2014.

[13]Yu Wang,Gao Cong,Guojie Song, et al.Community-based Greedy Algorithm for Mining Top-K Influential Nodes in Mobile Social Networks[C].//16th ACM SIGKDD international conference on knowledge discovery and data mining 2010. vol. 2.2010:1039-1048.

[14]Bharathi S , Kempe D , Salek M . Competitive Influence Maximization in Social Networks[M].Internet and Network Economics. Springer Berlin Heidelberg, 2007.

[15]MICHAEL TRUSOV.Determining Influential Users in Internet Social Networks[J].Journal of marketing research,2010,47(4):P.643-.

[16]Forum E.Influence Maximization in Social Networks:Towards an Optimal Algorithmic Solution[J].Environmental Health Perspectives,2012,117(12):1939-1944.

[17]曹玖新,董丹,徐顺,郑啸,刘波,罗军舟.一种基于k-核的社会网络影响最大化算法[J].计算机学报,2015,38(02):238-248.

[18]朱玉婷,李雷,施化吉,周从华,施磊磊,徐慧.社会网络中基于主题的影响力最大化算法[J].计算机应用研究,2016,33(12):3611-3614.

[19]孙子力,彭舰,仝博.社会网络中基于社群衰减的影响力最大化算法[J/OL].计算机应用:1-6[2019-03-26].http://kns.cnki.net/kcms/detail/51.1307.TP.20180918.1411.006.html.

[20]胡庆成,张勇,邢春晓.基于有重叠社区划分的社会网络影响最大化方法研究[J].计算机科学,2018,45(6):32-35. DOI:10.11896/j.issn.1002-137X.2018.06.005.

[21]曹玖新,崔桂旗,冯雪艳,闵绘宇.社交网络中基于成本的广告投放策略[J].东南大学学报(自然科学版),2018,48(04):583-589.

[22]李敏佳,许国艳,朱帅,张网娟.基于结构洞的社会网络影响力最大化算法[J/OL].计算机应用:1-7[2019-03-26].http://kns.cnki.net/kcms/detail/51.1307.TP.20180725.1318.074.html.

[23]刘钰峰,郅欢欢,周喻鑫.社会网络影响力最大化的核重构算法及传播模型[J].计算机应用与软件,2018,35(06):279-285.

[24]刘济群.国外社交媒体影响力研究述评——进展与启示[J].现代情报,2016, 36(03):158-166 177.

[25]朱丽,吕本富,彭赓.基于AHP法的个人博客影响力评价方法研究[J].数学的实践与认识,2008(15):109-117.

[26]宗娜,田宇,姚伟华,李良.基于SNA的大学生榜样挖掘及影响力测量研究[J].未来与发展,2019,43(02):88-92.

[27]林宏伟,邵培基.基于互联网环境下的企业网络广告投资策略研究[J].中国管理科学,2014,22(02):65-74.

[28]李微山,洪增林,寇晓东,翟国涛.基于社会网络分析的中小企业网络建模研究[J].陕西科技大学学报(自然科学版),2011,29(04):144-148 154.

[29]平亮,宗利永.基于社会网络中心性分析的微博信息传播研究——以Sina微博为例[J].图书情报知识,2010(06):92-97.

[30]康书龙. 基于用户行为及关系的社交网络节点影响力评价[D].北京邮电大学,2011.

[31]刘小平,田晓颖.媒体微博的社会网络结构及其影响力分析[J].情报科学,2018,36(01):96-101 123.

[32]韩忠明,陈炎,刘雯,原碧鸿,李梦琪,段大高.社会网络节点影响力分析研究[J].软件学报,2017,28(01):84-104.

[33]张伯雷. 社会网络信息传播与影响力最大化研究[D].南京大学,2016.

[34]马茜. 社会网络中的节点影响力度量和k-节点集的影响力最大化问题研究[D].山东大学,2017.

[35]夏涛,陈云芳,张伟,陆有为.社会网络中的影响力综述[J].计算机应用,2014, 34(04):980-985.

[36]冯锐,李闻.社交媒体影响力评价指标体系的构建[J].现代传播(中国传媒大学学报),2017,39(03):63-69.

[37]林琛.微博个体信息传播影响力评价模型研究[J].现代图书情报技术,2014(02):79-85.

[38]李军,陈震,黄霁崴.微博影响力评价研究[J].信息网络安全,2012(03):10-13 27.

[39]周生福. 线性阈值模型下影响最大化算法研究[D].云南大学,2014.

[40]王晰巍,张柳,李师萌,王楠阿雪.新媒体环境下社会公益网络舆情传播研究——以新浪微博“画出生命线”话题为例[J].数据分析与知识发现,2017,1(06):93-101.

[41]胡庆成,张勇,许信辉,邢春晓,陈池,陈信欢.一种新的复杂网络影响力最大化发现方法[J].物理学报,2015,64(19):27-38.

[42]马茜,马军.在影响力最大化问题中寻找种子节点的替补节点[J].计算机学报, 2017,40(03):674-686.