基于結(jié)構(gòu)相似度的大規(guī)模社交網(wǎng)絡(luò)聚類算法研究.pdf

1、社交網(wǎng)絡(luò)為社交系統(tǒng)下個(gè)體之間的關(guān)系所組成的復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)。隨著信息時(shí)代互聯(lián)網(wǎng)科技的迅猛發(fā)展，社交網(wǎng)絡(luò)，特別是在線社交網(wǎng)絡(luò)，已成為人與人之間分享信息不可或缺的媒介。社交網(wǎng)絡(luò)中個(gè)體之間的相互連接關(guān)系作為信息的傳播途徑，在很多方面有不可忽視的作用。如廣告投遞，潛在商機(jī)發(fā)現(xiàn)，效果預(yù)測(cè)以及危機(jī)預(yù)警。因此如何從這些龐大的網(wǎng)絡(luò)中獲取有價(jià)值的信息成為了目前重要的研究課題。網(wǎng)絡(luò)結(jié)構(gòu)分析也吸引了眾多研究者的關(guān)注，其中的網(wǎng)絡(luò)聚類即是一種有效的結(jié)構(gòu)分析手段和途徑

2、。然而目前的網(wǎng)絡(luò)聚類算法仍面臨重大的挑戰(zhàn)。首先，現(xiàn)有網(wǎng)絡(luò)聚類算法沒有充分考慮實(shí)際社交網(wǎng)絡(luò)的特性。對(duì)社交網(wǎng)絡(luò)的結(jié)構(gòu)分析不同于一般網(wǎng)絡(luò)聚類，社交網(wǎng)絡(luò)中常常存在一些具有特殊作用的點(diǎn)，同時(shí)節(jié)點(diǎn)間的社交關(guān)系大多為有向的。其次，沒有將大規(guī)模網(wǎng)絡(luò)數(shù)據(jù)的處理作為目標(biāo)。
　　 本文針對(duì)現(xiàn)有社交網(wǎng)絡(luò)聚類中所面臨的問題，提出了一種面向大規(guī)模有向網(wǎng)絡(luò)的結(jié)構(gòu)聚類算法。首先，提出了基于結(jié)構(gòu)相似度的處理有向網(wǎng)絡(luò)的聚類方法。本文對(duì)有向網(wǎng)絡(luò)進(jìn)行聚類操作提出了兩種

3、不同的方法：提出一種兩階段方法，首先將有向網(wǎng)絡(luò)近似為無向網(wǎng)絡(luò)，再使用結(jié)構(gòu)相似度聚類算法進(jìn)行結(jié)構(gòu)分析；對(duì)現(xiàn)有的針對(duì)無向網(wǎng)絡(luò)的方法進(jìn)行改進(jìn)使其能夠直接對(duì)有向網(wǎng)絡(luò)進(jìn)行聚類。其次，針對(duì)社交網(wǎng)絡(luò)的大規(guī)模特性，本文研究了如何將原本非并行的基于結(jié)構(gòu)相似度的聚類算法進(jìn)行并行化，使其能夠處理大規(guī)模網(wǎng)絡(luò)數(shù)據(jù)。算法中，針對(duì)社交網(wǎng)絡(luò)數(shù)據(jù)特性，設(shè)計(jì)了合理的數(shù)據(jù)劃分策略，各機(jī)器之間的數(shù)據(jù)交換策略。本文對(duì)算法進(jìn)行了理論分析，證明采用這種高效率的并行編程框架實(shí)現(xiàn)的并行