Random graphs as mathematical models of massive scale-free networks have recently become very popular. While a number of interesting properties of them have been proven, huge instances of such networks actually need to be generated for experimental evaluation and to provide artificial data sets. In this paper, we consider generation methods for random graph models based on linear preferential attachment under limited computational resources and investigate our techniques using the well-known Barabasi-Albert (BA) graph model. We present the first two I/O-efficient BA generators, MP-BA and TFP-BA, for the external-memory (EM) model and then extend MP-BA to massive parallelism based on but not limited to GPGPU. Our simple and easily generalizable sequential TFP-BA outperforms a highly tuned implementation of the sequential lineartime BB-BA algorithm by Batagelj and Brandes by several orders of magnitude once the graph size exceeds the available RAM by only 2%. An implementation of MP-BA targeting heterogeneous systems with CPUs and GPUs is 17.6 times faster than BB-BA for instances fitting in main memory and scales well in the EM setting. Both schemes support a number of features in more general preferential attachment models, e.g., seed graphs exceeding main memory, vertices with random initial degrees, the uniform sampling of vertices, directed graphs and edges between two randomly chosen vertices. Compared with previous studies on computer clusters, MP-BA yields competitive results and already poses a viable alternative using only a single machine.
展开▼
