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

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

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

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