大數(shù)據(jù)時代,很多問題的底層數(shù)據(jù)模型是頂點或邊的數(shù)據(jù)規(guī)模達到千萬甚至上億級別,且頂點和邊實時變化的大規(guī)模動態(tài)圖,例如,社交網(wǎng)絡圖、Web網(wǎng)頁圖等等。為了高效地進行大規(guī)模動態(tài)圖的分布式/并行計算,必須對大規(guī)模動態(tài)圖進行均衡合理劃分,高效的大規(guī)模動態(tài)圖劃分是高效的大規(guī)模動態(tài)圖分布式/并行計算的基礎和前提。一般而言,高效的大規(guī)模動態(tài)圖劃分算法需要滿足以下3個要求:1)劃分的各分區(qū)間的通信代價盡可能小;2)各分區(qū)內的頂點/邊的數(shù)量應盡可能均衡;3)大規(guī)模動態(tài)圖劃分算法是大規(guī)模動態(tài)圖分布式/并行計算的預處理,所以大規(guī)模動態(tài)圖劃分算法應具有較好的時間性能。由于大規(guī)模動態(tài)圖劃分問題的復雜性,它是一個亟待解決的NP難問題。近年來,許多學者開始關注并研究大規(guī)模動態(tài)圖劃分問題,也開始涌現(xiàn)了一些創(chuàng)新性的大規(guī)模動態(tài)圖劃分算法,但是現(xiàn)有算法普遍存在以下缺陷:1)算法時間性能有待于提高;2)算法不能實時應對大規(guī)模動態(tài)圖中邊/頂點的變化;3)現(xiàn)有的算法僅考慮了各個分區(qū)上頂點/邊的均衡問題,沒有考慮動態(tài)圖中各分區(qū)的活躍頂點/邊在圖計算中的均衡問題;4)算法需要較大的輔助空間。因此,創(chuàng)新研究與實現(xiàn)高效的大規(guī)模動態(tài)圖劃分算... 

【文章來源】：西安電子科技大學陜西省 211工程院校 教育部直屬院校

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

【學位級別】：碩士

【文章目錄】：
摘要
ABSTRACT
符號對照表
縮略語對照表
第一章 緒論
    1.1 選題背景與研究意義
    1.2 國內外研究現(xiàn)狀
    1.3 論文的主要工作與組織結構
        1.3.1 論文的主要工作與創(chuàng)新
        1.3.2 論文組織結構
第二章 基礎理論與相關工作綜述
    2.1 基礎理論
        2.1.1 相關基本概念及定義
        2.1.2 大規(guī)模動態(tài)圖劃分的問題模型
        2.1.3 頂點局部中心性
    2.2 大規(guī)模動態(tài)圖的特征
        2.2.1 大規(guī)模動態(tài)圖的拓撲結構演變特征
        2.2.2 大規(guī)模動態(tài)圖的拓撲結構特征
    2.3 大規(guī)模圖處理框架
        2.3.1 GraphX的數(shù)據(jù)存儲模型
        2.3.2 GraphX的圖計算模型
    2.4 大規(guī)模動態(tài)圖劃分算法綜述
    2.5 本章小結
第三章 CBH-DGP:高效大規(guī)模動態(tài)圖劃分算法設計
    3.1 算法設計動機
    3.2 算法思想與算法框架
    3.3 CBH-DGP算法的主要設計策略
        3.3.1 局域中心性度量策略
        3.3.2 實時局域中心性度量策略
        3.3.3 實時近似局域中心性度量策略
        3.3.4 基于局域中心性的邊散列策略
    3.4 CBH-DGP:大規(guī)模動態(tài)圖劃分算法設計
        3.4.1 CBH-GP:初始圖劃分算法設計
        3.4.2 UCBH-Ins:插入圖劃分算法設計
        3.4.3 CBH-DGP算法設計優(yōu)化策略
        3.4.4 算法分析
    3.5 時空復雜度分析
    3.6 本章小結
第四章 基于DynGraphX的分布式劃分算法實現(xiàn)
    4.1 DynGraphX總體設計
    4.2 DynGraphX設計與實現(xiàn)
        4.2.1 GraphX基礎
        4.2.2 DynGraphX的分配模塊
        4.2.3 DynGraphX的圖更新模塊
        4.2.4 DynGraphX的圖計算模塊
    4.3 基于DynGraphX的分布式圖劃分算法的實現(xiàn)
        4.3.1 CBH-DGP:大規(guī)模動態(tài)圖劃分算法的實現(xiàn)
        4.3.2 CBH-GP:初始圖劃分算法實現(xiàn)
        4.3.3 UCBH-Ins:插入圖劃分算法實現(xiàn)
    4.4 時空復雜度分析
    4.5 本章小結
第五章 實驗與分析
    5.1 實驗環(huán)境與數(shù)據(jù)集
        5.1.1 實驗平臺與配置介紹
        5.1.2 實驗數(shù)據(jù)集介紹
    5.2 實驗分析
        5.2.1 評估準則
        5.2.2 初始圖劃分算法性能分析
        5.2.3 插入圖劃分算法性能分析
        5.2.4 DynGraphX性能分析
    5.3 本章小結
第六章 總結與展望
    6.1 論文工作總結
    6.2 后續(xù)工作展望
參考文獻
致謝
作者簡介


【參考文獻】：
期刊論文
[1]社會網(wǎng)絡節(jié)點影響力分析研究[J]. 韓忠明,陳炎,劉雯,原碧鴻,李夢琪,段大高.  軟件學報. 2017(01)



本文編號：2951727