Ultra-fast influence maximization with fused sampling and sketches

Official URL: https://risc01.sabanciuniv.edu/record=b2579402_(Table of contents)

Influence Maximization (IM) is the problem of finding a subset of vertices in a social network whose influence reaches the maximum reachability according to a diffusion model. Due to the NP-Hardness of the problem, often, greedy approximation algorithms are applied. However, irregular memory access patterns and the probabilistic nature of the problem make it a challenging yet rewarding optimization target. This thesis proposes three high-performance IM methods and explores their performance considerations for implementation; first, we propose InFuseR-MG, an IM algorithm that uses a hash-based, direction-oblivious pseudo-random number generator and fused sampling to sample edges in undirected networks. Second, we propose HyperFuseR for directed, generic networks; HyperFuseR uses modified Flajolet-Martin sketches to estimate the cardinality of large reachability sets efficiently. Finally, we propose SuperFuseR, a sketch-based IM algorithm that is specifically designed for the multi-GPU setting. SuperFuseR uses a samplingaware sample-space split mechanism to distribute the graph to multiple devices. Also in this work, we discuss performance considerations at each step of the proposed algorithms and provide their high-performance implementations. For each algorithm, we provide detailed experimental results, including performance, quality, and scaling benchmarks.