做创意小视频的网站,想建网站怎么做,网站更换服务器对seo的影响,外链购买交易平台文章目录 前言一、graph-partition是什么#xff1f;二、具体分类三、graph-partition的意义参考链接 前言 最近在学习图论划分的方法#xff0c;碰巧搜索到了这个算是对我而言全新的一个体系#xff0c;在这里将逐步记载自己的学习资料和进度#xff0c;希望和大家一起探讨… 文章目录 前言一、graph-partition是什么二、具体分类三、graph-partition的意义参考链接 前言 最近在学习图论划分的方法碰巧搜索到了这个算是对我而言全新的一个体系在这里将逐步记载自己的学习资料和进度希望和大家一起探讨~ 一、graph-partition是什么 图分割是将一个大图均匀的分成一系列的子图去适应分布式应用每个子图存储在一台机器上子图之间可以并行化执行如果当前子图需要其他子图的信息就需要通讯开销而图分割的质量影响着每台机器存储代价和机器之间通讯代价。 粗略地按照分割的内存开销大小分类可以分为离线offline和流式streaming两类分割算法。offline是将整个图数据一次性载入内存中然后根据图的结构进行切分streaming是按批次读取图数据实时的将图的边或者结点分配到指定的子图中。对于大规模图数据来说单机的内存无法满足分割算法的需求这个时候流式分割显得尤为重要。
二、具体分类 按照对图数据的切分方式分类可以分为边分区/点分割vertex-partition or edge-cut和点分区/边分割edge-partition or vertex-cut有几个定义要注意下
edge-cut边分割 vertex-partition点分区vertex-cut点分割 edge-partition边分区 如下图所示点分区/边分割是将图的节点分配到各个子图中维持结点之间子图的完整性这个时候可能造成某些节点之间的边被切掉(edge-cut)同理边分区/点分割是将图的边分配到各个子图中每组分配的边构成子图这个时候造成某些结点的冗余vertex-cut。对于服从幂律分布power-law的图数据某些结点的边可能特别多如果执行点分割会造成大量边的缺失以及边的负载不均匀而边分割可以处理这类问题。
三、graph-partition的意义
将一个图划分为若干子图以便在分布式系统中运行图划分的优化目标包括两项负载均衡和最小割 (cut)二者都是为了提高在分布式系统中运算的性能。其中负载均衡是为了使分布式系统中的多台计算机有相近的任务负荷避免少数计算机负载过高。最小割则是为了减少计算机之间的通信代价。同时优化两个目标目前已知是NP困难问题。
参考链接 图分割Graph Partitioning技术总结 图流划分算法综述 【知识】如何区分图论中的点分割和边分割
