论文部分内容阅读
信息时代技术的发展和交流互通的需求，催生出了众多知名的大规模网站，如：微博、微信、Facebook和Twitter等。这些网站已被人们广泛用于社交、信息传播以及影响力扩散等诸多方面。近年来的研究显示，相较于从宣传单和报纸等公共渠道获得推荐信息，人们更乐于从家庭成员或者亲朋好友那里接受商品推荐。这种所谓“口口相传”的社会现象表明，我们可以充分利用这一现象进行针对性的信息投放，以获得更为广泛的传播效果。这一问题作为病毒营销领域的重要研究内容，被归纳为影响力最大化问题(Influence Maximization)。基于社交网络的影响力最大化问题，经过多年的研究形成了众多分支内容。
本文主要关注的研究内容包括两个方面：首先是考虑网络中各个节点因具有不同社会影响力，而具有不同激活代价的有限预算影响力最大化问题；再者就是网络节点间传播概率的合理化表示和预测问题。围绕着上述两个研究方向，本文分别进行了深入的分析研究，主要的工作内容组织如下：
1.由于现有的研究方法重点聚焦影响力最大化问题本身，对于在不同节点具有不同激活代价情况下的，基于有限预算的影响力最大化问题的解决方法有限，且主要集中于对Greedy方法的改进。因此本文在分析网络节点间关系的基础上，提出一种基于模拟退火算法的预算影响力最大化算法BoostSA，该方法能够有效解决Greedy方法依赖蒙特卡洛模拟而导致的计算复杂度过高的问题，并且相较于同类型算法CombinationSA，能够在几乎相同的运算时间内获得更好的影响力结果提升。
2.由于现有研究方法对于节点间的传播概率缺乏有效的特征表示和预测，多数情况下仅假设其为某个定值或简单分布，这显然与实际场景存在偏差。而利用节点嵌入表示学习的方法，虽然可以通过对节点的低维向量化表示，来间接实现对连边的低维向量化表示，进而实现对传播概率的合理预测，但不可避免地存在一定程度的信息损失。为此我们提出Combination算法，通过改进现有的边嵌入表示方法line2vec，并有针对性地融入已知的部分传播信息，实现对网络现有连边的合理表示。此外对于节点间组合生成的连边，沿用基于节点嵌入结果进行间接表示的方式。通过将两种表示方式相结合，应用于节点间传播概率的有效预测，在实际网络中的多组实验结果显示，Combination方法相较于原方法具有较好的提升。
3.在利用表示学习方法进行传播概率预测的过程中，现有DeepWalk方法认为可以直接利用已知传播序列，取代随机游走步骤产生的节点序列，实现节点特征的低维向量化表示。针对该做法存在的使用缺陷，我们提出直观的基于重构子图的RBC算法，以及针对RBC算法运行时间瓶颈问题改进后的基于重构完整网络略图的BRBC算法，实现节点序列的合理生成。实验结果显示BRBC算法相较于RBC算法具有较强的运算时间优势，并且较为合理地解决了DeepWalk做法中存在的缺陷。
本文主要关注的研究内容包括两个方面：首先是考虑网络中各个节点因具有不同社会影响力，而具有不同激活代价的有限预算影响力最大化问题；再者就是网络节点间传播概率的合理化表示和预测问题。围绕着上述两个研究方向，本文分别进行了深入的分析研究，主要的工作内容组织如下：
1.由于现有的研究方法重点聚焦影响力最大化问题本身，对于在不同节点具有不同激活代价情况下的，基于有限预算的影响力最大化问题的解决方法有限，且主要集中于对Greedy方法的改进。因此本文在分析网络节点间关系的基础上，提出一种基于模拟退火算法的预算影响力最大化算法BoostSA，该方法能够有效解决Greedy方法依赖蒙特卡洛模拟而导致的计算复杂度过高的问题，并且相较于同类型算法CombinationSA，能够在几乎相同的运算时间内获得更好的影响力结果提升。
2.由于现有研究方法对于节点间的传播概率缺乏有效的特征表示和预测，多数情况下仅假设其为某个定值或简单分布，这显然与实际场景存在偏差。而利用节点嵌入表示学习的方法，虽然可以通过对节点的低维向量化表示，来间接实现对连边的低维向量化表示，进而实现对传播概率的合理预测，但不可避免地存在一定程度的信息损失。为此我们提出Combination算法，通过改进现有的边嵌入表示方法line2vec，并有针对性地融入已知的部分传播信息，实现对网络现有连边的合理表示。此外对于节点间组合生成的连边，沿用基于节点嵌入结果进行间接表示的方式。通过将两种表示方式相结合，应用于节点间传播概率的有效预测，在实际网络中的多组实验结果显示，Combination方法相较于原方法具有较好的提升。
3.在利用表示学习方法进行传播概率预测的过程中，现有DeepWalk方法认为可以直接利用已知传播序列，取代随机游走步骤产生的节点序列，实现节点特征的低维向量化表示。针对该做法存在的使用缺陷，我们提出直观的基于重构子图的RBC算法，以及针对RBC算法运行时间瓶颈问题改进后的基于重构完整网络略图的BRBC算法，实现节点序列的合理生成。实验结果显示BRBC算法相较于RBC算法具有较强的运算时间优势，并且较为合理地解决了DeepWalk做法中存在的缺陷。