高级检索
    刘勇, 谢胜男, 仲志伟, 李金宝, 任倩倩. 社会网中基于主题兴趣的影响最大化算法[J]. 计算机研究与发展, 2018, 55(11): 2406-2418. DOI: 10.7544/issn1000-1239.2018.20170672
    引用本文: 刘勇, 谢胜男, 仲志伟, 李金宝, 任倩倩. 社会网中基于主题兴趣的影响最大化算法[J]. 计算机研究与发展, 2018, 55(11): 2406-2418. DOI: 10.7544/issn1000-1239.2018.20170672
    Liu Yong, Xie Shengnan, Zhong Zhiwei, Li Jinbao, Ren Qianqian. Topic-Interest Based Influence Maximization Algorithm in Social Networks[J]. Journal of Computer Research and Development, 2018, 55(11): 2406-2418. DOI: 10.7544/issn1000-1239.2018.20170672
    Citation: Liu Yong, Xie Shengnan, Zhong Zhiwei, Li Jinbao, Ren Qianqian. Topic-Interest Based Influence Maximization Algorithm in Social Networks[J]. Journal of Computer Research and Development, 2018, 55(11): 2406-2418. DOI: 10.7544/issn1000-1239.2018.20170672

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

    Topic-Interest Based Influence Maximization Algorithm in Social Networks

    • 摘要: 影响最大化问题是在社交网中寻找对传播项最具影响力的种集,使得传播项的传播范围最大.目前的研究只考虑了传播项上主题的分布,而忽略了用户本身的兴趣分布.在传播项的主题分布和用户的兴趣分布都被考虑的条件下,研究如何选取最具影响力的种集.首先提出了基于主题兴趣的独立级联传播模型TI-IC,并利用期望最大化算法求学习TI-IC模型参数;然后在TI-IC模型基础上提出了基于主题兴趣的影响最大化问题TIIM,并提出了求解TIIM问题的启发式算法ACG-TIIM.ACG-TIIM首先构造以每个用户为根的可达路径树,快速粗略预估每个用户的影响范围;然后根据预估的影响范围排序所有结点并选择少量结点作为候选种子;最后使用带有EFLF优化的贪心算法从候选种子中选择最具影响力的种集.多个真实数据集上的实验结果表明:在描述传播规律和预测传播结果方面,TI-IC模型优于经典的IC模型和TIC模型.ACG-TIIM算法可以有效并高效地求解基于主题兴趣的影响最大化问题.

       

      Abstract: 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.

       

    /

    返回文章
    返回