首页 | 本学科首页   官方微博 | 高级检索  
     

电信社群网络中介度的网格并行算法及调度算法
引用本文:陈平,王柏,徐六通,吴斌,王艳辉.电信社群网络中介度的网格并行算法及调度算法[J].北京邮电大学学报,2006,29(Z1):77-81.
作者姓名:陈平  王柏  徐六通  吴斌  王艳辉
作者单位:北京邮电大学 通信软件工程中心 北京 100876
基金项目:国家自然科学基金项目(60402011),北京市教委合作研究项目(SYS100130422)
摘    要:为了解决电信社群网络中介度(图的一个几何量)计算中的海量计算问题,研究并实现了高性能网格并行计算方法。该算法采用层次性的二分法分割数据,能在较短的时间内完成大规模社群网络图的各个顶点中介度计算。为了提高计算的加速比,还提出了一种改进的网格并行调度算法,采用动静态结合的方法来平衡负载。论证表明,改进算法的加速比、并行效率和平衡度都有提高,计算用时与网格上并行计算处理器数目成近似线形关系。

关 键 词:复杂网络  电信社群网络  中介度  网格并行  任务调度算法
收稿时间:2006-01-25

Grid Based Parallel and Schedule Algorithm for Betweenness Computation in Telecom Social Network Graph
CHEN Ping,WANG Bai,XU Liu-tong,WU Bin,WANG Yan-hui.Grid Based Parallel and Schedule Algorithm for Betweenness Computation in Telecom Social Network Graph[J].Journal of Beijing University of Posts and Telecommunications,2006,29(Z1):77-81.
Authors:CHEN Ping  WANG Bai  XU Liu-tong  WU Bin  WANG Yan-hui
Affiliation:Telecom Software Engineering Center, Beijing University of Posts and Telecommunications, Beijing 100876, China
Abstract:For betweeness computation in telecom social network graph with huge amount of data,a grid based parallel algorithm is presented.It adopts the hierarchic dichotomy of data.Meanwhile a new schedule strategy is proposed,that combines static and dynamic methods to reach load balance.The experimental results justified that the algorithm achieves a higher speedup ratio and the parallel efficiency,and the time consumption is approximately proportion to the number of parallel CPUs as well.
Keywords:complex network  telecom social network  betweeness  grid parallel computation  task scheduling algorithm
本文献已被 CNKI 等数据库收录!
点击此处可从《北京邮电大学学报》浏览原始摘要信息
点击此处可从《北京邮电大学学报》下载全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号