基于進(jìn)化和局部?jī)?yōu)先的動(dòng)態(tài)網(wǎng)絡(luò)社團(tuán)檢測(cè)算法.pdf

1、作為一種對(duì)現(xiàn)實(shí)中大規(guī)模復(fù)雜系統(tǒng)的抽象工具，復(fù)雜網(wǎng)絡(luò)得到了廣泛的關(guān)注。現(xiàn)實(shí)世界中的復(fù)雜系統(tǒng)往往隨時(shí)間緩慢變化，動(dòng)態(tài)網(wǎng)絡(luò)作為刻畫復(fù)雜網(wǎng)絡(luò)動(dòng)態(tài)性的有效手段，具有很高的研究?jī)r(jià)值。目前對(duì)復(fù)雜網(wǎng)絡(luò)進(jìn)行分析的方法主要集中在社團(tuán)檢測(cè)上。對(duì)動(dòng)態(tài)網(wǎng)絡(luò)進(jìn)行社團(tuán)檢測(cè)，有助于人們認(rèn)識(shí)網(wǎng)絡(luò)特性以及發(fā)展趨勢(shì)，具有重要的理論和實(shí)際意義。
　　傳統(tǒng)的動(dòng)態(tài)網(wǎng)絡(luò)社團(tuán)檢測(cè)算法通常在每個(gè)時(shí)刻對(duì)網(wǎng)絡(luò)快照進(jìn)行劃分，試圖找到“模塊性”較高的社團(tuán)結(jié)構(gòu)，然后分析社團(tuán)之間的關(guān)系。這種

2、方法忽視了動(dòng)態(tài)網(wǎng)絡(luò)的時(shí)序性，難以發(fā)現(xiàn)社團(tuán)結(jié)構(gòu)的演化性。同時(shí)，傳統(tǒng)的社團(tuán)檢測(cè)算法通常以一種“自頂向下”的視角對(duì)網(wǎng)絡(luò)進(jìn)行劃分，這種方法通常難以發(fā)現(xiàn)小于一定規(guī)模的小社團(tuán)。然而，現(xiàn)實(shí)中這些小社團(tuán)可能具有一些實(shí)際的功能和意義。另一方面，現(xiàn)有的動(dòng)態(tài)社團(tuán)檢測(cè)算法通常不能檢測(cè)到社團(tuán)的重疊結(jié)構(gòu)，而重疊性作為社團(tuán)結(jié)構(gòu)的重要特征，很有研究的必要。綜上所述，本文提出了一種基于進(jìn)化和局部?jī)?yōu)先的動(dòng)態(tài)社團(tuán)檢測(cè)算法，對(duì)每個(gè)節(jié)點(diǎn)抽取其EgoMinusEgo子圖，在其上使

3、用標(biāo)簽傳播算法進(jìn)行局部社團(tuán)劃分，之后以一種“自底向上”的視角不斷合并局部社團(tuán)直至得到網(wǎng)絡(luò)的一組劃分。在執(zhí)行合并策略時(shí)，引入了覆蓋率和分布率兩個(gè)指標(biāo)分別代表當(dāng)前社團(tuán)拓?fù)浣Y(jié)構(gòu)與歷史信息兩個(gè)方面，使用進(jìn)化聚類框架來平衡這兩個(gè)指標(biāo)，從而使得到的社團(tuán)具有時(shí)序演化性。
　　本文在真實(shí)網(wǎng)絡(luò)數(shù)據(jù)上對(duì)提出的動(dòng)態(tài)網(wǎng)絡(luò)社團(tuán)檢測(cè)方法進(jìn)行了實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明本文提出的基于進(jìn)化和局部?jī)?yōu)先的社團(tuán)檢測(cè)算法能夠有效地檢測(cè)到社團(tuán)的重疊結(jié)構(gòu)，同時(shí)能夠檢測(cè)到具有實(shí)際意義