兰州网站怎么建设,汕头模板开发建站,遵义祥云平台网站建设,html网页设计模板免费下载文章目录 前言一、Metis原理二、Metis优点三、Metis软件包安装流程参考链接 前言 今天来学一下Metis算法#xff0c;经过搜索发现这个算法还是蛮多人在讲解的#xff0c;我也在这里浅浅记录一下~ 一、Metis原理 METIS是一种层次化的分割算法#xff08;multi-level partitio… 文章目录 前言一、Metis原理二、Metis优点三、Metis软件包安装流程参考链接 前言 今天来学一下Metis算法经过搜索发现这个算法还是蛮多人在讲解的我也在这里浅浅记录一下~ 一、Metis原理 METIS是一种层次化的分割算法multi-level partitioning核心思想对于给定原图结构持续的降低原图的大小然后达到一定程度对于缩减后的图结构进行分割最后将分割后的小图还原成原始的图结构保证每份子图的均衡性。 整个划分过程分成coarsening, initial partitioning 和 uncoarsening (refinement) 三个部分。coarsening将图的大小逐渐缩小G1-G2-G3-G4在G4阶段执行K路划分然后在uncoarsening阶段将图中的原始节点映射到G4划分的cluster中。
二、Metis优点
具有高质量的划分结果据称比通常的谱聚类spectral clustering要精确10%-50%执行效率非常高比常见的划分算方法快1-2个数量级百万级顶点的图几秒钟之内就可以切分为256个类METIS具有很低的注入元fill-in 从而降低了存储负载和计算量。
三、Metis软件包安装流程 METIS是由Karypis Lab开发的一个具有强大功能的图切分软件包是的METIS已经有软件包了用于划分大型不规则图、划分大网格以及计算稀疏矩阵的降填充序本文只介绍图划分部分。METIS基于George Karypis等人提出的多级图划分范式实现它提供了一组独立的命令行程序和应用程序接口API可通过C/C或ForTran程序调用。具体的METIS软件包的下载、安装和用于图划分的使用过程看这个链接实测可以成功 使用METIS软件包进行图划分 参考链接 METIS-一种图切分的软件包简介 图分割Graph Partitioning技术总结 使用METIS软件包进行图划分
