• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>IEEE Transactions on Parallel and Distributed Systems >gIM: GPU Accelerated RIS-Based Influence Maximization Algorithm
【24h】

gIM: GPU Accelerated RIS-Based Influence Maximization Algorithm

机译：GIM：GPU加速RIS的影响最大化算法

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Given a social network modeled as a weighted graph G, the influence maximization problem seeks k vertices to become initially influenced, to maximize the expected number of influenced nodes under a particular diffusion model. The influence maximization problem has been proven to be NP-hard, and most proposed solutions to the problem are approximate greedy algorithms, which can guarantee a tunable approximation ratio for their results with respect to the optimal solution. The state-of-the-art algorithms are based on Reverse Influence Sampling (RIS) technique, which can offer both computational efficiency and non-trivial (1 - 1/e - epsilon)-approximation ratio guarantee for any epsilon > 0. RIS-based algorithms, despite their lower computational cost compared to other methods, still require long running times to solve the problem in large-scale graphs with low values of epsilon. In this article, we present a novel and efficient parallel implementation of a RIS-based algorithm, namely IMM, on GPU. The proposed GPU-accelerated influence maximization algorithm, named gIM, can significantly reduce the running time on large-scale graphs with low values of epsilon. Furthermore, we show that gIM algorithm can solve other variations of the IM problem, only by applying minor modifications. Experimental results show that the proposed solution reduces the runtime by a factor up to 220 x. The source code of gIM is publicly available online.
机译：给定作为加权图G建模的社交网络，影响最大化问题会旨在最初影响K顶点，以最大化特定扩散模型下的受影响的节点的预期数量。已经证明了影响最大化问题是NP-Hard，并且最拟议的问题解决方案是近似贪婪算法，其可以保证它们在最佳解决方案方面的可调近似比。最先进的算法基于反向影响采样（RIS）技术，其可以为任何EPSILON> 0. RIS提供计算效率和非普通（1 - 1 / E-EPSILON）的批量率保证基于算法，​​尽管与其他方法相比较低的计算成本，但仍需要长时间的时间来解决具有低ε的大值的大规模图中的问题。在本文中，我们提出了一种基于RIS的算法，即IMM，GPU的新颖有效的并行实施。所提出的GPU加速影响名为GIM的最大化算法，可以显着减少具有低ε的大型图形的运行时间。此外，我们表明GIM算法可以解决IM问题的其他变体，只能通过应用轻微的修改。实验结果表明，所提出的解决方案将运行时间减少到220 x的因子。 GIM的源代码在线公开提供。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号