基于事件的動態(tài)復雜網(wǎng)絡(luò)社區(qū)演化分析.pdf

1、現(xiàn)實世界中的很多系統(tǒng)可以抽象成復雜網(wǎng)絡(luò)，在復雜網(wǎng)絡(luò)中，社區(qū)結(jié)構(gòu)是最常見也是最重要的拓撲屬性之一。社區(qū)劃分研究以及動態(tài)復雜網(wǎng)絡(luò)的社區(qū)檢測和演化研究使人們對復雜網(wǎng)絡(luò)有了更深的認識，對復雜網(wǎng)絡(luò)內(nèi)部的結(jié)構(gòu)特點有更好的了解，能幫助人們找出復雜網(wǎng)絡(luò)中具有共同點的團體，預測動態(tài)網(wǎng)絡(luò)的行為，揭示隱藏其后的重大事件等，這些研究都具有較好的理論意義和實際的應(yīng)用價值。
　　在對現(xiàn)有的靜態(tài)社區(qū)算法研究的基礎(chǔ)上，提出了一個基于并查集數(shù)據(jù)結(jié)構(gòu)的改進的k-團劃

2、分算法，從而提高了在重疊度較高的復雜網(wǎng)絡(luò)中劃分社區(qū)的時間效率，能在近似線性的時間復雜度內(nèi)劃分所有的社區(qū)。首先求出所有的最大團，然后構(gòu)造一個結(jié)點-團映射和團-團映射，再使用并查集結(jié)構(gòu)存儲已劃分的社區(qū)，并減少不必要的交叉測試的次數(shù)，從而提高劃分的時間效率。通過在真實數(shù)據(jù)集上實驗，發(fā)現(xiàn)該算法是合理和有效的，并且其時間效率比其他的重疊社區(qū)算法要更高一些。
　　研究了基于事件的動態(tài)社區(qū)的演化過程，首先定義了三種演化關(guān)系，以及社區(qū)聚度和社區(qū)散

3、度的定義，接著基于時間片劃分的思想，并結(jié)合改進的重疊社區(qū)劃分算法，對動態(tài)復雜網(wǎng)絡(luò)進行劃分，然后綜合分析相鄰時間片上的社區(qū)演化關(guān)系，刻畫出動態(tài)社區(qū)演化的整個過程，并根據(jù)社區(qū)聚度和社區(qū)散度值，結(jié)合聚散度圖，發(fā)現(xiàn)社區(qū)演化過程中會出現(xiàn)大的聚或是大的散，這種結(jié)構(gòu)突然的大聚大散，可以揭示出隱藏在數(shù)據(jù)中的重大事件。最后，通過在DBLP和安然郵件數(shù)據(jù)集實驗，用實際發(fā)生的事件證明了在社區(qū)演化過程中重大事件對社區(qū)結(jié)構(gòu)突變的影響，并可以通過社區(qū)聚度和社區(qū)散度