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