資源描述：
《基于多核心工作站機(jī)群的并行介數(shù)算法.pdf》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、上海理工大學(xué)學(xué)報(bào)第34卷第6期J．UniversityofShanghaiforScienceandTechnologyVo1．34No．62012文章編號：1007—6735(2012}06—0527—04基于多核心工作站機(jī)群的并行介數(shù)算法毛國勇，張寧(1．常州工學(xué)院電子信息與電氣212程學(xué)院，常州213002；2．上海理工大學(xué)管理學(xué)院，上海200093)摘要：針對計(jì)算大規(guī)模復(fù)雜網(wǎng)絡(luò)時(shí)介數(shù)的空間和時(shí)間復(fù)雜度問題，根據(jù)網(wǎng)絡(luò)數(shù)據(jù)的存儲特點(diǎn)，設(shè)計(jì)了減少內(nèi)存占用并能提高查找速度的數(shù)據(jù)結(jié)構(gòu)．根據(jù)介數(shù)計(jì)算的特點(diǎn)，用Python語言設(shè)計(jì)了粗粒度并
2、行算法，在多核心工作站機(jī)群實(shí)現(xiàn)了并行算法．實(shí)驗(yàn)結(jié)果表明：并行算法不僅能夠適用于上億條邊規(guī)模的網(wǎng)絡(luò)，而且能夠獲得線性加速比，使120個(gè)計(jì)算核心的加速比達(dá)到了71左右，為分析大規(guī)模復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)的特性提供了易操作的方案．關(guān)鍵詞：大規(guī)模；復(fù)雜網(wǎng)絡(luò)；介數(shù)；并行計(jì)算中圖分類號：TP338．6文獻(xiàn)標(biāo)志碼：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大規(guī)模網(wǎng)絡(luò)分析在許多重要領(lǐng)域，如社會網(wǎng)絡(luò)、使用的一個(gè)指標(biāo)．通過這個(gè)指標(biāo)，可以對圖中節(jié)點(diǎn)的信息傳播網(wǎng)絡(luò)和生物網(wǎng)絡(luò)等領(lǐng)域中有著廣泛的應(yīng)重要程度進(jìn)行定量分析，可以衡量一個(gè)節(jié)點(diǎn)在網(wǎng)絡(luò)用，而介數(shù)(BC)是分析大規(guī)模復(fù)雜網(wǎng)絡(luò)時(shí)廣泛通信中的重要性，識別出網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)．較高的收稿日期：2012—09—19基金項(xiàng)目：國家自然科學(xué)基金資助項(xiàng)目(70971089)；江蘇省高校優(yōu)秀中青年
7、教師和校長境外研究計(jì)劃資助項(xiàng)目；常州工學(xué)院自然科學(xué)基金資助項(xiàng)目(YN1004)作者簡介：毛國勇(1971一)，男，副教授．研究方向：并行計(jì)算、圖論算法．E-mail：maogy@CZU．cn528上海理工大學(xué)學(xué)報(bào)2012年第34卷BC指標(biāo)表明，一個(gè)節(jié)點(diǎn)到其它節(jié)點(diǎn)有相對較多的最短路徑，或者這個(gè)節(jié)點(diǎn)位于其它兩個(gè)節(jié)點(diǎn)最短路2并行BC算法徑上的可能性很大．BC反映了相應(yīng)的節(jié)點(diǎn)在整個(gè)網(wǎng)絡(luò)中的作用和影響力，是一個(gè)重要的全局幾何量，2．1算法的數(shù)據(jù)結(jié)構(gòu)具有很強(qiáng)的現(xiàn)實(shí)意義．例如，在社會關(guān)系網(wǎng)或技術(shù)網(wǎng)求解BC時(shí)，復(fù)雜網(wǎng)絡(luò)的規(guī)模也是計(jì)算中必需絡(luò)中，介數(shù)的
8、分布特征反映了不同人員、資源和技術(shù)面對的問題．在空間復(fù)雜度方面，目前復(fù)雜網(wǎng)絡(luò)主要在相應(yīng)生產(chǎn)關(guān)系中的地位，這對于發(fā)現(xiàn)和保護(hù)關(guān)鍵有鄰接表和鄰接矩陣兩種表示方法．如果用鄰接矩資源、技術(shù)和人才具有重要意義BC的計(jì)算是網(wǎng)絡(luò)陣來表示
