無標度網絡是指頂點的度服從泊松分布的拓撲圖。隨著現(xiàn)代信息化的大量普及,大規(guī)模數據圖越來越多地被應用到社交網絡等現(xiàn)實場景,而現(xiàn)實世界的大部分數據圖結構均滿足大規(guī)模無標度網絡的特性,因而可以通過對大規(guī)模無標度網絡圖數據的處理來驗證圖處理算法的性能。然而,現(xiàn)有大規(guī)模無標度網絡圖的構建方法存在效率低,擴展性差等問題。本文旨在研究大規(guī)模無標度網絡圖的高效生成方法,具體內容如下。首先,針對現(xiàn)有方法生成無標度網絡所存在的低效性問題,本文提出一種基于BA模型的大規(guī)模無標度網絡生成算法及相應的網絡圖數據存儲結構RWBT。設計了相應的遍歷策略以便提高算法效率,并對節(jié)點的刪除操作優(yōu)化處理,通過采用節(jié)點序號互換代替刪除桶的操作從而降低更新樹的頻次,解決了在內存中處理大規(guī)模數據圖時,重復遍歷節(jié)點導致的低效性的問題。其次,本文提出一種基于RWBT結構擴展的RWKT索引結構,并進一步改善數據圖的存儲結構以及相應的節(jié)點遍歷策略,通過對k叉樹結構的內部節(jié)點進行排序,減少了冗余比較次數,進一步提升了算法的處理效率。最后,通過對本文討論到的幾種算法的不同參數進行設置,通過實驗分別從結果質量、運行時間以及原子操作次數等多方面... 

【文章來源】：燕山大學河北省

【文章頁數】：59 頁

【學位級別】：碩士

【文章目錄】：
摘要
abstract
第1章 緒論
    1.1 研究背景
    1.2 研究現(xiàn)狀
    1.3 研究內容
    1.4 本文結構
第2章 基礎知識概述
    2.1 無標度網絡的相關概念
        2.1.1 小世界特性
        2.1.2 無標度特性
    2.2 現(xiàn)有圖生成模型
    2.3 創(chuàng)建無標度網絡的基本算法
        2.3.1 簡單輪盤算法
        2.3.2 隨機選擇算法
        2.3.3 基于桶結構的輪盤算法
    2.4 本章小結
第3章 基于RWBT的網絡生成算法
    3.1 問題分析
    3.2 基本思想
    3.3 基于RWBT結構的算法
        3.3.1 初始化無標度網絡
        3.3.2 取樣操作
        3.3.3 更新RWBT權值
        3.3.4 插入節(jié)點
        3.3.5 刪除節(jié)點
        3.3.6 RWBT算法
    3.4 對RWBT算法的分析
    3.5 算法優(yōu)化
    3.6 本章小結
第4章 基于RWKT的網絡生成算法
    4.1 問題分析
    4.2 RWKT算法基本思想
    4.3 RWKT算法描述
    4.4 算法分析
    4.5 基于RWMST結構的優(yōu)化算法
    4.6 本章小結
第5章 實驗結果與分析
    5.1 引言
    5.2 實驗環(huán)境
    5.3 數據集及評價標準
    5.4 性能比較與分析
        5.4.1 新增邊數的影響
        5.4.2 初始節(jié)點個數的影響
        5.4.3 數據規(guī)模的影響
        5.4.4 分支數對算法影響
        5.4.5 內存增長情況比較
    5.5 本章小結
結論
參考文獻
攻讀碩士學位期間承擔的科研任務與主要成果
致謝



本文編號：2978827