论文部分内容阅读
随着信息技术特别是互联网的巨大创新,微信、Facebook等社交网站在每个人的生活中都已经必不可少。影响力最大化问题是社交网络领域研究的一个重点热门问题,近年来得到了广泛的研究,其目的为在一个社交网络中,找到一个能够获得最大影响力传播的个体群(种子节点集合)。研究者们已经提出了许多有效的算法来解决这个问题,然而,大多数研究只关注如何在一个社交网络中高效的找到目标节点,忽略了真实社交网络的复杂性与多样性,比如激活目标种子节点的代价问题。在本论文中,我们使用进化算法对社交网络的影响力最大化问题进行了研究,详细论述了三项研究工作。首先提出了一种多智能体进化算法用来解决一般的影响力最大化问题;接着针对以往研究的不足进行了进一步的补充,在考虑真实社交网络的特性后建立了影响力最大化代价最小化模型,并提出了一种多目标粒子群算法来解决该问题;最后我们提出了一种社交网络影响力最大化增强算法模型,用于在确定种子节点后,其在网络中的进一步影响力增强工作。具体工作总结如下:基于多智能体进化算法的社交网络影响力最大化算法研究:多智能体算法在大规模网络中具有优异的表现,本文把多智能体进化算法应用于社交网络影响力最大化问题中,提出了一种基于多智能体进化算法的社交网络影响力最大化算法(MAGA-IM)。在本文中,我们设计了邻域竞争算子、增强算子、自学习算子用来快速选取网络中影响传播最大的种子节点集合,另外,为了加速MAGA-IM的收敛,我们还特别设计了种群初始化方法。我们在四种不同规模和平均度的真实社交网络上进行了实验,并对比了两种不同的影响力评估方式。实验结果表明我们提出的算法能高效解决各种网络的影响力最大化问题。基于多目标粒子群优化的社交网络影响力最大化代价最小化算法:传统的影响力最大化问题模型通常假设种子集中每个个体的激活成本是相同的,忽略了它们之间的成本差异,而这点与真实社交网络特性往往是不符的。事实上,如果一家公司计划推销其产品或创意,它会根据个体在网络中的影响力级别支付给种子集合中每个个体不同的报酬,并且所有公司都希望以可接受的最低成本获得最大的影响力。受此启发,我们建立了一种影响力最大化代价最小化(IM-CM)的新问题模型,它可以精确地捕捉现实世界网络的这一特征特征。为了解决这个问题,我们提出了一种多目标离散粒子群优化算法,该算法综合考虑了总代价和总的影响力,其旨在找到各个代价下所能得到的最大影响力值,为决策者提供多种选择,以便他们根据预算进行选择。我们在三个不同的真实网络上对我们的算法进行了检验,其实验结果表明我们提出的算法能有效的解决影响力最大化代价最小化问题,并且有极高的效率。社交网络影响力最大化增强算法:社交网络是一个变化频率极高的网络,当网络变化时,改变种子节点是一个代价很高的选择。如何使用较小的代价在有限的资源下进一步提高种子节点群在网络中的整体影响力是一个很值得研究的问题。我们针对这一问题,提出了一种导向连接(Target-Rewiring)方法用来进一步提高种子节点群在网络中的整体影响力。实验中,在三个真实网络中检验了我们算法的提高效果。实验表明,我们提出的策略能够以很小的代价较大地提高网络的影响力。