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

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

【學位級別】：碩士

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



本文編號：4039058