大規(guī)模網(wǎng)絡(luò)分析的中心性算法并行化研究.pdf

1、隨著近十幾年互聯(lián)網(wǎng)的飛速發(fā)展，用戶數(shù)量的迅速增加使得海量的用戶數(shù)據(jù)被不斷地制造出來，往往都是幾百萬甚至上千萬的超大規(guī)模數(shù)據(jù)集。因此，如何從如此海量的用戶數(shù)據(jù)中篩選出有用信息，從而進(jìn)一步挖掘其深層的商業(yè)價(jià)值、理解其內(nèi)在的商業(yè)行為以及發(fā)現(xiàn)隱含的新的業(yè)務(wù)增長(zhǎng)點(diǎn)成為一個(gè)重要的研究方向和挑戰(zhàn)。但是互聯(lián)網(wǎng)的不斷深化導(dǎo)致了用戶數(shù)據(jù)規(guī)模的迅速增加，從而給社會(huì)網(wǎng)絡(luò)分析算法和工具帶來了新的要求和挑戰(zhàn)，即大規(guī)模網(wǎng)絡(luò)數(shù)據(jù)分析能力。本文旨在解決單機(jī)多核的系統(tǒng)平臺(tái)

2、下的大規(guī)模網(wǎng)絡(luò)數(shù)據(jù)分析處理。
　　中心性分析是網(wǎng)絡(luò)分析研究中的重點(diǎn)，它主要描述了網(wǎng)絡(luò)中的節(jié)點(diǎn)（個(gè)人或者組織）在網(wǎng)絡(luò)中具有怎樣的權(quán)力，居于怎樣的中心地位，對(duì)于信息在整個(gè)網(wǎng)絡(luò)中如何傳播以及對(duì)傳播有怎樣的控制效果。
　　隨著計(jì)算機(jī)硬件技術(shù)的摩爾式飛速發(fā)展，以及并行技術(shù)和并行算法的日益成熟，我們選擇中心性算法的并行化來解決基于單機(jī)多核的大規(guī)模網(wǎng)絡(luò)數(shù)據(jù)分析問題。以下是本文的主要研究成果：
　　1.本文受到復(fù)雜網(wǎng)絡(luò)小世界的特性的啟

3、發(fā)，結(jié)合算法并行化分而治之的原則，分別對(duì)度中心性、臨近中心性算法進(jìn)行并行化設(shè)計(jì)，尤其在介數(shù)中心性算法中，把圖遍歷（BFS）的過程當(dāng)做獨(dú)立的運(yùn)行模塊，并把處理器分配給它們，實(shí)現(xiàn)并行化運(yùn)算，提出介數(shù)中心性算法的粗粒度和細(xì)粒度并行算法。
　　2.本文充分考慮真實(shí)世界網(wǎng)絡(luò)的非平衡度分布的特性，去除真實(shí)世界網(wǎng)絡(luò)中大量度為1的頂點(diǎn)，并修改并行算法代碼，改進(jìn)優(yōu)化算法。
　　3.本文選擇matlab的并行工具箱，采用parfor數(shù)據(jù)并行編程