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

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

2、中，網(wǎng)絡(luò)中存在具有多個社團(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)程度，對于動態(tài)的網(wǎng)絡(luò)，根據(jù)重疊節(jié)點(diǎn)還能對社區(qū)的下一步變化進(jìn)行預(yù)測，因此，重疊節(jié)點(diǎn)的發(fā)現(xiàn)有特殊的意義和研究價值。
　　本文在對已有的經(jīng)典社團(tuán)劃分算法的研究基礎(chǔ)上，提出了一種基于模糊聚類的社團(tuán)劃分算法，可以同時應(yīng)用于非重疊社團(tuán)和重疊社團(tuán)結(jié)構(gòu)的網(wǎng)絡(luò)的社團(tuán)劃分。
　　基于模糊聚類的社團(tuán)劃分算法是一種啟發(fā)式算法，它的啟發(fā)

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

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