计算机科学 ›› 2017, Vol. 44 ›› Issue (6): 80-82.doi: 10.11896/j.issn.1002-137X.2017.06.013
朱凯龙,陆余良,张岩庆
ZHU Kai-long, LU Yu-liang and ZHANG Yan-qing
摘要： 针对传统单机算法在计算大规模互联网拓扑特征参数时效率低的问题,基于MapReduce分布式计算框架对网络拓扑特征参数算法进行研究。通过分析单机图算法并行移植时存在的问题,提出了图算法并行化设计的原则和消息传递机制；根据设计原则和消息传递机制,为4个网络拓扑参数设计了并行算法。实验证明,并行的拓扑参数算法能够有效提高计算效率,且具备良好的可扩展性。
| [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! |
|
||
首页