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

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

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

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