基于項(xiàng)點(diǎn)度和頂點(diǎn)個(gè)數(shù)的圖聚類算法.pdf

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

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

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