设计图分割算法的总结

1 初衷

? ? ? ? 在设计并行SNN的时候，涉及到将SNN作为图分割到不同的进程中进行模拟，由于这一块涉及到图分割的相关知识，因此，在这里开一个板块，用来设计和实现一些图分割的算法，并进行性能的测试。

2 简介

????????图划分（Graph Partitioning）是图论中的一个重要问题，旨在将一个图分割成多个部分或子图，使得划分后的子图之间的连接尽可能稀疏，而划分内部的连接尽可能稠密，这样能够实现分布式的应用。

????????图划分问题可以形式化为以下形式：给定一个图 G=(V,E)，其中 V 是顶点集合，E 是边集合，以及一个指定的划分数 k，要求将顶点集合 V 划分为 k 个部分 V1, V2, ..., Vk，使得划分后的部分满足以下条件：

1. ?负载均衡load balancing（减少进程之间的同步代价）
2. ?最小化切边或点minimum cuts（减少通讯代价）

????????同时优化这两个目标是平衡图分割（balanced graph partitioning）问题，这是一个NP难的问题。

3 算法总结

? ? ? ? 3.1?Random Hash

?????????随机哈希点分割的核心思想是通过哈希函数将顶点映射到不同的部分，并根据邻居顶点的分布信息来更新顶点的部分标识。这样可以实现一种随机性的划分，从而在一定程度上平衡了顶点在不同部分的分布。比如使用哈希函数f(v)=hash(v)mod(k)，给每个结点分配不同的id，然后通过分割分数k进行取模，最后分配到指定的子图中。

? ? ? ? 3.2 贪心算法

????????心算法是最简单和常用的图划分方法之一。它是基于局部最优决策来逐步构建整体的划分结果。它通常通过贪心策略选择当前最优的操作，以期望达到较好的划分质量。常见的贪婪算法包括 Kernighan-Lin 算法和 Fiduccia-Mattheyses 算法。

? ? ? ? 3.3? 谱图划分

????????谱图划分基于图的特征值和特征向量进行划分。它通过计算图的拉普拉斯矩阵的特征向量，将图的顶点划分为两个或多个部分。谱图划分方法包括比率割、最小割、最大化图划分等。

? ? ? ? 3.4 多级划分（metis）

????????多级划分核心思想对于给定原图结构持续的稀疏化融合结点和边来降低原图的大小，然后达到一定程度对于缩减后的图结构进行分割，最后将分割后的小图还原成原始的图结构保证每份子图的均衡性。经典的多极化分是metis

? ? ? ? 3.5 超图划分

? ? ? ? 将普通的图构造为超图，来进行划分，以后慢慢聊

4 参考博客

图分割Graph Partitioning技术总结_fennel图流划分算法-CSDN博客?