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

Yi Chen Lo, Cheng Te Li, Shou De Lin

研究成果: Conference contribution

4 引文 斯高帕斯(Scopus)

摘要

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.

原文English
主出版物標題Proceedings - 2012 ASE/IEEE International Conference on Privacy, Security, Risk and Trust and 2012 ASE/IEEE International Conference on Social Computing, SocialCom/PASSAT 2012
頁面229-238
頁數10
DOIs
出版狀態Published - 2012 12月 1
事件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 - Amsterdam, Netherlands
持續時間: 2012 9月 32012 9月 5

出版系列

名字Proceedings - 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
國家/地區Netherlands
城市Amsterdam
期間12-09-0312-09-05

All Science Journal Classification (ASJC) codes

  • 安全、風險、可靠性和品質

指紋

深入研究「Parallelizing preferential attachment models for generating large-scale social networks that cannot fit into memory」主題。共同形成了獨特的指紋。

引用此