| 电信社群网络中介度的网格并行算法及调度算法 |
| |
| 引用本文： | 陈平,王柏,徐六通,吴斌,王艳辉.电信社群网络中介度的网格并行算法及调度算法[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 等数据库收录！ |
| 点击此处可从《北京邮电大学学报》浏览原始摘要信息 |
|
点击此处可从《北京邮电大学学报》下载全文 |
