一種基于MapReduce的圖結(jié)構(gòu)聚類算法

　　圖結(jié)構(gòu)聚類（SCAN）是一種著名的基于密度的圖聚類算法。該算法不僅能夠找到圖中的聚類結(jié)構(gòu)，而且還能發(fā)現(xiàn)圖中的Hub節(jié)點(diǎn)和離群節(jié)點(diǎn)。然而，隨著圖數(shù)據(jù)規(guī)模越來越大，傳統(tǒng)的SCAN算法的復(fù)雜度為O（tril‘5）（m為圖中邊的條數(shù)），因此很難處理大規(guī)模的圖數(shù)據(jù)。為了解決SCAN算法的可擴(kuò)展性問題，提出了一種新穎的基于MapReduce的海量圖結(jié)構(gòu)聚類算法MRSCAN。具體地，提出了一種計(jì)算核心節(jié)點(diǎn)，以及兩種合并聚類的MapReduce算法。最后，在多個(gè)真實(shí)的大規(guī)模圖數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)測試，實(shí)驗(yàn)結(jié)果驗(yàn)證了算法的準(zhǔn)確性、有效性，以及可擴(kuò)展性。