Computer Science ›› 2017, Vol. 44 ›› Issue (6): 80-82.doi: 10.11896/j.issn.1002-137X.2017.06.013

Previous Articles     Next Articles

Study on Calculation Method for Internet Topological Parameters Based on MapReduce

ZHU Kai-long, LU Yu-liang and ZHANG Yan-qing   

  • Online:2018-11-13 Published:2018-11-13

Abstract: In order to improve the efficiency of the traditional single machine algorithms in computing Internet topological parameters,we used MapReduce to study the Internet topological parameters algorithms.Through discussing the difficulties of parallelizing the traditional algorithms,this paper gave the concurrent design discipline of graph algorithms based on MapReduce and presented the message passing mechanism of graph algorithms.We designed and improved parallel algorithms to compute 4 topological parameters by using message passing mechanism.The experimental results show that the proposed MapReduce algorithm effectively improves the efficiency,and has a good scalability.

Key words: Internet topological parameters,MapReduce,Message passing mechanism,Parallel algorithm

[1] FALOUTSOS M,FALOUTSOS P,FALOUTSOS C.On power-law relationships of the Internet topology[J].ACM Sigcomm Computer Communication Review,1999,9(4):251-262.
[2] ZENG W,XU M W,WU J P.Survey of Network TopologyModels [J].Application Research of Computers,2005,2(7):1-8.(in Chinese) 曾伟,徐明伟,吴建平.网络拓扑模型评估述评[J].计算机应用研究,2005,2(7):1-8.
[3] 郭世泽,陆哲明.复杂网络基础理论[M].北京:科学出版社,2012:40-43.
[4] FOSTER I,KESSELMAN C.The Grid 2 Blueprint for a newcomputing infrastructure(second edition)[M].Burlinton:Morgan Kaufman,2003.
[5] ISARD M,BUDIU M,YU Y,et al.Dryad:distributed data-parallel programs from sequential building blocks[J].ACM Sigops Operating Systems Review,2007,1(3):59-72.
[6] DEAN J,GHEMAWAT S.MapReduce:Simplified data proces-sing on large clusters [J].Communication of the ACM,2008,1(1):107-113.
[7] VALIANT L G.A bridging model for parallel computation [J].Communications of the ACM,1990,3(8):154-166.
[8] 谷峪,于戈,鲍玉斌.大规模图数据的分布式处理[M].北京:清华大学出版社,2015:23-27.
[9] JIMMY L,MICHAEL S.Design patterns for efficient graph algorithm in MapReduce [C]∥Eighth Workshop on Mining and Learning with Graphs 2010.Washington,DC,2010.
[10] FREEMAN L C.Centrality in social networks:Conceptual clari-fication [J].Social Networks,2012,1(3):215-239.
[11] PROUNTZOS D,PINGALI K.Betweenness centrality:algo-rithms and implementations [J].ACM Sigplan Notices,2013,8(8):35-46.
[12] BRANDES U.A faster algorithm for betweenness centrality[J].Journal of Mathematical Sociology,2010,5(2):163-177.
[13] 汪小帆,李翔,陈关荣.复杂网络理论及其应用[M].北京:清华大学出版社,2006:49-55.
[14] XIE C,MAI L D,DU Z H,et al.Research and analysis of Parallel computing system speedup[J].Computer Engineering and Applications,2003,9(26):66-68.(in Chinese) 谢超,麦联叨,都志辉,等.关于并行计算系统中加速比的研究与分析[J].计算机工程与应用,2003,9(26):66-68.

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!