Parallelizing preferential attachment models for generating large-scale social networks that cannot fit into memory

Yi Chen Lo, Cheng Te Li, Shou De Lin

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Citations (Scopus)

Abstract

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.

Original languageEnglish
Title of host publicationProceedings - 2012 ASE/IEEE International Conference on Privacy, Security, Risk and Trust and 2012 ASE/IEEE International Conference on Social Computing, SocialCom/PASSAT 2012
Pages229-238
Number of pages10
DOIs
Publication statusPublished - 2012 Dec 1
Event2012 ASE/IEEE International Conference on Social Computing, SocialCom 2012 and the 2012 ASE/IEEE International Conference on Privacy, Security, Risk and Trust, PASSAT 2012 - Amsterdam, Netherlands
Duration: 2012 Sep 32012 Sep 5

Publication series

NameProceedings - 2012 ASE/IEEE International Conference on Privacy, Security, Risk and Trust and 2012 ASE/IEEE International Conference on Social Computing, SocialCom/PASSAT 2012

Other

Other2012 ASE/IEEE International Conference on Social Computing, SocialCom 2012 and the 2012 ASE/IEEE International Conference on Privacy, Security, Risk and Trust, PASSAT 2012
CountryNetherlands
CityAmsterdam
Period12-09-0312-09-05

    Fingerprint

All Science Journal Classification (ASJC) codes

  • Safety, Risk, Reliability and Quality

Cite this

Lo, Y. C., Li, C. T., & Lin, S. D. (2012). Parallelizing preferential attachment models for generating large-scale social networks that cannot fit into memory. In Proceedings - 2012 ASE/IEEE International Conference on Privacy, Security, Risk and Trust and 2012 ASE/IEEE International Conference on Social Computing, SocialCom/PASSAT 2012 (pp. 229-238). [6406288] (Proceedings - 2012 ASE/IEEE International Conference on Privacy, Security, Risk and Trust and 2012 ASE/IEEE International Conference on Social Computing, SocialCom/PASSAT 2012). https://doi.org/10.1109/SocialCom-PASSAT.2012.28