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

Research on Topic-Based Local Influence Maximization Algorithm in Social Network

作　　者：谢胜男[1] 刘勇[1] 朱敬华[1] 谭龙[1] 

机构地区：[1]黑龙江大学计算机科学与技术学院,哈尔滨150080

出　　处：《计算机科学与探索》2016年第5期646-656,共11页Journal of Frontiers of Computer Science and Technology

基　　金：国家自然科学基金No.81273649;黑龙江省自然科学基金No.F201430;黑龙江省教育厅科学技术研究项目Nos.12531476;12531498~~

摘　　要：局部影响最大化问题是在社会网中寻找最能影响某个目标节点的种集。现有的研究只考虑对单一目标节点的影响,忽略了传播项上的主题分布以及用户之间基于主题的影响概率。重点研究了在主题分布的条件下,如何选取最能影响目标节点集合的种集,提出了针对目标节点集合的局部影响程度计算方法(topicbased 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 propagation algorithm （TLPA）. The experimental results on several real datasets show that the proposed algorithms can solve the TLIM problem effectively and efficiently.

关 键 词：社会网 基于主题 局部影响最大化 目标集合 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]