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

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