基于圖聚類的社會網(wǎng)絡數(shù)據(jù)挖掘算法研究.pdf

1、近年來，隨著生物化學、社會關系網(wǎng)絡、文本檢索以及 Web分析的廣泛應用，一些比較復雜的結構，已經(jīng)不能用序列、項集描述出來。而圖作為一種普適模型，可以用來描述現(xiàn)實世界各類復雜系統(tǒng)。使用圖可以更好的分析、理解現(xiàn)實復雜的問題。在現(xiàn)實生活中，人們處在各種各樣的社會關系當中，這些社會關系就構成了一張社會關系網(wǎng)絡。這張社會關系網(wǎng)絡描述了社會成員及其相互的關系。從數(shù)據(jù)挖掘的觀點來說，社會關系網(wǎng)絡可以用圖的方式來進行表示。圖中的節(jié)點代表被研究的個體，邊

2、代表個體與個體之間的相互關系。
　　本文通過對經(jīng)典社區(qū)挖掘算法GN(Girvan-Newman algorithm, GN)算法進行研究，結合SCAN(Structural Clustering Algorithm for Networks，SCAN)算法中提出的結構相似性，通過重新定義邊介數(shù)的計算，提出了一種改進的基于結構相似度的社區(qū)挖掘聚類算法GNSCAN(Girvan-Newman algorithm based on SC

3、AN, GNSCAN)及其改進算法IGNSCAN(Improved Girvan-Newman algorithm based on SCAN, IGNSCAN)。同時，使用GN算法與鏈路預測中的資源分配指標RA(Resource Allocation, RA)相結合，提出了一種基于鏈路預測的社區(qū)挖掘算法 GNRA(Girvan-Newman algorithm based on Resource Allocation, GNRA)，及

4、其相應的改進算法IGNRA(Improved Girvan-Newman algorithm based on Resource Allocation, IGNRA)。以上所提出的兩類算法均是采用了分裂的層次聚類思想。使用時間復雜度較低的相似性度量方法代替邊介數(shù)的計算，達到降低GN算法時間復雜度的目的。通過對兩類算法的實現(xiàn)，驗證了所提改進算法具有較低的時間復雜度。
　　本文將圖聚類的思想運用到了社區(qū)發(fā)現(xiàn)當中。將社會關系網(wǎng)絡看作是一