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

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

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

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