Parallelizing Preferential Attachment Models for Generating Large-Scale Social Networks that Cannot Fit into Memory

Social network generation is an important problem in social network analysis. The goal is to produce artificial networks that preserve some real world properties of social networks. As one of most popular social network generation algorithms, the Barabási -- Albert (BA) model is a method that can generate random social networks with power-law degree distribution. This paper discusses the situation of generating large-sized social network that cannot fit into the memory. We design a parallel framework to tackle this problem. The challenge lies in the fact that the preferential attachment mechanism used in the BA model has direct conflict with the concept of parallelism. To achieve the preferential attachment, during the generation processes the degree information of nodes needs to be known, which prohibits the parallelism that allows nodes to generate edges independently. To handle this issue, this paper proposes a method to generate the expected accumulated degree of vertices for the parallel BA model. We further propose several novel techniques to reduce the complexity of generating N vertices with P processes to O(NlogN/P). We implement the model using MapReduce and the experiment results show that our model can produce billion-sized scale-free networks in minutes.