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

《基于多核心工作站机群的并行介数算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、上海理工大学学报第34卷第6期J．UniversityofShanghaiforScienceandTechnologyVo1．34No．62012文章编号：1007—6735(2012}06—0527—04基于多核心工作站机群的并行介数算法毛国勇，张宁(1．常州工学院电子信息与电气212程学院，常州213002；2．上海理工大学管理学院，上海200093)摘要：针对计算大规模复杂网络时介数的空间和时间复杂度问题，根据网络数据的存储特点，设计了减少内存占用并能提高查找速度的数据结构．根据介数计算的特点，用Python语言设计了粗粒度并

2、行算法，在多核心工作站机群实现了并行算法．实验结果表明：并行算法不仅能够适用于上亿条边规模的网络，而且能够获得线性加速比，使120个计算核心的加速比达到了71左右，为分析大规模复杂网络数据的特性提供了易操作的方案．关键词：大规模；复杂网络；介数；并行计算中图分类号：TP338．6文献标志码：AParallelAlgorithmofBetweennessCentralityinMulticoreClusterofWorkstationsMA0Guo-yong，ZHANGNincj2(1．DepartmentofElectronicInf

3、ormationandElectricEngineering，ChangzhouInstituteofTechnology，Changzhou213002，China；2．BusinessSchool，ShanghaiUniversityofScienceandTechnology，Shanghai200083，China)Abstract：Focusingonthespaceandtimecomplexityproblemsincomputingbetweennesscentralityinlargecomplexnetwork，t

4、hedatastructurethatcanreducethememoryconsumptionandincreaseexecutionspeedwasbroughtforwardbasedonthestoragepropertyofnetworkdata．AcoarsegrainparallelalgorithmwasdesignedusingPythonlanguageaccordingtothefeaturesofcomputingbetweennesscentrality。Theparallelalgorithmwasreal

5、izedintheclusterofmulti—coreworkstations．Thetestresultsindicatethatthealgorithmcanbeappliedintheanalysisoflargenetworkwithhundredmillionsofedges，andhaslinearspeedup．Thespeedupcanreach71when120coresareused，SOastoprovideanoperationalmethodfortheanalysisoflargescalecomplex

6、networkda切．Keywords：largescale；complexnetwork；betweennesscentrality；parallelcomputing大规模网络分析在许多重要领域，如社会网络、使用的一个指标．通过这个指标，可以对图中节点的信息传播网络和生物网络等领域中有着广泛的应重要程度进行定量分析，可以衡量一个节点在网络用，而介数(BC)是分析大规模复杂网络时广泛通信中的重要性，识别出网络中的关键节点．较高的收稿日期：2012—09—19基金项目：国家自然科学基金资助项目(70971089)；江苏省高校优秀中青年

7、教师和校长境外研究计划资助项目；常州工学院自然科学基金资助项目(YN1004)作者简介：毛国勇(1971一)，男，副教授．研究方向：并行计算、图论算法．E-mail：maogy@CZU．cn528上海理工大学学报2012年第34卷BC指标表明，一个节点到其它节点有相对较多的最短路径，或者这个节点位于其它两个节点最短路2并行BC算法径上的可能性很大．BC反映了相应的节点在整个网络中的作用和影响力，是一个重要的全局几何量，2．1算法的数据结构具有很强的现实意义．例如，在社会关系网或技术网求解BC时，复杂网络的规模也是计算中必需络中，介数的

8、分布特征反映了不同人员、资源和技术面对的问题．在空间复杂度方面，目前复杂网络主要在相应生产关系中的地位，这对于发现和保护关键有邻接表和邻接矩阵两种表示方法．如果用邻接矩资源、技术和人才具有重要意义BC的计算是网络阵来表示