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

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

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

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



本文編號(hào)：4039058