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

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

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

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