發(fā)布時間：2022-07-08 11:41

　　隨著計算機與互聯(lián)網(wǎng)技術(shù)的不斷發(fā)展,網(wǎng)絡(luò)已成為人們?nèi)粘Ｉ畈豢苫蛉钡囊徊糠�。人們現(xiàn)實生活中的大部分?jǐn)?shù)據(jù)都可用網(wǎng)絡(luò)或圖（Graph）來表示,如通信網(wǎng)絡(luò),交通網(wǎng)絡(luò)、社交網(wǎng)絡(luò)、生物網(wǎng)絡(luò)等。社團結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)的一個重要結(jié)構(gòu)特征,研究這些社團結(jié)構(gòu)有利于更好地理解復(fù)雜網(wǎng)絡(luò)的功能與特性。此外,復(fù)雜網(wǎng)絡(luò)在社團結(jié)構(gòu)層面通常會顯示出一些單個節(jié)點或整個網(wǎng)絡(luò)層面所不具備的特性。為了更深入地研究復(fù)雜網(wǎng)絡(luò),捕獲更多有意義的潛在信息,需要使用社團檢測技術(shù)。然而隨著節(jié)點數(shù)量不斷增加,網(wǎng)絡(luò)結(jié)構(gòu)不斷復(fù)雜,傳統(tǒng)的社團檢測算法已不再適用于大規(guī)模復(fù)雜網(wǎng)絡(luò)。而分布式并行處理技術(shù)為處理大規(guī)模復(fù)雜網(wǎng)絡(luò)提供了有效手段。因此,研究復(fù)雜網(wǎng)絡(luò)的社團檢測并行算法對深入理解網(wǎng)絡(luò)結(jié)構(gòu)與性質(zhì)具有重大理論意義與實際價值。基于上述原因,本文提出了一種針對大規(guī)模復(fù)雜網(wǎng)絡(luò)的并行化社團檢測算法——Parallel LPA-Attractor算法（簡稱PLA）。在設(shè)計這種算法的過程中涉及圖表示、分割、存儲、計算以及結(jié)果融合問題,其中最重要的是單個計算單元的社團檢測算法。在對現(xiàn)有的社團檢測算法進行多方面的權(quán)衡比較后,本文采用Attractor算法作為核心計算算法。... 

【文章頁數(shù)】：85 頁

【學(xué)位級別】：碩士

【文章目錄】：
摘要
ABSTRACT
符號對照表
縮略語對照表
第一章 緒論
    1.1 研究背景
    1.2 研究意義
    1.3 國內(nèi)外研究現(xiàn)狀
    1.4 本文的工作與安排
        1.4.1 研究內(nèi)容
        1.4.2 本文組織結(jié)構(gòu)
第二章 復(fù)雜網(wǎng)絡(luò)社團檢測的相關(guān)基礎(chǔ)
    2.1 網(wǎng)絡(luò)與社團的相關(guān)基礎(chǔ)
        2.1.1 復(fù)雜網(wǎng)絡(luò)定義
        2.1.2 復(fù)雜網(wǎng)絡(luò)的表示方法
        2.1.3 其他基本概念
        2.1.4 社團的定義
    2.2 社團檢測評價指標(biāo)
        2.2.1 模塊度
        2.2.2 歸一化互信息
        2.2.3 F1分?jǐn)?shù)
    2.3 復(fù)雜網(wǎng)絡(luò)中的經(jīng)典社團檢測算法
        2.3.1 標(biāo)簽傳播算法
        2.3.2 其他常見算法
    2.4 本章小結(jié)
第三章 基于動態(tài)距離的Attractor算法及其改進算法
    3.1 基于動態(tài)距離的Attractor算法
        3.1.1 Attractor算法的基本原理
        3.1.2 Attractor算法的相關(guān)定義與計算模式
        3.1.3 Attractor算法時間復(fù)雜度及算法流程
        3.1.4 Attractor算法存在的問題
    3.2 Attractor的改進算法——LA算法
        3.2.1 LA算法的基本原理
        3.2.2 LA算法的三種計算模式
        3.2.3 LA算法的流程
        3.2.4 LA算法的時間復(fù)雜度
    3.3 LPA的改進算法——AMLPA算法
        3.3.1 AMLPA算法的基本原理
        3.3.2 AMLPA的算法流程
        3.3.3 AMLPA算法的時間復(fù)雜度
    3.4 本章小結(jié)
第四章 LA的并行化算法——PLA算法
    4.1 一種圖的表示方式——耦合表
    4.2 大規(guī)模圖的分布式處理
        4.2.1 METIS算法
        4.2.2 分布式存儲方式
        4.2.3 改進的分布式存儲方式
        4.2.4 分布式結(jié)果融合方法
    4.3 PLA算法
        4.3.1 PLA算法的原理
        4.3.2 PLA算法的流程
        4.3.3 PLA算法的時間復(fù)雜度分析
    4.4 本章小結(jié)
第五章 實驗與分析
    5.1 實驗設(shè)備
    5.2 實驗數(shù)據(jù)集
    5.3 PLA核心算法社團分布對比實驗
    5.4 PLA算法對輸入?yún)?shù)的敏感性測試
    5.5 PLA算法的NMI測試
    5.6 PLA算法時間性能
    5.7 本章小結(jié)
第六章 總結(jié)與展望
    6.1 工作總結(jié)
    6.2 未來展望
參考文獻
致謝
作者簡介



本文編號：3656963