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

doi:10.3778/j.issn.1673-9418.1507073

计算机科学与探索 ›› 2016, Vol. 10 ›› Issue (5): 646-656.DOI: 10.3778/j.issn.1673-9418.1507073

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

谢胜男，刘勇+，朱敬华，谭龙

黑龙江大学计算机科学与技术学院，哈尔滨 150080

出版日期:2016-05-01 发布日期:2016-05-04

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

XIE Shengnan, LIU Yong+, ZHU Jinghua, TAN Long

School of Computer Science and Technology, Heilongjiang University, Harbin 150080, China

Online:2016-05-01 Published:2016-05-04

摘要/Abstract

摘要： 局部影响最大化问题是在社会网中寻找最能影响某个目标节点的种集。现有的研究只考虑对单一目标节点的影响，忽略了传播项上的主题分布以及用户之间基于主题的影响概率。重点研究了在主题分布的条件下，如何选取最能影响目标节点集合的种集，提出了针对目标节点集合的局部影响程度计算方法（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）。多个真实数据的实验结果表明，所提算法可以有效并高效地求解基于主题的局部影响最大化问题。

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

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

Key words: social network, topic-based, local influence maximization, target set

谢胜男，刘勇，朱敬华，谭龙. 社会网中基于主题的局部影响最大化算法研究[J]. 计算机科学与探索, 2016, 10(5): 646-656.

XIE Shengnan, LIU Yong, ZHU Jinghua, TAN Long. Research on Topic-Based Local Influence Maximization Algorithm in Social Network[J]. Journal of Frontiers of Computer Science and Technology, 2016, 10(5): 646-656.

[1]	刘文星, 范敏, 李金海. 网络形式背景下的社区划分方法研究[J]. 计算机科学与探索, 2021, 15(8): 1441-1449.
[2]	冯勇，张冰茹，徐红艳，王嵘冰，张永刚. 结合改进差分进化和模块密度的社区发现算法[J]. 计算机科学与探索, 2020, 14(6): 1070-1080.
[3]	钱付兰，徐涛，赵姝，张燕平. 基于局部概率解的免疫遗传影响力最大化算法[J]. 计算机科学与探索, 2020, 14(5): 783-791.
[4]	董祥祥，高昂，梁英，毕晓迪. 动态社会网络数据发布隐私保护方法[J]. 计算机科学与探索, 2019, 13(9): 1441-1458.
[5]	张晓琳，袁昊晨，李卓麟，张换香，刘娇. 面向子图匹配的社会网络隐私保护方法[J]. 计算机科学与探索, 2019, 13(9): 1504-1515.
[6]	张昱，高克宁，陈默，于戈. 融合网络结构和节点属性的链接预测方法[J]. 计算机科学与探索, 2019, 13(7): 1094-1101.
[7]	张晓琳，何晓玉，张换香，李卓麟. PLRD-(k,m):保护链接关系的分布式k-度-m-标签匿名方法[J]. 计算机科学与探索, 2019, 13(1): 70-82.
[8]	李春英，汤志康，汤庸，赵剑冬，黄泳航. 局部优先的社会网络社区结构检测算法[J]. 计算机科学与探索, 2018, 12(8): 1263-1277.
[9]	张云飞，李劲，岳昆，罗之皓，刘惟一. 关联影响力传播最大化方法[J]. 计算机科学与探索, 2018, 12(12): 1891-1902.
[10]	刘勇，谢胜男，张巍，朱敬华，王楠. 社会网中时间最优的利润最大化算法研究[J]. 计算机科学与探索, 2017, 11(11): 1723-1732.
[11]	陈晓，郭景峰，张春英. 社会网络顶点间相似性度量及其应用[J]. 计算机科学与探索, 2017, 11(10): 1629-1641.
[12]	孙焕良，富珊珊，刘俊岭，于戈，许鸿斐. 社会网络中弱关系团队形成问题研究[J]. 计算机科学与探索, 2016, 10(6): 773-785.
[13]	刘勇，曲思桐，王楠，郭龙江. 不同营销模式中基于时间的影响传播方法研究[J]. 计算机科学与探索, 2016, 10(3): 338-349.
[14]	白宇清，李海健，蔡青松. 移动P2P社会网络中关键节点发现方法[J]. 计算机科学与探索, 2016, 10(3): 350-362.
[15]	张恩德，高克宁，张昱，李封. 结合用户生成内容与链接关系的社区发现算法[J]. 计算机科学与探索, 2016, 10(2): 194-200.

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

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

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics