基于多层次划分的大规模动态图分割方法研究

发布时间：2025-01-04 03:47

　　图结构因其能较为准确地表示现实世界中实体间的关系,而被广泛应用于社交网络、生物信息网络、智能交通网等众多领域。随着信息技术的飞速发展,图数据规模日益增大,分布式并行计算成为解决大规模图数据处理的有效方法,而应用分布式并行计算的前提是快速有效地将图分割并分配到若干台计算机中,并尽可能保证负载平衡,避免因较大偏差造成存储空间的浪费。同时,现实应用中,图常随时间而动态变化,如何对大规模动态图进行有效地分割成为处理图数据的关键,因而成为当前图数据处理技术的研究热点之一。本文针对当前图分割问题进行了深入研究,发现在当前数据增长的规模与速度背景下,现实应用对图分割效率、分割结果优劣以及分割中的冗余存储等方面提出了更高的要求,现有的图分割方法已无法有效地解决大规模动态图的分割问题。针对上述问题,本文根据相邻两时刻,图的分区结构具有一定相似性的短暂平滑效应,将动态图分割问题分为两个阶段进行解决。首先针对初始图的静态结构,基于分层划分思想框架,针对初始分割阶段提出了一种利用部分节点交换的算法来进行划分,以尽可能保证负载均衡,即MPA-S方法。其次针对动态图结构,为避免重新分割造成的巨大开销,本文提出一种有...

【文章页数】：70 页

【学位级别】：硕士

【部分图文】：

图3-1多层次图分割方法的基本思想步骤在整个粗化阶段，原始图的所有节点以及边的权重都会在图规模缩小的过程中进行累计，最终形成最小规模的缩小图结构

节点间联系较少，则节点间的边的权值越小。一般来说，一个加权图可以由G(V,E,W)三元组来表示，其中V表示的是图G中所有节点的集合；E表示图G中所有节点间边的集合；W则代表图中边上的权重值的集合。如图3-1所示，原图在

本文编号：4022857