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

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

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

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