IEEE Transactions on Parallel and Distributed Systems (TPDS)

Yuhong Feng¹  Junpeng Wang¹ Zhiqiang Zhang² Haoming Zhong³ Zhong Ming¹ Xuan Yang¹ Rui Mao¹

¹Shenzhen University ²Beansmile ³WeBank

Abstract

Automated weighted graph construction from massive data is essential to weighted graph theory based data mining processes, where the edge weight computation is time consuming or even fails to complete on a single machine when necessary resources are exhausted. In addition, existing work lacks of the measurement on the accuracy of the edge weights, which represents the graph accuracy and affects the following data mining results. This paper describes the classification, implementation and evaluation of edge weight computation algorithms with MapReduce Framework, which is a powerful parallel and distributed processing model. First, a classification of the edge weight computation algorithms is developed and how they can be applied on MapReduce is also discussed. Then we propose comprehensive measurements on the edge weight accuracy in terms of the number of edges, strength distribution, community structure, Hop-plot and effective diameters. Finally, a performance study has been conducted to evaluate these algorithms in terms of memory and disk usage, execution time and accuracy using a real massive social network application dataset. The results are presented and discussed. Our comparison results can help find out the most effective parallel and distributed edge weight computation algorithm for constructing a weighted graph for a given massive dataset.

Fig. 1. Weighted Graph Contruction Workflow

Fig. 2. Various Applications

Fig. 3. Speeding up computation with parallel & distributed computing technologies & dimension reduction reductions.

Acknowledgements

The authors would like to thank Prof. X. Cheng-zhong for his valued comments on improving the paper. We would also like to appreciate the support by the Shenzhen Science and Technology Foundation (JCYJ20150324140036842, JCYJ2015 0529164656096JCYJ201418193546117 and JCYJ2014050917 2609174), National Natural Science Foundation of China (61103001,61170077, and 61202377), National Key Technology Research and Development Program of the Ministry of Sci-ence and Technology of China (2014BAH28F05), the Guang-dong Province Key Laboratory Project (2012A061400024), the Guangdong Natural Science Foundation (2014A030313553), the National High Technology Joint Research Program of China (2015AA015305), Science and Technology Planning Project of Guangdong Province (2013B090500055), National High Technology Joint Research Program of China (2015AA015305) and NSF-China and Guangdong Province Joint Project (U1301252). Z. Ming and R. Mao are the corre-sponding authors.

Bibtex

@article{

DBLP:journals/tpds/FengWZZMYM16, 

author = {Yuhong Feng and Junpeng Wang and Zhiqiang Zhang and Haoming Zhong and Zhong Ming and Xuan Yang and Rui Mao}, 

title = {The Edge Weight Computation with MapReduce for Extracting Weighted Graphs}, 

journal = {{IEEE} Trans. Parallel Distributed Syst.}, 

volume = {27}, 

number = {12}, 

pages = {3659--3672}, 

year = {2016}, 

}

Downloads