社会网中基于主题兴趣的影响最大化算法  

Topic-Interest Based Influence Maximization Algorithm in Social Networks

作　　者：刘勇[1,2] 谢胜男[1,2] 仲志伟[1,2] 李金宝 任倩倩[1,2] Liu Yong;Xie Shengnan;Zhong Zhiwei;Li Jinbao;Ren Qianqian(School of Computer Science and Technology,Heilongjiang University,Harbin 150080;Key Laboratory of Database and Parallel Computing of Heilongjiang Province(Heilongjiang University),Harbin 150080)

机构地区：[1]黑龙江大学计算机科学技术学院,哈尔滨150080 [2]黑龙江省数据库与并行计算重点实验室(黑龙江大学),哈尔滨150080

出　　处：《计算机研究与发展》2018年第11期2406-2418,共13页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(61370222;61602159);黑龙江省自然科学基金项目(F201430);哈尔滨科技创新人才研究专项资金项目(2017RAQXJ094);黑龙江省高校基本科研业务费专项资金(HDJCCX-201608)~~

摘　　要：影响最大化问题是在社交网中寻找对传播项最具影响力的种集,使得传播项的传播范围最大.目前的研究只考虑了传播项上主题的分布,而忽略了用户本身的兴趣分布.在传播项的主题分布和用户的兴趣分布都被考虑的条件下,研究如何选取最具影响力的种集.首先提出了基于主题兴趣的独立级联传播模型TI-IC,并利用期望最大化算法求学习TI-IC模型参数;然后在TI-IC模型基础上提出了基于主题兴趣的影响最大化问题TIIM,并提出了求解TIIM问题的启发式算法ACG-TIIM.ACG-TIIM首先构造以每个用户为根的可达路径树,快速粗略预估每个用户的影响范围;然后根据预估的影响范围排序所有结点并选择少量结点作为候选种子;最后使用带有EFLF优化的贪心算法从候选种子中选择最具影响力的种集.多个真实数据集上的实验结果表明:在描述传播规律和预测传播结果方面,TI-IC模型优于经典的IC模型和TIC模型.ACG-TIIM算法可以有效并高效地求解基于主题兴趣的影响最大化问题.Influence maximization is a problem of finding a small set of seed nodes in a social network that maximizes the spread scope of a propagation item.Existing works only take into account the topic distribution on propagation items,but ignore the interest distribution on users.This paper focuses on how to select the most influential seeds when both the topic distribution of propagation items and the interest distribution of users are taken into consideration.A topic-interest independent cascade(TI-IC)propagation model is proposed,and an expectation maximization(EM)algorithm is proposed to learn the parameters of the TI-IC model.Based on the TI-IC model,a topic-interest influence maximization(TIIM)problem is proposed,and a new heuristic algorithm called ACG-TIIM is presented to solve TIIM.ACG-TIIM first takes each user as a root node to construct a reachable path tree,roughly estimate the influence scope of each user,and then sorts all the users according to the estimated influence scope to select a small number of users as candidate seeds,finally uses the greedy algorithm with EFLF optimization to select the most influential seeds from candidate seeds.The experimental results on real datasets show that TI-IC model is superior to classical IC and TIC models in describing propagation law and predicting propagation results.ACG-TIIM can solve the TIIM problem effectively and efficiently.

关 键 词：社会网 影响最大化 主题分布 传播模型 期望最大化 

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