動態(tài)復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法研究及應(yīng)用.pdf

1、復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)對于分析復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)和功能有重要意義?，F(xiàn)實世界中的多數(shù)網(wǎng)絡(luò)是隨時間演化的，這就需要相應(yīng)的動態(tài)網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法。本文主要研究動態(tài)網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法及應(yīng)用。首先，針對動態(tài)加權(quán)網(wǎng)絡(luò)提出了一種演化社區(qū)發(fā)現(xiàn)算法，該算法結(jié)合歷史社區(qū)結(jié)構(gòu)，不需要給定社區(qū)數(shù)目，能發(fā)現(xiàn)節(jié)點、邊和社區(qū)隨時間變化的社區(qū)結(jié)構(gòu);其次，為了分析網(wǎng)絡(luò)社區(qū)的演化路徑，提出了一種分析動態(tài)網(wǎng)絡(luò)社區(qū)演化路徑的兩階段方法。最后，將本文的動態(tài)網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法和演化分析方法應(yīng)用到

2、我國“985工程”高校校際科研合作網(wǎng)絡(luò)中，結(jié)果表明本文方法具有一定的實用價值。本文的主要研究工作如下:
　　(1)針對節(jié)點數(shù)量、邊的數(shù)量、邊的權(quán)重和社區(qū)數(shù)量隨時間變化的動態(tài)加權(quán)網(wǎng)絡(luò)，提出了一種動態(tài)加權(quán)網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法。該算法在考慮歷史社區(qū)結(jié)構(gòu)的情況下，發(fā)現(xiàn)穩(wěn)定連續(xù)的社區(qū)結(jié)構(gòu)。首先，根據(jù)隸屬度函數(shù)發(fā)現(xiàn)一個以節(jié)點度最大的節(jié)點為中心的初始社區(qū)。然后，利用社區(qū)的鄰居節(jié)點和評價是否將節(jié)點加入社區(qū)的指標(biāo)對初始社區(qū)進行擴展。最后，運用是否將兩個

3、社區(qū)合并的指標(biāo)對整個網(wǎng)絡(luò)的社區(qū)進行合并。此外，分別將本文的算法應(yīng)用于人工合成數(shù)據(jù)和現(xiàn)實世界網(wǎng)絡(luò)數(shù)據(jù)，說明本文算法是有效和可行的。
　　(2)提出一種動態(tài)網(wǎng)絡(luò)社區(qū)演化分析方法。本文提出一個改進的匹配矩陣，根據(jù)相鄰時間步各個社區(qū)所包含成員，計算匹配矩陣。在計算得到的匹配矩陣的基礎(chǔ)上，依次分析所有時間步每個社區(qū)的前件和后件。再根據(jù)社區(qū)的前件和后件分析動態(tài)網(wǎng)絡(luò)社區(qū)的出現(xiàn)、消失、生存、合并和分裂五個事件。最后分析動態(tài)網(wǎng)絡(luò)社區(qū)在不同時間步的演

4、化情況。分別對人工數(shù)據(jù)和現(xiàn)實世界網(wǎng)絡(luò)數(shù)據(jù)進行測試，表明該方法的可行性和有效性。
　　(3)將本文的動態(tài)加權(quán)網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法和動態(tài)網(wǎng)絡(luò)社區(qū)演化路徑分析方法應(yīng)用到“985工程”高校校際科研合作網(wǎng)絡(luò)中。首先，用動態(tài)加權(quán)網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法發(fā)現(xiàn)科研合作網(wǎng)絡(luò)的演化社區(qū)結(jié)構(gòu)，再在此基礎(chǔ)上，運用社區(qū)演化路徑分析方法，分析高?？蒲泻献骶W(wǎng)絡(luò)社區(qū)的演化路徑。實驗表明，本文的動態(tài)網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法能夠有效地發(fā)現(xiàn)動態(tài)網(wǎng)絡(luò)演化社區(qū)結(jié)構(gòu)和社區(qū)演化路徑，對于分析現(xiàn)實