基于模糊聚類(lèi)的社團(tuán)劃分算法研究.pdf

1、社團(tuán)結(jié)構(gòu)作為復(fù)雜網(wǎng)絡(luò)的重要特性之一，對(duì)復(fù)雜網(wǎng)絡(luò)進(jìn)行社團(tuán)劃分，則可以通過(guò)對(duì)幾個(gè)小社團(tuán)的研究，以“分而治之”的方式對(duì)整個(gè)系統(tǒng)的模塊、功能及演化進(jìn)行研究，大大降低了直接對(duì)龐大的復(fù)雜系統(tǒng)進(jìn)行研究的復(fù)雜性，還進(jìn)一步加深了對(duì)復(fù)雜系統(tǒng)的組織原則、拓?fù)浣Y(jié)構(gòu)與動(dòng)力學(xué)特性的理解。
　　目前已有的復(fù)雜網(wǎng)絡(luò)的社團(tuán)劃分算法中，大部分的算法主要是非重疊社團(tuán)劃分算法，劃分結(jié)果顯示為網(wǎng)絡(luò)被劃分為若干個(gè)互相獨(dú)立的社團(tuán)，社團(tuán)與社團(tuán)之間沒(méi)有重疊節(jié)點(diǎn)。但是在某些實(shí)際網(wǎng)絡(luò)

2、中，網(wǎng)絡(luò)中存在具有多個(gè)社團(tuán)屬性的節(jié)點(diǎn)即重疊節(jié)點(diǎn)，社團(tuán)之間是存在一定關(guān)聯(lián)的，我們可以根據(jù)重疊節(jié)點(diǎn)進(jìn)而推斷社團(tuán)之間的關(guān)聯(lián)程度，對(duì)于動(dòng)態(tài)的網(wǎng)絡(luò)，根據(jù)重疊節(jié)點(diǎn)還能對(duì)社區(qū)的下一步變化進(jìn)行預(yù)測(cè)，因此，重疊節(jié)點(diǎn)的發(fā)現(xiàn)有特殊的意義和研究?jī)r(jià)值。
　　本文在對(duì)已有的經(jīng)典社團(tuán)劃分算法的研究基礎(chǔ)上，提出了一種基于模糊聚類(lèi)的社團(tuán)劃分算法，可以同時(shí)應(yīng)用于非重疊社團(tuán)和重疊社團(tuán)結(jié)構(gòu)的網(wǎng)絡(luò)的社團(tuán)劃分。
　　基于模糊聚類(lèi)的社團(tuán)劃分算法是一種啟發(fā)式算法，它的啟發(fā)

3、式規(guī)則：將節(jié)點(diǎn)作為模糊聚類(lèi)算法中用于聚類(lèi)的樣本，應(yīng)用模糊聚類(lèi)算法后，屬于同一等價(jià)類(lèi)的樣本對(duì)應(yīng)的節(jié)點(diǎn)應(yīng)屬于相同的社團(tuán)。在傳統(tǒng)的模糊聚類(lèi)算法中，隸屬函數(shù)的值反映的是樣本之間的模糊關(guān)系~R的程度即樣本間的相似程度。將傳統(tǒng)的模糊聚類(lèi)算法應(yīng)用到社團(tuán)劃分中，將節(jié)點(diǎn)作為聚類(lèi)樣本，本文算法的具體工作如下：1、對(duì)傳統(tǒng)的共享鄰居數(shù)的定義進(jìn)行了改進(jìn)，通過(guò)改進(jìn)后的共享鄰居數(shù)定義表示節(jié)點(diǎn)間的相似程度并提出了一種基于節(jié)點(diǎn)間共享鄰居數(shù)的隸屬函數(shù)。2、對(duì)于網(wǎng)絡(luò)中存在重

4、疊節(jié)點(diǎn)的情況，模糊聚類(lèi)算法所得的劃分結(jié)果中，針對(duì)少數(shù)不屬于任何等價(jià)類(lèi)的節(jié)點(diǎn)即重疊節(jié)點(diǎn)候選解，提出了重疊節(jié)點(diǎn)的判別準(zhǔn)則，檢測(cè)出候選解中的重疊節(jié)點(diǎn)。本文提出的算法的時(shí)間復(fù)雜度為22O(n log n)。在 GN經(jīng)典人造網(wǎng)和幾個(gè)實(shí)際網(wǎng)絡(luò)上進(jìn)行測(cè)試，對(duì)社團(tuán)大小規(guī)模已知且不存在重疊社團(tuán)的 GN經(jīng)典人造網(wǎng)的劃分結(jié)果符合真實(shí)情況，算法在實(shí)際網(wǎng)絡(luò)的驗(yàn)證上，通過(guò)與其它算法的劃分結(jié)果進(jìn)行比較，得到的模塊度Q值較高，并且能夠更好的檢測(cè)出實(shí)際網(wǎng)絡(luò)中的重疊節(jié)點(diǎn)。