基于多核心工作站机群的并行介数算法  

Parallel Algorithm of Betweenness Centrality in Multicore Cluster of Workstations

作　　者：毛国勇[1] 张宁[2] 

机构地区：[1]常州工学院电子信息与电气工程学院,常州213002 [2]上海理工大学管理学院,上海200093

出　　处：《上海理工大学学报》2012年第6期527-530,共4页Journal of University of Shanghai For Science and Technology

基　　金：国家自然科学基金资助项目(70971089);江苏省高校优秀中青年教师和校长境外研究计划资助项目;常州工学院自然科学基金资助项目(YN1004)

摘　　要：针对计算大规模复杂网络时介数的空间和时间复杂度问题,根据网络数据的存储特点,设计了减少内存占用并能提高查找速度的数据结构.根据介数计算的特点,用Python语言设计了粗粒度并行算法,在多核心工作站机群实现了并行算法.实验结果表明:并行算法不仅能够适用于上亿条边规模的网络,而且能够获得线性加速比,使120个计算核心的加速比达到了71左右,为分析大规模复杂网络数据的特性提供了易操作的方案.Focusing on the space and time complexity problems in computing betweenness centrality in large complex network, the data structure that can reduce the memory consumption and increase execution speed was brought forward based on the storage property of network data. A coarse grain parallel algorithm was designed using Python language according to the features of computing betweenness centrality. The parallel algorithm was realized in the cluster of multi-core workstations. The test results indicate that the algorithm can be applied in the analysis of large network with hundred millions of edges, and has linear speedup. The speedup can reach 71 when 120 cores are used, so as to provide an operational method for the analysis of large scale complex network data.

关 键 词：大规模 复杂网络 介数 并行计算 

分 类 号：TP338.6[自动化与计算机技术—计算机系统结构]