基于項點度和頂點個數(shù)的圖聚類算法.pdf

1、聚類(或分類)是數(shù)學(xué)、計算科學(xué)、管理科學(xué)等領(lǐng)域的熱門研究話題,并且在諸如模式識別、數(shù)據(jù)分析、通信、生物以及商務(wù)等領(lǐng)域有著廣泛的應(yīng)用.圖聚類,就是應(yīng)用圖理論方法對圖(頂點集)進(jìn)行分類,是數(shù)據(jù)聚類領(lǐng)域一種很重要的變體.與普通的數(shù)值聚類不同的是,基于圖理論的聚類具有其本身的特殊性,可以用圖來表示數(shù)據(jù)集中的相似程度.
　　 一般來說,圖聚類是按照圖結(jié)點間所具有的關(guān)聯(lián)特性對結(jié)點進(jìn)行分類或標(biāo)識,其最終目標(biāo)是將圖中結(jié)點分組,使其組內(nèi)具有緊密的

2、關(guān)聯(lián),而組間的關(guān)聯(lián)相對稀疏.本文在分析了Moussiades與Vakali(Clustering dense graph:A web site graphparadigm.Information Processing and Management,2010)提出的基于內(nèi)部連通比率(inter connection ratio,ICR)的圖聚類算法(以下簡稱MV-ICR聚類算法)基礎(chǔ)上,進(jìn)行了相應(yīng)的改進(jìn),提出了一個新的聚類指標(biāo)和基于新指標(biāo)

3、的聚類算法.主要工作如下:
　　 (1)提出了一種基于ICR的聚類策略,改進(jìn)了MV-ICR聚類算法中無法將關(guān)系相等的多個類同時歸類的問題,改進(jìn)后的算法使得聚類過程更加快速、聚類結(jié)果更加清晰,較MV-ICR算法更加合理有效.
　　 (2)提出了一種基于類內(nèi)關(guān)聯(lián)頂點個數(shù)的新聚類指標(biāo)(稱為類內(nèi)頂點連接比率),并給出了基于類內(nèi)頂點連接比率的聚類算法；實例分析表明,提出的新算法合理有效.
　　 (3)對ICR算法、ICR改