位置敏感的社交网中最小种集选取算法研究

• 作者: 张兆功 李建中 李智慧
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: J-MIN-Seed问题 地理位置 基于树的近似模型 影响最大化 社会网络
• 年，卷（期）: 2017,（10）
• 所属期刊栏目: 数据科学与工程
• 页码范围: 2305-2319
• 页数: 15页
• 分类号: TP311
• 字数: 19170字
• 语种: 中文
• DOI: 10.11897/SP.J.1016.2017.02305

摘要

最小种子集合选取问题(J-MIN-Seed问题)的目标是选择一个种子集合S,在影响传播结束后,它不仅需要影响一定数量的用户(如.J个用户),同时S是最小的集合.虽然该问题得到了广泛的研究,但是现有工作却忽略了一个重要事实,即地理位置信息对于J-MIN-Seed问题是非常重要的.在许多真实的应用中,例如位置敏感的口碑营销,都有地理位置的需求.因此,该文将地理位置因素融入到J-MIN-Seed问题中,提出了位置敏感的J-MIN-Seed问题,并证明了该问题是NP-hard问题.该问题的一个挑战是如何高效且有效地计算给定区域的影响范围.为了解决这个挑战,该文对现有的树模型进行扩展,设计出一种高效且有效的近似模型.基于此模型,该文首先提出了朴素的贪心算法MS-Greedy.MS-Greedy虽然有近似保证,但其计算量太大.为满足在线查询的需求,该文又提出了另外两种高效的算法Bound-based和Partition-Assembly-based.大量真实数据的实验结果表明:文中算法能有效地解决位置敏感的J-MIN-Seed问题.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李建中	哈尔滨工业大学海量数据计算研究中心	237	6003	33.0	72.0
2	张兆功	黑龙江大学计算机科学技术学院	13	44	4.0	6.0
3	李智慧	黑龙江大学计算机科学技术学院	2	5	1.0	2.0