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

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

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

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

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