發(fā)布時間：2023-02-15 14:08

　　隨著大規(guī)模網(wǎng)絡(luò)的不斷發(fā)展,涌現(xiàn)了許多相關(guān)的新興應(yīng)用,同時圖規(guī)模快速增長,圖數(shù)據(jù)也頻繁更新,對大規(guī)模網(wǎng)絡(luò)的處理提出了更高的要求。稠密子圖發(fā)現(xiàn)是一個基本的圖挖掘問題,已經(jīng)成為廣泛的數(shù)據(jù)分析任務(wù)中的原語,稠密子圖發(fā)現(xiàn)作為網(wǎng)絡(luò)處理中的熱點問題,其質(zhì)量和效率直接影響到復(fù)雜的網(wǎng)絡(luò)分析。本文對稠密子圖發(fā)現(xiàn)和k核的相關(guān)理論進行了研究,根據(jù)靜態(tài)圖及動態(tài)圖上稠密子圖的特點提出了基于k團核的稠密子圖發(fā)現(xiàn)方法,主要研究內(nèi)容包括:1.提出一種新的稠密子圖模型。k團核模型既可以捕獲頂點的團核數(shù)又能保證子圖一定的緊密性,k團核心分解算法獲得的團核數(shù)能夠有效地得到密度假想值的緊密上下限,從而減少二進制搜索的次數(shù)。2.提出基于k團核的靜態(tài)稠密子圖發(fā)現(xiàn)的一種精確算法和一種近似算法,實現(xiàn)大規(guī)模圖上的快速稠密子圖發(fā)現(xiàn)。精確算法利用k團核,提出三個優(yōu)化規(guī)則提高效率,并且利用核心分解算法,在特定的核上構(gòu)建流網(wǎng)絡(luò),通過使用二分查找法解決最大流問題找到稠密子圖。近似算法為了進一步提高效率,不利用核心分解算法,而是提出一種新的方法,直接計算最大的k團核,并證明最大k團核是稠密子圖發(fā)現(xiàn)問題的近似解。3.提出動態(tài)圖上的稠密子圖發(fā)現(xiàn)算法。在...

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

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

【文章目錄】：
摘要
Abstract
1 緒論
    1.1 研究背景與意義
    1.2 國內(nèi)外研究現(xiàn)狀
        1.2.1 稠密子圖發(fā)現(xiàn)研究現(xiàn)狀
        1.2.2 基于k核的稠密子圖發(fā)現(xiàn)研究現(xiàn)狀
    1.3 研究內(nèi)容
    1.4 論文結(jié)構(gòu)
2 相關(guān)理論基礎(chǔ)概述
    2.1 稠密子圖模型
        2.1.1 基于平均度的稠密子圖模型
        2.1.2 基于k核的稠密子圖模型
        2.1.3 基于團的稠密子圖模型
    2.2 稠密子圖發(fā)現(xiàn)算法
        2.2.1 稠密子圖發(fā)現(xiàn)的精確算法
        2.2.2 稠密子圖發(fā)現(xiàn)的近似算法
        2.2.3 稠密子圖發(fā)現(xiàn)的分段算法
        2.2.4 稠密子圖發(fā)現(xiàn)的邊權(quán)更新算法
    2.3 k核心分解方法
    2.4 h團(h-clique)
    2.5 本章小結(jié)
3 基于k團核的稠密子圖發(fā)現(xiàn)算法
    3.1 問題定義
        3.1.1 k團核定義
        3.1.2 靜態(tài)稠密子圖發(fā)現(xiàn)定義
        3.1.3 在k團核上構(gòu)建流網(wǎng)絡(luò)的過程
    3.2 基于k團核的精確算法
        3.2.1 k團核的密度上限和下限
        3.2.2 k團核心分解
        3.2.3 基于k團核的精確算法設(shè)計
    3.3 基于k團核的近似算法
    3.4 本章小結(jié)
4 動態(tài)的稠密子圖發(fā)現(xiàn)算法
    4.1 問題定義
        4.1.1 動態(tài)稠密子圖定義
        4.1.2 滑動時間窗口模型
        4.1.3 存儲高團度頂點的數(shù)據(jù)結(jié)構(gòu)
    4.2 動態(tài)稠密子圖發(fā)現(xiàn)算法
        4.2.1 添加頂點和添加邊算法
        4.2.2 刪除頂點和刪除邊算法
        4.2.3 完整的動態(tài)稠密子圖發(fā)現(xiàn)算法
    4.3 本章小結(jié)
5 實驗驗證與結(jié)果分析
    5.1 實驗概述
        5.1.1 實驗環(huán)境及評估指標
        5.1.2 實驗數(shù)據(jù)集
    5.2 實驗分析
        5.2.1 稠密子圖發(fā)現(xiàn)的精確算法結(jié)果分析
        5.2.2 稠密子圖發(fā)現(xiàn)的近似算法結(jié)果分析
        5.2.3 稠密子圖發(fā)現(xiàn)的精確與近似算法比較
        5.2.4 稠密子圖發(fā)現(xiàn)的動態(tài)算法結(jié)果分析
    5.3 案例研究
    5.4 本章小結(jié)
結(jié)論
參考文獻
致謝
作者簡歷及攻讀碩士學(xué)位期間的科研成果



本文編號：3743345