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

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

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

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

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