全息譜聚類算法在多尺度社團(tuán)檢測(cè)中的研究.pdf

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

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

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