论文部分内容阅读
随着社会网络规模不断扩大，利用社会网络中存在的关系进行信息传播受到研究者广泛关注。受到市场营销中“口碑营销”及“病毒式营销”问题的启发，该问题逐渐演化出一类新的研究方向——影响力最大化问题（简称IMP问题），并在计算机学、信息传播学、社会学等领域引起了研究热潮。IMP问题的研究首先需要依据网络拓扑结构的不同，在网络拓扑的基础上分析网络中信息的传播特征，从而建立信息传播特定模型，设计出高效的影响力最大化算法，算法的目的在于找出一组最具影响力的用户集合（节点集合），用以触发在网络中信息的最大范围传播。 社会网络影响力最大化问题研究具有实际意义，目前已被用于链路预测、推荐系统、网络竞选、舆情预警、突发事件通知等领域，随着网络规模的扩大，影响力最大化问题的研究越发具有价值，它能帮解决大规模网络中重要信息传播等问题，但同时，现有的影响力最大化算法具有以下问题，即难以在保证传播算法传播范围最大化同时降低运行时间。为了解决现有工作的不足，本文提出了新的研究思路，本文主要工作包括: (1)本文对社会网络基本概念做出简要概述，介绍三种基础影响力传播模型及影响力最大化问题算法的评价指标，最后详细介绍现有两类影响力最大化算法，并总结指出现有算法不足以及本文将要改进之处。 (2)本文提出一种基于结构洞的贪心算法(SHBG)。该算法首先对网络中所有节点计算结构洞值，根据结构洞值对节点排序，按一定比例从排序节点中选出候选节点集，使用静态贪心算法对候选节点寻优，最后得到种子节点集。由于算法选择种子节点只从少量结构洞候选集中选取，从而节省了运行时间，同时保证传播范围最大化。实验结果证明SHBG算法在保证影响力传播范围同时能有效地降低运行时间。 (3)本文提出一种基于度与聚类系数的贪心算法(DCBG)。该算法结合节点度与聚类系数两个指标，对网络中节点进行重要性排序，按一定比例从排序节点中选出候选节点，使用静态贪心算法对候选节点寻优，最后得到种子节点集。实验结果证明DCBG算法能近似获得贪心算法的传播范围，同时有效地降低了算法运行时间。