基于連接度的圖聚類方法研究.pdf

1、圖是實(shí)體及其關(guān)系建模的一種常見(jiàn)方法并廣泛地運(yùn)用于Internet，Web結(jié)構(gòu)，社會(huì)網(wǎng)絡(luò)，代謝網(wǎng)絡(luò)，蛋白質(zhì)作用網(wǎng)絡(luò)，文獻(xiàn)共引關(guān)系網(wǎng)絡(luò)，以及通訊網(wǎng)絡(luò)等的結(jié)構(gòu)描述。隨著通訊技術(shù)、計(jì)算機(jī)及網(wǎng)絡(luò)技術(shù)的飛速發(fā)展和社會(huì)信息化進(jìn)程的持續(xù)推進(jìn)，用于描述真實(shí)世界網(wǎng)絡(luò)結(jié)構(gòu)的圖的規(guī)模普遍呈現(xiàn)出指數(shù)增長(zhǎng)趨勢(shì)。這一現(xiàn)象，一方面確定了大型復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)特征研究的必要性和挑戰(zhàn)性;另一方面激發(fā)了很多研究者試圖探索以聚類方法分析、理解和表示它們的濃厚興趣。
　　圖聚類

2、是按照結(jié)點(diǎn)具有的關(guān)聯(lián)特性對(duì)結(jié)點(diǎn)進(jìn)行分類或標(biāo)識(shí)。其目標(biāo)是分組圖的結(jié)點(diǎn)，使其組內(nèi)緊密關(guān)聯(lián)，組間稀疏關(guān)聯(lián)。不同于一般的數(shù)值聚類，圖聚類具有其自身的特殊性。主要是因?yàn)閳D的許多特性，如結(jié)點(diǎn)間的距離，關(guān)聯(lián)關(guān)系等，對(duì)圖中的邊具有高度敏感性;另外，圖的距離往往是整數(shù)，結(jié)點(diǎn)到多個(gè)聚類中心等距的情況十分常見(jiàn)。因此，一般很難簡(jiǎn)單復(fù)制數(shù)值聚類的現(xiàn)有方法達(dá)到圖聚類的目標(biāo)。
　　本文以連通的無(wú)向非加權(quán)圖為研究對(duì)象，在系統(tǒng)地分析和比較幾種典型的圖聚類方法的基礎(chǔ)

3、上，主要完成如下研究工作:
　　(1)提出了結(jié)點(diǎn)連接度和圖的連接度矩陣的概念，并給出了它們的定義及計(jì)算方法，該方法的效率主要依賴于計(jì)算過(guò)程中所用的最短路徑算法。
　　(2)將最大最小距離聚類方法的基本思想與連接度矩陣相結(jié)合，提出了最大最小連接度圖聚類方法，該聚類方法的時(shí)間復(fù)雜度為O((k+3)k/2n)，其中，k是期望的聚類數(shù)目，n是圖的結(jié)點(diǎn)數(shù)。
　　(3)引入結(jié)點(diǎn)相異度和圖的相異度矩陣的概念，給出其具體定義和計(jì)算模型