java - Spark GraphX 中完整图的分区策略

Question

我使用 Spark graphX 创建了一个图，其中每个顶点都直接连接到图的每个其他顶点，即完整图。如果有人可以针对此类情况提出良好的分区策略或任何实现自定义分区策略的想法，请提供。

我有 100 万个顶点和 5 亿条边。

任何与此相关的想法或建议将不胜感激。提前致谢。

Answer 1

如果您有完整的图，则不必关心复杂的分区算法。就采用GraphX已经实现的随机分区方法即可。

如果您有 n 个图顶点和 k 个分区，则任何 balanced (edge-cut) partitioning strategy将为每个分区分配大约 n/k 个顶点，这会导致每个分区有 (n-n/k) 个传出边到其他分区:每个顶点都连接到每个其他分区上的每个其他顶点。