基于Hadoop的社區(qū)發(fā)現(xiàn)算法并行化研究.pdf

1、社區(qū)發(fā)現(xiàn)算法是研究復(fù)雜網(wǎng)絡(luò)中社區(qū)結(jié)構(gòu)的主要方法。隨著網(wǎng)絡(luò)規(guī)模爆發(fā)式的增長，傳統(tǒng)單機(jī)、串行的社區(qū)發(fā)現(xiàn)算法已不適用于處理當(dāng)前大規(guī)模的網(wǎng)絡(luò)。Hadoop作為新興的一種大數(shù)據(jù)處理技術(shù)，因其高擴(kuò)展、高可靠、編程模型簡單受到許多開發(fā)者的青睞。
　　本研究主要內(nèi)容包括：⑴針對(duì)Fast-Newman算法計(jì)算節(jié)點(diǎn)模塊度復(fù)雜度比較高問題，提出基于Hadoop框架調(diào)度的Fast-Newman并行算法。并行化Fast-Newman算法存在的主要難點(diǎn)為在m

2、ap函數(shù)中各節(jié)點(diǎn)無法獲取其鄰居節(jié)點(diǎn)的信息，故還需借助Web服務(wù)提供全局圖信息。改進(jìn)后的Fast-Newman算法將在map函數(shù)中并行的計(jì)算每個(gè)節(jié)點(diǎn)與其鄰居節(jié)點(diǎn)合并后的模塊度增量，在reduce函數(shù)中匯總找出模塊度增量最大的兩個(gè)節(jié)點(diǎn)并將該兩節(jié)點(diǎn)合并，此為一次合并過程。合并后的結(jié)果重新作為map函數(shù)的輸入，迭代執(zhí)行map、reduce過程直到所有節(jié)點(diǎn)合并成一個(gè)社區(qū)。采用Ego-Facebook作為數(shù)據(jù)集，在仿真環(huán)境下實(shí)驗(yàn)結(jié)果表明并行化后的F

3、ast-Newman算法具有較高的加速比。⑵針對(duì)處理大規(guī)模網(wǎng)絡(luò)難問題，提出基于Hadoop的Fast-Unfolding并行化算法PFU(Parallel-Fast-Unfolding)。該算法主要采用“分而治之”的思想，首先將大規(guī)模網(wǎng)絡(luò)分區(qū)并各自合并，然后根據(jù)各分區(qū)合并結(jié)果重構(gòu)網(wǎng)絡(luò)，最后迭代合并重構(gòu)網(wǎng)絡(luò)直到社區(qū)結(jié)構(gòu)不再發(fā)生變化。該并行化方案存在兩個(gè)難點(diǎn)：一是如何保證分區(qū)后邊連接信息不會(huì)丟失；二是分區(qū)完成后如何重構(gòu)網(wǎng)絡(luò)。針對(duì)上述兩個(gè)難點(diǎn)