Boosting parallel influence-maximization Kernels for undirected networks with fusing and vectorization

Göktürk, Gökhan and Kaya, Kamer (2021) Boosting parallel influence-maximization Kernels for undirected networks with fusing and vectorization. IEEE Transactions on Parallel and Distributed Systems, 32 (5). pp. 1001-1013. ISSN 1045-9219 (Print) 1558-2183 (Online)

Full text not available from this repository. (Request a copy)


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 article 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. In addition, 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-MG which is more than 3000\times3000× faster than the greedy approaches and can run on large graphs that have been considered as too large in the literature. For instance, the new algorithm runs in 2.09, 0.08, 0.36 seconds on graphs Amazon, NetHEP, NetPhy with 16 threads where the sequential baseline takes 141.3, 259.1 and 1725.2 seconds, respectively. To compare INFuseR-MG with the state-of-the-art approximation algorithms, we conduct a thorough experimental analysis with various influence settings. The results on real-life, undirected networks show that on 16 threads, INFuseR-MG is 2.3\times2.3×-173.8\times173.8× faster than state-of-the-art while being superior in terms of influence scores, and using a comparable amount of memory.
Item Type: Article
Uncontrolled Keywords: Monte Carlo methods; Social networking (online); Instruction sets; Memory management; Approximation algorithmsBoostingKernel
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Computer Science & Eng.
Faculty of Engineering and Natural Sciences
Depositing User: Kamer Kaya
Date Deposited: 16 Aug 2022 16:42
Last Modified: 16 Aug 2022 16:42

Actions (login required)

View Item
View Item