IMpart: A Partitioning-based Parallel Approach to Accelerate Influence Maximization
IMpart: A Partitioning-based Parallel Approach to Accelerate Influence Maximization
复制标题
DOI：
10.1109/hipc56025.2022.00028
复制
发表时间：
2022-12
期刊：
影响因子：
--
通讯作者：
Reet Barik;Marco Minutoli;M. Halappanavar;A. Kalyanaraman
中科院分区：
文献类型：
--
作者：
Reet Barik;Marco Minutoli;M. Halappanavar;A. Kalyanaraman
影响最大化(IM)是图问题中的一个基本运算，它涉及模拟现实世界网络上的随机扩散过程。给定一个图G(V，E)，目标是识别一小部分关键的有影响力的“种子”，即k个节点的固定大小的集合，当受到影响时，很可能导致网络中最大数量的节点受到影响。这个问题有许多应用，包括(但不限于)社交网络中的病毒营销，接触网络中的流行病控制，以及在分子网络中寻找有影响力的蛋白质。尽管它很重要，但在规模上实现影响力最大化仍然构成重大挑战。虽然问题是NP难的，但在实践中使用了使用贪婪爬山的高效近似算法。然而，即使在具有数十万个节点的中等大小的输入上，这些算法也会消耗数小时的多线程执行时间。在本文中，我们提出了一种基于划分的方法来加速共享和分布式存储计算机上基于贪婪爬山的IM方法。具体地说，我们提出了两种并行算法--一个使用图划分(IMPARE-METIS)，另一个使用社区感知划分(IMPARE-免费)--在近似质量上有可证明的保证。实验结果表明，与最先进的多线程爬山实现相比，我们的方法能够提供两到三个数量级的加速，而质量损失可以忽略不计。例如，在一个中等大小的输入上(Slashdot：73K节点；905K边)，我们基于分区的共享内存实现产生了4610倍的加速比，将128个线程的运行时间从9h 36m减少到7秒。此外，我们的分布式存储实现将问题规模扩大到具有×106个节点和×108条边的图输入，并支持IM解的亚分钟计算。
Influence maximization (IM) is a fundamental operation among graph problems that involve simulating a stochastic diffusion process on real-world networks. Given a graph G(V, E), the objective is to identify a small set of key influential "seeds"— i.e., a fixed-size set of k nodes, which when influenced is likely to lead to the maximum number of nodes in the network getting influenced. The problem has numerous applications including (but not limited to) viral marketing in social networks, epidemic control in contact networks, and in finding influential proteins in molecular networks. Despite its importance, application of influence maximization at scale continues to pose significant challenges. While the problem is NP-hard, efficient approximation algorithms that use greedy hill climbing are used in practice. However those algorithms consume hours of multithreaded execution time even on modest-sized inputs with hundreds of thousands of nodes. In this paper, we present IMpart, a partitioning-based approach to accelerate greedy hill climbing based IM approaches on both shared and distributed memory computers. In particular, we present two parallel algorithms— one that uses graph partitioning (IMpart-metis) and another that uses community-aware partitioning (IMpart-gratis)— with provable guarantees on the quality of approximation. Experimental results show that our approaches are able to deliver two to three orders of magnitude speedup over a state-of-the-art multithreaded hill climbing implementation with negligible loss in quality. For instance, on one of the modest-sized inputs (Slashdot: 73K nodes; 905K edges), our partitioning-based shared memory implementation yields 4610× speedup, reducing the runtime from 9h 36m to 7 seconds on 128 threads. Furthermore, our distributed memory implementation enhances problem size reach to graph inputs with ×106 nodes and ×108 edges and enables sub-minute computation of IM solutions.