Distributed-Memory Parallel Algorithms for Generating Massive Scale-free Networks Using Preferential Attachment Model

Recently, there has been substantial interest in the study of various random networks as mathematical models of com-plex systems. As these complex systems grow larger, the ability to generate progressively large random networks be-comes all the more important. This motivates the need for efficient parallel algorithms for generating such networks. Naive parallelization of the sequential algorithms for gener-ating random networks may not work due to the dependen-cies among the edges and the possibility of creating duplicate (parallel) edges. In this paper, we present MPI-based dis-tributed memory parallel algorithms for generating random scale-free networks using the preferential-attachment model. Our algorithms scale very well to a large number of proces-sors and provide almost linear speedups. The algorithms can generate scale-free networks with 50 billion edges in 123 seconds using 768 processors