论文部分内容阅读
自从影响力最大化问题提出以来,就引起了很多学者的研究,提出了各式各样的算法来解决这一问题。其中,尤以贪心算法最为常见。然而,由于贪心及其改进算法的运算复杂度较高,即不适宜在大型网络上运行,也不能满足人们对时间的要求;而以度为基础的一些算法虽然运行速度较快,但结果却不能得到有效的保证。启发式算法在各种复杂问题的优化上都可以取得不错的效果,本文使用基于和声搜索的启发式算法来解决影响力最大化问题。和声搜索算法是一种模拟音乐的创作过程而形成的启发式算法,相比其他的启发式算法,具有收敛速度快、效果好、适应性强等优点。但直接将和声搜索算法应用到影响力最大化问题上,发现其存在两方面的不足:一方面,因为和声搜索算法需要对每次产生的新解进行评估来决定优化的方向,而传统的评估方式都是通过模拟传播来完成,所以每一次的评估都要耗费大量的时间;另一方面,由于节点数目众多,和声搜索算法在影响力最大化问题上的优化速度过慢,需要大量的迭代才能生成不错的解,这又加剧了运行速度过慢的问题。本文针对这两方面的问题对和声搜索算法进行了改进。针对第一个问题,通过计算解的邻居节点的激活期望来作为效果评估的指标。由于原本的评估方式仅适用于独立级联模型,本文对其进行了一定的拓展,使其可以应用在线性阈值模型和权重级联模型上。对于第二个问题,将和声搜索算法在节点度排序的基础上进行优化。首先构成一个按节点度大小排序的解空间,然后剔除掉一些明显不可能的边缘节点来缩小解空间的范围,再通过和声搜索算法进行优化。为了进一步使和声搜索算法的优化速度得到提升,对记忆库取值概率(HMCR)采用分布调整的策略,并且采取按照解空间排序调整和随机选取K步近邻的两种方式来对新解进行微调。通过实验发现,相比原始的和声搜索算法,在本文所使用的三种不同的传播模型中,改进后的算法的优化速度得到了大幅的提高,在影响力最大化问题上取得很好的效果,展现了改进后的算法具有良好的适应性。