论文部分内容阅读
影响力最大化问题是指,找到网络中影响力最大的k个节点,作为网络的种子节点,网络中的信息由种子节点,按照一定的传播模型在网络中流动,传播过程中永久性的改变其他节点的状态,最后的目标是让网络中被种子节点集合改变状态的节点总数达到最大。影响力最大化问题是NP-Hard问题。因此如何在网络中获得最接近于最具影响力节点集的一组节点,是影响力最大化研究领域的核心问题。针对这一问题的算法研究主要集中在两个方面,基于贪婪策略的算法与基于网络拓扑结构的启发式算法。其中基于贪婪策略的算法效率很低,无法在大规模网络中应用;而基于网络拓扑结构的启发式算法由于与传播模型结合不紧密等缺点,查找的准确度较低,两类现有的算法都无法获得令人满意的结果。针对现有的影响力最大化相关算法的不足,本文从以下几方面进行改进与优化:首先,我们提出了一种新的基于离散鲸鱼优化的群体智能启发式算法DiWOA。我们重新定义了鲸鱼优化算法的粒子和进化策略,以将其应用在影响力最大化问题中。在初始化阶段我们选择网络中度最大的节点作为原始激活节点,在算法进化过程中加入突变操作,让搜索过程拥有更多的可能性。我们还将影响力传播模型作为启发式算法的适应度函数,将启发式算法与传播模型相结合,最大限度的保证查找结果的准确度。其次,本文在已提出的算法的基础上,利用影响力函数的上限值期望对算法的适应度函数进行优化,将这种策略应用于我们提出的算法UB-DiWOA中。算法通过计算部分节点集的影响力最大值来省略掉许多不必要的计算过程,减小计算规模,在保证准确度的前提下提升算法效率。最后,我们还利用矩阵分析理论将得到的影响力期望上限形式做出了进一步简化,使我们的UB-DiWOA算法在满足特定条件时,可以利用更加简单的适应度函数形式进行影响力最大化节点集识别工作,极大程度地节省计算空间。本文从准确度与算法效率两个角度出发,对我们提出的算法进行了大量的实验验证。实验结果表明,本文提出的基于期望上界的UB-DiWOA算法在算法准确度以及运行效率方面都优于现有的方法。