社会网中基于主题的局部影响最大化算法研究

摘要

局部影响最大化问题是在社会网中寻找最能影响某个目标节点的种集。现有的研究只考虑对单一目标节点的影响，忽略了传播项上的主题分布以及用户之间基于主题的影响概率。重点研究了在主题分布的条件下，如何选取最能影响目标节点集合的种集，提出了针对目标节点集合的局部影响程度计算方法（topic-based local influence degree computational method，T-LID），在此基础上提出了基于主题的局部影响最大化（topic-based local influence maximization，TLIM）问题，并证明了该问题为NP-hard问题。为求解TLIM问题，提出了基于主题的局部贪心算法（topic-based local greedy algorithm，TLGA）以及基于主题的局部传播算法（topic-based local propagation algorithm，TLPA）。多个真实数据的实验结果表明，所提算法可以有效并高效地求解基于主题的局部影响最大化问题。%Local influence maximization is the problem of finding a small set of seed nodes in a social network that maximizes the influence on a target node. Existing works only consider the influence on a single target node, and also ignore the topic distribution of diffusion items and the influence probabilities between users based on topics. This paper focuses on how to select a seed set that has the maximum influence on a given target set based on the topic distri-bution, and proposes a new topic-based local influence degree computational method (T-LID). Based on T-LID, this paper also proposes a topic-based local influence maximization (TLIM) problem and proves that TLIM is NP-hard. In order to solve TLIM, this paper proposes a topic-based local greedy algorithm (TLGA) and a topic-based local propa-gation algorithm (TLPA). The experimental results on several real datasets show that the proposed algorithms can solve the TLIM problem effectively and efficiently.