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

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

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

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



本文編號(hào)：3743345