电信社群网络中介度的网格并行算法及调度算法

为了解决电信社群网络中介度(图的一个几何量)计算中的海量计算问题，研究并实现了高性能网格并行计算方法。该算法采用层次性的二分法分割数据，能在较短的时间内完成大规模社群网络图的各个顶点中介度计算。为了提高计算的加速比，还提出了一种改进的网格并行调度算法，采用动静态结合的方法来平衡负载。论证表明，改进算法的加速比、并行效率和平衡度都有提高，计算用时与网格上并行计算处理器数目成近似线形关系。

Grid Based Parallel and Schedule Algorithm for Betweenness Computation in Telecom Social Network Graph

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.