基于局部介數(shù)的復(fù)雜網(wǎng)絡(luò)社區(qū)動(dòng)態(tài)演化研究.pdf

1、網(wǎng)絡(luò)技術(shù)的快速發(fā)展給人們帶來(lái)大量的網(wǎng)絡(luò)資源，如何從浩瀚的網(wǎng)絡(luò)資源中快速有效的找到所需的資源成為當(dāng)今學(xué)者研究的一個(gè)重要課題。學(xué)者們研究發(fā)現(xiàn)這些資源之間并不是毫無(wú)關(guān)聯(lián)的，而是存在著某種聯(lián)系，即網(wǎng)絡(luò)中所呈現(xiàn)出的社區(qū)結(jié)構(gòu)。由于社區(qū)結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)的一個(gè)重要特性，所以研究社區(qū)結(jié)構(gòu)不僅有利于人們更好的認(rèn)識(shí)復(fù)雜網(wǎng)絡(luò)，而且對(duì)解決現(xiàn)實(shí)世界中的疑難問(wèn)題有重要的理論和現(xiàn)實(shí)意義。
　　 本文首先對(duì)復(fù)雜網(wǎng)絡(luò)度量特性進(jìn)行了分析，研究了復(fù)雜網(wǎng)絡(luò)的幾種典型網(wǎng)絡(luò)模

2、型，并對(duì)社會(huì)網(wǎng)絡(luò)進(jìn)行了簡(jiǎn)要描述。然后對(duì)現(xiàn)有網(wǎng)絡(luò)社區(qū)劃分算法進(jìn)行了分析研究，發(fā)現(xiàn)有些算法在某些特定的網(wǎng)絡(luò)中發(fā)現(xiàn)社區(qū)的準(zhǔn)確度較高，但是這些算法執(zhí)行時(shí)間復(fù)雜度也較高，有些算法對(duì)處理結(jié)構(gòu)混亂的網(wǎng)絡(luò)效果好，但是只適用于具有特定結(jié)構(gòu)的網(wǎng)絡(luò)。最后，本文以分析復(fù)雜網(wǎng)絡(luò)動(dòng)態(tài)結(jié)構(gòu)為目的提出了兩種算法，即在動(dòng)態(tài)網(wǎng)絡(luò)中發(fā)現(xiàn)非重疊社區(qū)的算法和發(fā)現(xiàn)重疊社區(qū)的算法。復(fù)雜網(wǎng)絡(luò)的動(dòng)態(tài)特性使得網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法需要加入時(shí)間軸信息，以得到網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)結(jié)果更加真實(shí)。本文首先提出

3、了在動(dòng)態(tài)網(wǎng)絡(luò)中發(fā)現(xiàn)非重疊社區(qū)的算法，該算法是基于GN算法邊介數(shù)的思想基礎(chǔ)，同時(shí)在計(jì)算網(wǎng)絡(luò)邊介數(shù)的過(guò)程中考慮局部計(jì)算，在很大程度上改進(jìn)了算法的時(shí)間復(fù)雜度。首先，算法對(duì)動(dòng)態(tài)網(wǎng)絡(luò)時(shí)間軸上的信息進(jìn)行了整合，井根據(jù)社會(huì)學(xué)經(jīng)驗(yàn)將歷史信息進(jìn)行了信息量衰減，使得到的網(wǎng)絡(luò)數(shù)據(jù)信息更加接近于真實(shí)世界的數(shù)據(jù)信息。其次，根據(jù)網(wǎng)絡(luò)中邊介數(shù)最大的邊是網(wǎng)絡(luò)中關(guān)鍵邊的特性，利用去除網(wǎng)絡(luò)中邊介數(shù)最大的邊而得到不連通子圖，這些不連通的子圖成為了一個(gè)個(gè)的社區(qū)結(jié)構(gòu)。然后，本文

4、在3組數(shù)據(jù)集上進(jìn)行了算法驗(yàn)證，并對(duì)結(jié)果進(jìn)行了分析，發(fā)現(xiàn)算法得到的社區(qū)劃分結(jié)果是比較正確的。最后，在不同數(shù)量級(jí)的數(shù)據(jù)集上，與Framework模型和FacetNet算法進(jìn)行了時(shí)間復(fù)雜度的對(duì)比，發(fā)現(xiàn)本文算法在處理大數(shù)據(jù)集的能力上有明顯優(yōu)勢(shì)。本文基于網(wǎng)絡(luò)中存在一個(gè)節(jié)點(diǎn)可能會(huì)出現(xiàn)在多個(gè)社區(qū)的網(wǎng)絡(luò)特征事實(shí)，提出了另一種動(dòng)態(tài)網(wǎng)絡(luò)中發(fā)現(xiàn)重疊社區(qū)的算法。該算法是在動(dòng)態(tài)網(wǎng)絡(luò)中發(fā)現(xiàn)非重疊社區(qū)算法的基礎(chǔ)上，對(duì)網(wǎng)絡(luò)結(jié)構(gòu)特性進(jìn)行了重新思考，利用復(fù)制網(wǎng)絡(luò)中分割介數(shù)