基于MapReduce的社區(qū)發(fā)現(xiàn)算法的設(shè)計與實(shí)現(xiàn).pdf

1、從人類社會進(jìn)入互聯(lián)網(wǎng)時代以來，各種社交網(wǎng)絡(luò)服務(wù)平臺，為人們提供了低成本的交流方式。但由于互聯(lián)網(wǎng)信息的傳播具有隱蔽性，網(wǎng)絡(luò)間諜、水軍等網(wǎng)絡(luò)敵對勢力會利用其獲取或者傳播信息。所以我國亟需針對龐大數(shù)據(jù)量的社交網(wǎng)站進(jìn)行社區(qū)發(fā)現(xiàn)以監(jiān)控可能存在的敵對勢力用戶社區(qū)。
　　社區(qū)發(fā)現(xiàn)算法一般分成兩類，一類是通過聚類等數(shù)據(jù)挖掘算法進(jìn)行社區(qū)發(fā)現(xiàn);一類是根據(jù)圖論相關(guān)知識，將用戶直接抽象為圖中的節(jié)點(diǎn)，用戶之間的關(guān)系抽象為圖中的邊，從而直接對網(wǎng)絡(luò)拓?fù)溥M(jìn)行社區(qū)

2、發(fā)現(xiàn)。
　　由于傳統(tǒng)單機(jī)運(yùn)行的社區(qū)發(fā)現(xiàn)算法不能夠滿足計算復(fù)雜度，存儲容量等方面的要求，故其不適用于處理大數(shù)據(jù)量的社交網(wǎng)絡(luò)。為了提高算法的計算效率，使得社區(qū)發(fā)現(xiàn)算法能夠應(yīng)用到大數(shù)據(jù)量的社交網(wǎng)絡(luò)中，需要在分布式平臺上實(shí)現(xiàn)社區(qū)發(fā)現(xiàn)算法。分布式開源計算平臺Hadoop中MapReduce框架能夠針對大數(shù)據(jù)量進(jìn)行處理。
　　本文的工作重點(diǎn)總結(jié)如下:
　　1.深入了解MapReduce編程模型，分析了幾種傳統(tǒng)的聚類算法，針對KMe

3、ans算法在初始聚類中心選擇的隨機(jī)性以及孤立節(jié)點(diǎn)對聚類效果的影響等所存在的問題，進(jìn)行了改進(jìn)，提出了初始Canopy的KMeans(KMeans with Canopy based on MapReduce，MRKC)算法，并在MapReduce框架上進(jìn)行了實(shí)現(xiàn)。在此基礎(chǔ)上，分析聚類應(yīng)用于社區(qū)發(fā)現(xiàn)的整體流程，實(shí)現(xiàn)了從社交網(wǎng)絡(luò)上獲取用戶留言數(shù)據(jù)，并對用戶進(jìn)行聚類的相關(guān)算法。
　　2.針對留言獲取可能存在的權(quán)限導(dǎo)致信息不全等問題，提出了

4、基于結(jié)構(gòu)的社區(qū)發(fā)現(xiàn)算法（PREP, COREP and POSTP，MRPCP）。根據(jù)用戶的好友關(guān)系網(wǎng)絡(luò)的信息，計算好友間相似度，對好友關(guān)系拓?fù)溥M(jìn)行分割，最后通過計算連通子圖來劃分社區(qū)。
　　3.研究了拓?fù)洳季值南嚓P(guān)算法，實(shí)現(xiàn)了基于力導(dǎo)引等拓?fù)潼c(diǎn)線結(jié)構(gòu)布局算法和社區(qū)發(fā)現(xiàn)結(jié)果的可視化展現(xiàn)。
　　4.設(shè)計并實(shí)現(xiàn)了基于MapReduce的社區(qū)發(fā)現(xiàn)算法原型實(shí)驗系統(tǒng)，并對本文研究的算法進(jìn)行了實(shí)驗驗證。通過對本文提出的算法與經(jīng)典的社區(qū)發(fā)