基于節(jié)點重要性的社團檢測算法研究.pdf

1、社團結(jié)構(gòu)是網(wǎng)絡(luò)中相同屬性節(jié)點的集合，揭示了復雜網(wǎng)絡(luò)中的隱藏屬性和交互規(guī)律。識別和分析網(wǎng)絡(luò)中的社團結(jié)構(gòu)有助于更深入的了解復雜網(wǎng)絡(luò)的內(nèi)在規(guī)律，探究網(wǎng)絡(luò)中個體的未來演化動態(tài)，預測復雜網(wǎng)絡(luò)的發(fā)展規(guī)律，因此，開展對社團結(jié)構(gòu)檢測的研究具有重要的理論與實際意義。
　　模塊度優(yōu)化算法和標簽傳播算法是現(xiàn)有的兩種較為典型的社團檢測算法。二者在初始化時都是將各個節(jié)點視為一個獨立的社團，這影響了模塊度優(yōu)化算法第一階段的性能；另外，由于標簽傳播算法在計算時

2、選擇目標標簽的隨機性，導致社團檢測結(jié)果不準確，算法的魯棒性較差。針對以上兩個算法存在的問題，本文結(jié)合復雜網(wǎng)絡(luò)的節(jié)點重要性提出了相應(yīng)的改進算法：
　?。?）基于節(jié)點重要性的改進模塊度優(yōu)化社團檢測算法：首先，對網(wǎng)絡(luò)進行預處理，合并度值為1的節(jié)點；然后，對網(wǎng)絡(luò)中節(jié)點進行重要性排序，以序列中若干重要節(jié)點作為中心進行擴展，形成網(wǎng)絡(luò)的初始社團結(jié)構(gòu)；最后以初始社團結(jié)構(gòu)作為節(jié)點形成新圖，以模塊度為衡量標準將新圖的節(jié)點進行相互合并得到最終社團結(jié)構(gòu)。

3、基于4個真實網(wǎng)絡(luò)以及1個人工合成網(wǎng)絡(luò)，選取了MDD算法等7種常用節(jié)點重要性排序算法對網(wǎng)絡(luò)節(jié)點進行重要性排序，與基本模塊度優(yōu)化算法及其它典型算法相比，結(jié)果表明改進模塊度優(yōu)化算法能夠更為有效地檢測出網(wǎng)絡(luò)中的社團結(jié)構(gòu)，對于真實網(wǎng)絡(luò)檢測的模塊度值和NMI值都優(yōu)于其它算法。
　?。?）基于模塊度和節(jié)點重要性的改進標簽傳播算法：算法初始時不為節(jié)點分配標簽，而是將網(wǎng)絡(luò)進行準確和快速的初始劃分，對劃分在一起的節(jié)點分配相同的標簽，減少了標簽數(shù)量；根