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

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

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

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

4、基于結(jié)構(gòu)的社區(qū)發(fā)現(xiàn)算法（PREP, COREP and POSTP，MRPCP）。根據(jù)用戶(hù)的好友關(guān)系網(wǎng)絡(luò)的信息，計(jì)算好友間相似度，對(duì)好友關(guān)系拓?fù)溥M(jìn)行分割，最后通過(guò)計(jì)算連通子圖來(lái)劃分社區(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è)計(jì)并實(shí)現(xiàn)了基于MapReduce的社區(qū)發(fā)現(xiàn)算法原型實(shí)驗(yàn)系統(tǒng)，并對(duì)本文研究的算法進(jìn)行了實(shí)驗(yàn)驗(yàn)證。通過(guò)對(duì)本文提出的算法與經(jīng)典的社區(qū)發(fā)