【作者】 张莉；

【导师】 卢鹏丽；

【作者基本信息】 兰州理工大学 ， 计算机技术（专业学位）， 2023， 硕士

【摘要】 随着各种社交平台的不断涌现,海量的数据呈现爆炸式增长,在线社交网络在我们日常生活交流以及许多其它社会活动中扮演着重要的角色,如创新产品或服务的营销活动以及网络空间安全治理等,它的迅速发展引起了人们的广泛关注。影响力最大化(Influence Maximization,IM)问题是社会网络分析中一个热门的话题,它的目的是从网络中选取κ个节点作为初始活跃集合,并通过特定的信息传播模型,使其在网络中具有最大范围的影响力传播。近年来,关于影响力最大化问题的大部分工作仅聚焦于如何实现影响力传播最大化,而不关注其它目标。然而,在实际生活中,影响力最大化并不是一个简单的单目标优化问题。企业在营销中选择影响力大的个体时需要考虑成本因素,在预算成本最小化的基础上找到影响力大的个体才更符合实际营销需要。因此,多目标影响力最大化问题也是值得我们关注的。针对以上问题,本文基于网络拓扑结构,提出了两种算法来识别网络中影响力传播覆盖广且成本小的关键节点集合,主要研究工作如下:(1)提出了一种基于多目标优化的固定种子节点数κ的离散差分进化算法(MultiObjective Discrete Differential Evolution,MODDE)同时解决社会网络中影响力传播最大化和成本约束最小化问题。由于社会网络中每个个体的影响力不同,所以其被选作种子的成本也不同。首先,基于网络拓扑结构,设计了一个预算成本约束函数来衡量网络中种子集合所需的成本,并将该函数与一个影响力传播期望函数形式化为一个多目标影响力最大化问题。其次,将度中心性方法用于突变种群,对染色体中的节点基因排序并选择出度大的节点来代替度小的节点,使染色体种群更加快速地寻找到影响力传播范围更大的Pareto非支配解。最后,在六个真实网络数据集上进行了实验,结果表明,该方法在识别网络中具有影响力的节点和寻找均匀分布的Pareto非支配解方面是有效的。(2)设计了一种可变种子集合大小κ的离散多目标差分进化算法(Discrete Multi-Objective Differential Evolution,DMODE)解决多目标影响力最大化问题。在实际营销中,企业可能会根据不同的需求寻找不同数量的影响力大的用户推广产品,这就导致在网络中寻找种子节点时需要考虑到种子集合大小的可变性。利用线性阈值模型进行影响力传播模拟,并将影响力传播数和种子节点数分别作为影响力传播函数和成本约束函数。在种群突变操作中,利用两种突变策略分别改进DMODE算法的全局探索和局部开发性能,并且在此步骤中提出一个基于度排序的策略来加速算法的收敛。算法在四个真实网络数据集上进行测试,实验结果表明,DMODE算法寻找出的Pareto非支配解具有较大的影响力传播值以及较小的成本值,并且实验验证了两种突变策略相比一种突变策略而言更具竞争优势。更多还原

【Abstract】 With the continuous emergence of various social platforms and the explosive growth of massive data,online social networks play an important role in our daily communication and many other social activities,such as marketing activities of innovative products or services and cyberspace security governance,and its rapid development has attracted widespread attention.Influence Maximization is a hot topic in social network analysis,which aims to select κnodes from the network as the initial active set,and make them have the maximum range of influence propagation in the network by a specific information propagation model.In recent years,most of the work on influence maximization has focused only on how to maximize the spread of influence without focusing on other goals.However,in practice,influence maximization is not a simple single-objective optimization problem.Enterprises need to consider the cost factors when choosing individuals with great influence in marketing,and find influential individuals on the basis of minimizing budget costs to better meet the actual marketing needs.Therefore,the problem of multi-objective influence maximization is also worth our attention.To solve the above problems,based on the network topology structure,this paper proposes two algorithms to identify the set key nodes with wide influence spread coverage and low cost in the network,and the main research work is as follows:(1)A multi-objective discrete differential evolution algorithm with a fixed number of seed nodes κbased on multi-objective optimization is proposed to solve the problem of influence propagation maximization and cost constraint minimization in social networks simultaneously.Because each individual in a social network has different influence,the cost of being selected as a seed is also different.Firstly,based on the network topology,a budget cost constraint function is designed to measure the cost required by the seed set in the network,and the function and an influence propagation expectation function are formalized into a multi-objective influence maximization problem.Secondly,the degree centrality method is applied to the mutant population,where the node genes in chromosomes are sequenced and nodes with high degree are selected to replace those with low degree,allowing chromosome populations to find the Pareto non-dominant solutions with greater influence and propagation range more quickly.Finally,experiments are conducted on six real network datasets,and the results show that the method is effective in identifying influential nodes in the network and finding uniformly distributed Pareto non-dominated solutions.(2)A discrete multi-objective differential evolution algorithm with variable seed set size κis designed to solve the problem of maximizing the influence of multiple objectives.In practical marketing,enterprises may seek different number of influential users to promote products according to different needs,which leads to the need to consider the variability of seed set size when finding seed nodes in the network.The linear threshold model is used to simulate influence propagation,and the number of influence propagation and the number of seed nodes are taken as influence propagation function and cost constraint function respectively.In the population mutation operation,two mutation strategies are used to improve the global exploration and local exploitation performance of DMODE algorithm,and a strategy based on degree ranking is proposed to accelerate the convergence of the algorithm in this step.The algorithm is tested on four real network datasets,and the experimental results show that the Pareto non-dominant solutions found by DMODE algorithm has larger influence propagation and smaller cost,and the experiments verify that the two mutation strategies are more competitive than the one mutation strategy.更多还原