基于半監(jiān)督學(xué)習(xí)的社團劃分算法研究.pdf

1、自然界中存在的大量復(fù)雜系統(tǒng)都可以通過各種各樣的網(wǎng)絡(luò)進行描述。近年來,復(fù)雜網(wǎng)絡(luò)的研究受到了越來越多的關(guān)注,并滲透到從自然科學(xué)到工程科學(xué)甚至社會科學(xué)的多個領(lǐng)域。研究所涉及的網(wǎng)絡(luò)主要有:生命科學(xué)領(lǐng)域的各種網(wǎng)絡(luò)、Internet/WWW網(wǎng)絡(luò)、交通網(wǎng)絡(luò)、社會網(wǎng)絡(luò)、科學(xué)家合作網(wǎng)絡(luò)和語言學(xué)網(wǎng)絡(luò)等等。隨著對網(wǎng)絡(luò)性質(zhì)的深入研究,人們發(fā)現(xiàn)許多網(wǎng)絡(luò)具有一個共同的性質(zhì)一社團結(jié)構(gòu)。諸多學(xué)者從不同角度對如何發(fā)現(xiàn)網(wǎng)絡(luò)中的社團結(jié)構(gòu)問題進行了研究。而當(dāng)復(fù)雜網(wǎng)絡(luò)中存在已知

2、標(biāo)記節(jié)點時,如何更好的利用已知標(biāo)記和未知標(biāo)記節(jié)點訓(xùn)練出優(yōu)秀的分類器進行社團劃分成為了重點問題。而半監(jiān)督學(xué)習(xí)方法恰恰是針對大量無標(biāo)記節(jié)點集與有標(biāo)記節(jié)點集共同進行訓(xùn)練,以得到高性能以及較好泛化能力的學(xué)習(xí)器。因此,半監(jiān)督學(xué)習(xí)的方法能夠更好的解決存在已知標(biāo)記節(jié)點的復(fù)雜網(wǎng)絡(luò)社團劃分問題。本文從半監(jiān)督學(xué)習(xí)角度出發(fā)提出了兩種算法,旨在解決當(dāng)網(wǎng)絡(luò)中存在有標(biāo)記節(jié)點時的社團劃分問題。
　　 基于信息傳遞模型的劃分算法:信息從已知標(biāo)記節(jié)點開始通過節(jié)點

3、間的邊在網(wǎng)絡(luò)中進行傳播,直到每一個未知標(biāo)記節(jié)點接收到所有已知標(biāo)記節(jié)點的信息為止。然后算法分析每一個無標(biāo)記網(wǎng)絡(luò)所接收的每一類已知標(biāo)記節(jié)點的信息量,最終根據(jù)分析結(jié)果對每一個未知標(biāo)記節(jié)點進行標(biāo)記。信息在傳遞過程中,為了更好的模擬現(xiàn)實中信號衰減現(xiàn)象,算法利用信號衰減公式來控制衰減程度。此算法為線性時間復(fù)雜度,因此運行速度較快。實驗結(jié)果表明,在對一些網(wǎng)絡(luò)進行社團劃分時,此算法與GN、Wu-Huberman、Newman等算法有著相同的準(zhǔn)確率,在個

4、別網(wǎng)絡(luò)中,其準(zhǔn)確率要更高一些。
　　 基于引力模型的劃分算法:該算法把節(jié)點看作引力實體,然后將物理學(xué)中的萬有引力定律引入社團劃分算法中。首先計算已知標(biāo)記節(jié)點與未知標(biāo)記節(jié)點之間的引力作用值的大小,然后分析并比較每個已知標(biāo)記節(jié)點對未知標(biāo)記節(jié)點引力作用值的大小,最后根據(jù)一定的規(guī)則將未知標(biāo)記節(jié)點進行標(biāo)記。在實驗中,利用此算法對一些實際網(wǎng)絡(luò)進行分析,結(jié)果表明雖然運行速度比信息傳遞模型算法有所下降,但精度有所提高。而與傳統(tǒng)算法相比,雖然其時