基于進化和局部優(yōu)先的動態(tài)網(wǎng)絡(luò)社團檢測算法.pdf

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

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

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