An effective and efficient parallel approach for random graph generation over GPUs

The widespread usage of random graphs   has been highlighted in the context of database applications for several years. This because such data structures turn out to be very useful in a large family of database applications ranging from simulation to sampling, from analysis of complex networks to study of randomized algorithms, and so forth. Amongst others, Erdős–Rényi Γv,pΓv,p is the most popular model to obtain and manipulate random graphs. Unfortunately, it has been demonstrated that classical algorithms for generating Erdős–Rényi based random graphs do not scale well in large instances and, in addition to this, fail to make use of the parallel processing capabilities of modern hardware. Inspired by this main motivation, in this paper we propose and experimentally assess a novel parallel algorithm for generating random graphs under the Erdős–Rényi model that is designed and implemented in a Graphics Processing Unit (GPU), called PPreZER. We demonstrate the nice amenities due to our solution via a succession of several intermediary algorithms, both sequential and parallel, which show the limitations of classical approaches and the benefits due to the PPreZER algorithm. Finally, our comprehensive experimental assessment and analysis brings to light a relevant average speedup gain of PPreZER over baseline algorithms.

► The novel parallel algorithm PPreZER for generating random graphs under the Erdos–Rényi model over GPUs.
► Analysis and experimental evaluation of state-of-the-art algorithms for random graph generation.
► Implementation of the algorithm PPreZER and its comparative approaches.
► Experimental evaluation and analysis on different data sets and under different settings.
► Obtained significant computational gain over baseline approaches.