论文标题
增强与融合和矢量化的无向网络的平行影响最大化内核
Boosting Parallel Influence-Maximization Kernels for Undirected Networks with Fusing and Vectorization
论文作者
论文摘要
影响最大化（IM）是找到种子顶点集的问题，该集合有望产生最大影响在图上。它在实践中具有各种应用，例如设计一种有效，有效的方法来传播社交网络中的信息，新闻或广告。该问题表明是NP-HARD，文献中存在具有可证明质量保证的近似算法。但是，这些算法即使对于中等尺度的图，这些算法在计算上也很昂贵。此外，图形算法通常会在内存访问过程中遭受空间和时间不规则性的影响，这在本来已经昂贵的IM内核之上增加了额外的成本。在这项工作中，我们利用融合的采样，记忆和矢量化来进行重组，并行化和提高其在无向网络上的性能。所提出的方法采用伪随机函数，并同时执行多个蒙特卡洛模拟，以有效，有效地利用SIMD泳道。此外，它大大减少了边缘遍历的数量，因此从内存中带来的数据量对于几乎所有内存绑定的图形内核至关重要。我们将提出的方法应用于传统的混合式算法，并提出了漏斗器，该算法比传统的贪婪方法快3000倍，并且可以在文献中被认为太大的大图上运行。
Influence maximization (IM) is the problem of finding a seed vertex set which is expected to incur the maximum influence spread on a graph. It has various applications in practice such as devising an effective and efficient approach to disseminate information, news or ad within a social network. The problem is shown to be NP-hard and approximation algorithms with provable quality guarantees exist in the literature. However, these algorithms are computationally expensive even for medium-scaled graphs. Furthermore, graph algorithms usually suffer from spatial and temporal irregularities during memory accesses, and this adds an extra cost on top of the already expensive IM kernels. In this work, we leverage fused sampling, memoization, and vectorization to restructure, parallelize and boost their performance on undirected networks. The proposed approach employs a pseudo-random function and performs multiple Monte-Carlo simulations in parallel to exploit the SIMD lanes effectively and efficiently. Besides, it significantly reduces the number of edge traversals, hence the amount of data brought from the memory, which is critical for almost all memory-bound graph kernels. We apply the proposed approach to the traditional MixGreedy algorithm and propose Infuser which is more than 3000 times faster than the traditional greedy approaches and can run on large graphs that have been considered as too large in the literature.
