基于節(jié)點(diǎn)重要性的社團(tuán)檢測(cè)算法研究.pdf

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

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

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