图中度量骨干求解方法研究

发布时间：2025-04-01 06:25

　　图数据的分析一直都是研究者们所关注的热点之一。图分析在很多领域中扮演重要角色,包括中介中心性、社区发现等。目前对图数据的分析主要通过两个途径,一是在原始图数据上进行,二是在原始图数据的度量骨干上进行。利用度量骨干代替原始图的分析,使得分析工作的效率大大提升,本文主要研究计算图数据度量骨干的问题,具体内容如下。首先,现有算法OSME在删除图数据中1阶半度量边、查找图数据中的三角形时存在同一个三角形被重复查找的问题,导致算法效率低。对此,提出一种新的算法BSME来查找三角形。基本思想是当遍历到一个顶点u时,先获取大于u编号的邻接点列表,然后依次求出邻接列表中每个元素和顶点u的交集,由交集元素、邻接列表元素、顶点u即构成一个三角形。BSME算法避免了同一个三角形被重复查找的问题,提高了现有算法的效率。其次,现有算法CURE在确定一条边(u,v)是否是度量边时,如果顶点u的度变大,则以顶点u为起点需要被确定的边数往往也会变大。这时需要从顶点u出发进行多次BFS搜索来为每条边找可替代的间接路径,导致算法效率低。对此,提出一种新的算法TURE来提高现有算法的效率。基本思想是先将顶点按照其度从大到小进...

【文章页数】：58 页

【学位级别】：硕士

【文章目录】：
摘要
Abstract
第1章 绪论
    1.1 研究背景
    1.2 研究现状
    1.3 研究内容
    1.4 本文结构
第2章 基础知识概述
    2.1 基础概述
    2.2 数据模型
    2.3 基本概念
    2.4 真实半度量
    2.5 实际应用
        2.5.1 图形数据库
        2.5.2 批处理系统
        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 实验环境和数据集
    5.3 性能比较与分析
        5.3.1 删除1阶半度量边的时间效率
        5.3.2 不同k值下的TURE算法
    5.4 本章小结
结论
参考文献
致谢



本文编号：4039058