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

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

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

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

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