Ultra-fast influence maximization with fused sampling and sketches

Göktürk, Gökhan (2021) Ultra-fast influence maximization with fused sampling and sketches. [Thesis]

[thumbnail of 10409460.pdf] PDF

Download (1MB)


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.
Item Type: Thesis
Uncontrolled Keywords: Influence maximization. -- Fused sampling. -- Parallel graph algorithms. -- High-performance computing. -- Etki eniyilemesi. -- Örneklem birlestirme. -- Paralel çizge algoritmaları. -- Yüksek basarımlı hesaplama.
Subjects: T Technology > TK Electrical engineering. Electronics Nuclear engineering > TK7800-8360 Electronics > TK7885-7895 Computer engineering. Computer hardware
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Computer Science & Eng.
Faculty of Engineering and Natural Sciences
Depositing User: IC-Cataloging
Date Deposited: 19 Oct 2021 14:37
Last Modified: 26 Apr 2022 10:39
URI: https://research.sabanciuniv.edu/id/eprint/42500

Actions (login required)

View Item
View Item