【作者】 陈思；

【导师】 王邦；

【作者基本信息】 华中科技大学 ， 信息与通信工程， 2024， 硕士

【摘要】 在当今社交网络时代,影响力最大化(Influence Maximization,IM)问题受到了研究者的广泛关注。IM旨在选择一组网络中的节点作为种子节点,使影响力传播范围达到最大。该问题的研究对于病毒营销、谣言溯源和舆情引导等应用具有重要意义。在独立级联、线性阈值等影响力传播模型下,IM问题已被证明是一个NP-Hard组合优化问题,研究者们为此提出了各种解决方案。随着深度学习技术的不断发展,基于图表示学习的研究为解决IM问题提供了新的视角和方法。然而,现有的基于图表示学习的方法大多首先对单个节点进行影响力预测及排序,再简单地选择top-k作为种子节点。这忽略了IM是一个组合优化问题的本质,且通常需要较大的训练开销。另外,现实应用中有时需要对特定节点进行影响力传播最大化,而非对网络中所有节点进行影响力最大化传播,这类问题被称为目标影响力最大化(Target Influence Maximization,TIM)问题,图表示学习技术也为这一问题的解决提供了新的途径。本文对IM问题和TIM问题进行了深入研究。首先,对于IM问题提出了编码节点个体激活能力和集合传播能力的IM算法,名为IACD。该算法通过节点ego-net特征编码节点的个体激活能力和构造级联传播图(CDG)编码集合传播能力,预测候选节点在已选种子节点集合下的的影响力边际收益,迭代选择新种子节点。其次,对于TIM问题设计了编码全局影响和集合影响的TIM算法,名为TICI。该算法设计了一种目标感知图嵌入方法Target2Vec,以学习节点的目标感知嵌入向量;设计了由全局影响编码和集合影响编码组成的传播影响编码模块,并融合编码预测种子节点集合影响力,最后利用贪心框架进行新种子节点选择。两个算法均只需在小型网络上进行训练,即可迁移应用至不同规模及拓扑结构性质的其他网络。为验证所提出算法的有效性,本文在多个合成网络和真实网络数据集上进行了实验,并与多个对比算法进行了比较。实验结果表明,本文提出的算法模型能够分别有效地解决IM问题和TIM问题,为IM的研究和应用提供了新的方法和思路。更多还原

【Abstract】 In the era of social networks,the problem of Influence Maximization(IM)has received extensive attention from researchers.IM aims to select a set of nodes in a network as seed nodes to maximize the diffusion of influence.The study of this problem is of great significance for applications such as viral marketing,rumor tracking,and public opinion guidance.Under influence diffusion models such as Independent Cascade and Linear Threshold,IM has been proven to be an NP-hard combinatorial optimization problem,for which various solutions have been proposed by researchers.With the continuous development of deep learning,research based on graph representation learning has provided new perspectives and methods for solving the IM problem.However,existing graph representation learning methods mostly first predict and rank the influence of individual nodes and then simply select the top-k nodes as seed nodes.This overlooks the nature of IM as a combinatorial optimization problem and often requires significant training overhead.In addition,in real-world applications,sometimes it is necessary to maximize the influence diffusion for specific nodes rather than for all nodes in the network.These types of problems are referred to as Target Influence Maximization(TIM)problems,for which graph representation learning techniques also provide new approaches.This paper conducts in-depth research on both IM and TIM problems.Firstly,for the IM problem,an IM algorithm named IACD is proposed.This algorithm encodes the individual activation capacity of nodes using node ego-net features and constructs the Cascade Diffusion Graph(CDG)to encode the collective diffusion capacity,predicting the influence marginal gains of candidate nodes under the selected seed node set,and iteratively selecting new seed nodes.Secondly,for the TIM problem,a TIM algorithm named TICI is designed,which encodes global influence and collective influence.This algorithm designs a Target-aware Graph Embedding method(Target2Vec)to learn node target-aware embedding vectors and a diffusion influence encoding module composed of global influence encoding and collective influence encoding.It integrates the encoding to predict the influence of seed node sets and utilizes a greedy framework for new seed node selection.Both algorithms only need to be trained on small networks and can be transferred to other networks of different scales and topological characteristics.To verify the effectiveness of the proposed algorithms,experiments were conducted on multiple synthetic and real-world network datasets and compared with several benchmark algorithms.Experimental results demonstrate that the proposed algorithm models can effectively solve the IM and TIM problems,providing new methods and perspectives for IM research and applications.更多还原