發(fā)布時間：2025-04-01 06:25

　　圖數(shù)據(jù)的分析一直都是研究者們所關(guān)注的熱點之一。圖分析在很多領(lǐng)域中扮演重要角色,包括中介中心性、社區(qū)發(fā)現(xiàn)等。目前對圖數(shù)據(jù)的分析主要通過兩個途徑,一是在原始圖數(shù)據(jù)上進(jìn)行,二是在原始圖數(shù)據(jù)的度量骨干上進(jìn)行。利用度量骨干代替原始圖的分析,使得分析工作的效率大大提升,本文主要研究計算圖數(shù)據(jù)度量骨干的問題,具體內(nèi)容如下。首先,現(xiàn)有算法OSME在刪除圖數(shù)據(jù)中1階半度量邊、查找圖數(shù)據(jù)中的三角形時存在同一個三角形被重復(fù)查找的問題,導(dǎo)致算法效率低。對此,提出一種新的算法BSME來查找三角形�；�本思想是當(dāng)遍歷到一個頂點u時,先獲取大于u編號的鄰接點列表,然后依次求出鄰接列表中每個元素和頂點u的交集,由交集元素、鄰接列表元素、頂點u即構(gòu)成一個三角形。BSME算法避免了同一個三角形被重復(fù)查找的問題,提高了現(xiàn)有算法的效率。其次,現(xiàn)有算法CURE在確定一條邊(u,v)是否是度量邊時,如果頂點u的度變大,則以頂點u為起點需要被確定的邊數(shù)往往也會變大。這時需要從頂點u出發(fā)進(jìn)行多次BFS搜索來為每條邊找可替代的間接路徑,導(dǎo)致算法效率低。對此,提出一種新的算法TURE來提高現(xiàn)有算法的效率�；�本思想是先將頂點按照其度從大到小進(jìn)...

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

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

【文章目錄】：
摘要
Abstract
第1章 緒論
    1.1 研究背景
    1.2 研究現(xiàn)狀
    1.3 研究內(nèi)容
    1.4 本文結(jié)構(gòu)
第2章 基礎(chǔ)知識概述
    2.1 基礎(chǔ)概述
    2.2 數(shù)據(jù)模型
    2.3 基本概念
    2.4 真實半度量
    2.5 實際應(yīng)用
        2.5.1 圖形數(shù)據(jù)庫
        2.5.2 批處理系統(tǒng)
        2.5.3 圖形的壓縮
    2.6 算法分類
    2.7 本章小結(jié)
第3章 基于頂點大鄰居的BSME算法
    3.1 OSME算法問題分析
    3.2 BSME算法
        3.2.1 BSME算法思想
        3.2.2 BSME算法描述
        3.2.3 BSME算法分析
    3.3 本章小結(jié)
第4章 基于top-k索引的TURE算法
    4.1 CURE算法問題分析
    4.2 TURE算法
        4.2.1 TURE算法思想
        4.2.2 TURE算法描述
        4.2.3 TURE算法分析
    4.3 本章小結(jié)
第5章 實驗及結(jié)果分析
    5.1 引言
    5.2 實驗環(huán)境和數(shù)據(jù)集
    5.3 性能比較與分析
        5.3.1 刪除1階半度量邊的時間效率
        5.3.2 不同k值下的TURE算法
    5.4 本章小結(jié)
結(jié)論
參考文獻(xiàn)
致謝



本文編號：4039058