全息譜聚類算法在多尺度社團檢測中的研究.pdf

1、現(xiàn)實生活中存在著各種各樣的復(fù)雜網(wǎng)絡(luò)，這些復(fù)雜網(wǎng)絡(luò)可以看作復(fù)雜系統(tǒng)的高度抽象。隨著對復(fù)雜網(wǎng)絡(luò)的深入研究，研究人員發(fā)現(xiàn)許多實際網(wǎng)絡(luò)都存在一些共同的拓撲特性，如小世界特性、冪律度分布以及社團結(jié)構(gòu)等。其中，社團結(jié)構(gòu)描述的是復(fù)雜網(wǎng)絡(luò)中各群組內(nèi)部節(jié)點間的連接較為緊密，群組之間節(jié)點的連接相對稀疏的特性，是復(fù)雜網(wǎng)絡(luò)最重要的拓撲性質(zhì)之一。因此，復(fù)雜網(wǎng)絡(luò)中的社團檢測問題受到了許多學(xué)者的廣泛研究，針對該問題，本文主要做了以下工作：
　　1.首先介紹了復(fù)

2、雜網(wǎng)絡(luò)中社團結(jié)構(gòu)檢測問題的研究背景與意義，對經(jīng)典社團檢測算法進行了分類，并系統(tǒng)介紹了各算法對應(yīng)的算法原理與思想基礎(chǔ)。重點分析了譜聚類算法的優(yōu)缺點，以及該算法在網(wǎng)絡(luò)社團檢測中的應(yīng)用。
　　2.針對譜聚類算法在復(fù)雜網(wǎng)絡(luò)社團檢測中存在的兩個問題：（1）僅選擇網(wǎng)絡(luò)矩陣的部分特征向量對網(wǎng)絡(luò)節(jié)點聚類，沒有充分考慮到網(wǎng)絡(luò)的全局拓撲結(jié)構(gòu)；（2）矩陣特征向量的計算復(fù)雜度高，譜聚類算法無法適用于具有海量節(jié)點的網(wǎng)絡(luò)。本文對譜聚類算法進行了大幅改進，改進

3、后的算法稱為全息譜聚類算法。全息譜聚類算法釆用網(wǎng)絡(luò)矩陣的所有特征向量聚類，并利用譜圖理論中的Parseval公式，將網(wǎng)絡(luò)節(jié)點對應(yīng)向量的余弦相似性進行了轉(zhuǎn)化，避免了對網(wǎng)絡(luò)矩陣特征向量的計算，降低了算法的計算復(fù)雜度。
　　3.針對網(wǎng)絡(luò)矩陣的特征向量在網(wǎng)絡(luò)節(jié)點聚類中的重要性不同，引入了加權(quán)函數(shù)，通過對網(wǎng)絡(luò)矩陣的所有特征向量加權(quán)，既充分考慮到了網(wǎng)絡(luò)的全局拓撲結(jié)構(gòu)，又考慮到了不同的特征向量對網(wǎng)絡(luò)節(jié)點聚類的重要性問題。另外，為了使全息譜聚類算