论文部分内容阅读
当前我们正处于信息时代,越来越多的社交软件出现在人们的生活中。不同的社交关系为人类构建了一个巨大的社交网络。在社交网络中,人与人之间存在着不同的社会关系和角色定位,社会网络关系使得人与人之间的距离被拉近,使得信息的快速传播成为了可能。因此,如何通过社交网络传播重要信息成为了研究学者关注的重点。一些学者基于口口相传的营销策略提出了影响力最大化问题。影响力最大化问题的研究目标主要是在网络中找到一些具有影响力的种子节点集合,这些节点在特定的传播模型下能够最大化地影响到周围的邻居节点。当前影响力最大化问题的大部分工作都是围绕着网络的拓扑结构展开,通过网络中一些重要指标寻找种子节点集合。同时,当前大部分算法的目标仅为寻找的一些具有影响力的节点,对于其他目标并不予以关注。而现实中,影响力最大化问题并非一个简单的单目标优化问题,企业在营销中选择影响力大的用户是需要考虑成本因素的,如何在成本开销最小化的基础上寻找影响力最大化的节点更符合现实情况,因此,基于多目标影响力最大化问题的研究也值得我们关注。研究影响力最大化问题的实际意义十分重大,目前,影响力最大化问题的研究成果已经广泛用于个性化推荐,舆情监测和推荐系统,并且取得了显著的研究成果。现如今,随着网络规模的增加,对影响力最大化问题的研究也提出了新的要求,在保证节点质量的同时,提高算法的效率是当前工作的重点。影响力最大化问题是典型的NP-Hard问题,在解决此类问题时,传统方法是通过多次蒙特卡洛模拟获得最终的影响力值,而智能优化算法在解决NP-Hard问题时十分高效,因此,利用智能优化算法解决影响力最大化问题是一个新的思路。现有的智能优化算法可能存在着迭代次数多,收敛慢,寻优能力差等不足之处,为解决现在工作的不足,本文提出了研究影响力最大化问题的新思路,本文的主要工作如下:(1)本文首先介绍基于目标优化的影响力最大化问题,解释了影响力最大化问题的概念和评价指标,介绍了在影响力最大化问题的传播模型和一系列经典算法,总结了在单目标影响力最大化问题和多目标影响力最大化问题现存算法存在的不足之处,引出本文提出的两种算法的改进之处。(2)本文提出了一种基于克隆选择学说的影响力最大化算法(CSAIM)。该算法首先对数据集进行预处理,使用社团发现算法划分并筛选重要社团,对社团中的节点计算特征向量中心性值,按照此值筛选节点并构建候选种子节点池。最后通过克隆选择算法这一智能优化算法迭代寻优,获得最终的种子节点集合。由于候选节点池内的节点质量较高,数量较少,因此算法保障了影响力传播值和运行时间,在三个真实公开数据集上的实验结果表明了CSAIM算法的有效性。(3)本文提出了解决影响力最大化和成本开销最小化的算法(PRNSGA-II)。在现实生活中,寻找种子节点必须考虑付出的成本,如何在预算有限的情况下选择节点是我们研究的重点。PRNSGA-II算法首先删除数据集中存在的小社团和孤立节点,删减了网络规模。然后结合PageRank和EDV设计了第一个目标函数来计算节点的影响力传播值,根据度中心性概念,设计第二个成本函数。对于节点进行非支配排序后,执行交叉变异操作更新种群,不断迭代寻优,获得最后的Pareto最优解集。在三个公开真实数据集的实验结果表明,PRNSGA-II算法的有效性。