一種多維圖結構聚類的社交關系挖掘算法

　　社交關系的數(shù)據(jù)挖掘一直是大圖數(shù)據(jù)研究領域中的熱門問題。圖聚類算法如SCAN（ Structural clustering　algorithm for networks）雖可迅速地從海量圖數(shù)據(jù)中獲得關系緊密的社區(qū)結構，但這類社區(qū)往往只表示了社交對象的聚集，無法反饋對象間的真實社交關系，如家庭成員、同事、同學等。要獲取對象間真實的社交關系，需要更多維度地挖掘現(xiàn)實中社交對象間復雜的交互關系。對象間的交互維度很多，例如：通話、見面、微信、Email等，而傳統(tǒng)SCAN等聚類算法僅能夠挖掘單維度的交互數(shù)據(jù)。本文在研究社交對象間的多維社交關系圖數(shù)據(jù)與傳統(tǒng)圖結構聚類算法的基礎上，提出了一種有效的子空間聚類算法SCA（ Subspace Cluster Algorithm），首次對多維度下子空間的圖結構聚類進行研究，目的是探索如何通過圖數(shù)據(jù)挖掘發(fā)現(xiàn)對象間真實的社交關系。SCA算法遵循自底向上的原則，能夠發(fā)現(xiàn)社交圖數(shù)據(jù)中所有子空間的聚類集。為了提升SCA的運行速度，我們利用其子空間聚類單調(diào)性進行了性能優(yōu)化，進而提出了剪枝算法SCA+。最后，我們進行了大規(guī)模的性能測試實驗，以及真實數(shù)據(jù)的案例研究，其結果驗證了算法的效率和效用。