Comparison of the Efficiency of MapReduce and Bulk Synchronous Parallel Approaches to Large Network Processing

Network structures, especially social networks, grow rapidly and provide huge datasets intractable to analyse. In this paper, two parallel approaches to process large graph structures within the Hadoop environment were compared: Bulk Synchronous Parallel (BSP) and MapReduce (MR). The experimental studies were carried out for two different graph problems: collective classification by means of Relational Influence Propagation (RIP) and Single Source Shortest Path (SSSP) calculation. The appropriate BSP and MapReduce algorithms for these problems were applied to various network datasets differing in size and structural profile, originating from three domains: telecommunication, multimedia and microblog. The collected results revealed that iterative graph processing with BSP implementation significantly outperform popular MapReduce, especially for algorithms with many iterations and sparse communication. However, MapReduce still remains the only alternative for enormous networks.