TY - GEN
T1 - Parallelizing preferential attachment models for generating large-scale social networks that cannot fit into memory
AU - Lo, Yi Chen
AU - Li, Cheng Te
AU - Lin, Shou De
PY - 2012/12/1
Y1 - 2012/12/1
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84873667544&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84873667544&partnerID=8YFLogxK
U2 - 10.1109/SocialCom-PASSAT.2012.28
DO - 10.1109/SocialCom-PASSAT.2012.28
M3 - Conference contribution
AN - SCOPUS:84873667544
SN - 9780769548487
T3 - Proceedings - 2012 ASE/IEEE International Conference on Privacy, Security, Risk and Trust and 2012 ASE/IEEE International Conference on Social Computing, SocialCom/PASSAT 2012
SP - 229
EP - 238
BT - Proceedings - 2012 ASE/IEEE International Conference on Privacy, Security, Risk and Trust and 2012 ASE/IEEE International Conference on Social Computing, SocialCom/PASSAT 2012
T2 - 2012 ASE/IEEE International Conference on Social Computing, SocialCom 2012 and the 2012 ASE/IEEE International Conference on Privacy, Security, Risk and Trust, PASSAT 2012
Y2 - 3 September 2012 through 5 September 2012
ER -