performance - 在磁盘/流图分区算法上存储非常大的图？

Question

假设我有一个非常大的无向、未加权图（从数亿个顶点开始，每个顶点约 10 条边），非分布式且仅由单线程处理，并且我想对其进行广度优先搜索。我希望它们受 I/O 限制，因此我需要一个适合 BFS 的磁盘页面布局，磁盘空间不是问题。搜索可以以相等的概率从每个顶点开始。直观地说，这意味着最小化不同磁盘页面上顶点之间的边数，这是一个图分区问题。

图本身看起来像意大利面条，想想随机互连的随机点集，对较短的边有一些偏见。

问题是，一个分区图怎么这么大？我发现可用的图形分区器仅适用于内存中的图形。我找不到任何流图分区算法的描述或实现。

或者，也许有一种替代分区图的方法来获得适用于 BFS 的磁盘布局？

现在作为一个近似值，我使用顶点附有空间坐标的事实，并将顶点以希尔伯特排序顺序放在磁盘上。这种方式空间上接近的顶点落在同一页面上，但它们之间是否存在边缘被完全忽略。我能做得更好吗？

作为替代方案，我可以使用 Hilbert 顶点排序顺序将图拆分为多个部分，对子图进行分区，将它们缝合回去并接受接缝上的不良分区。

我已经研究过的一些事情：

如何存储具有数十亿个节点和顶点的大型有向未加权图
http://neo4j.org/ - 我发现关于它如何在磁盘上进行图形布局的零信息

分区实现（除非我弄错了，它们都需要将图形放入内存）：

编辑：关于图表的外观以及 BFS 可以在任何地方开始的信息。编辑：关于划分子图的想法

score 3 · Accepted Answer

没有算法真正需要“适应内存”——您总是可以根据需要将内容分页进出。但是您确实希望避免使计算花费不合理的时间——在一般情况下，全局图分区是一个 NP 完全问题，对于大多数甚至不适合内存的问题来说，这是“不合理的长”。

幸运的是，您希望进行广度优先搜索，这意味着您需要一种易于计算的广度优先格式。我不知道有什么算法可以做到这一点，但是如果您愿意允许一些额外的磁盘空间，您可以构建自己的广度优先布局。

如果边缘不偏向于局部交互，那么解开图形将很困难。如果他们偏向于局部交互，那么我建议使用如下算法：

从整个数据集中选择一组随机顶点作为起点。
对于每个顶点，收集所有相邻顶点（对数据集进行一次扫描）。
对于每组相邻顶点，收集一组邻居的邻居，并根据连接到它们的边数对它们进行排名。如果页面中没有空间来存储它们，请保留连接最多的顶点。如果您确实有空间将它们全部保存，您可能希望丢弃最不有用的那些（例如，如果保留在页面内的边缘部分/需要存储比率的顶点部分下降“太低” - 其中“太低”将取决于您的搜索真正需要多少广度，以及您是否可以进行任何修剪等等 - 然后不要包括附近的那些。
重复收集邻居并对其进行排名的过程，直到您的邻居已满（例如，填充一些适合您的页面大小）。然后检查随机选择的开始之间的重复。如果您有少量顶点出现在两者中，请将它们从一个或另一个中删除，以中断较少的边为准。如果您在两者中都出现了大量顶点，请保持具有最佳（邻域中的顶点/断边）比率的邻域并将另一个丢弃。

现在，您有一些近似局部最优的局部邻域，因为广度优先搜索往往落在内部。如果您的广度优先搜索非常有效地修剪掉了非生产性分支，那么这可能就足够了。如果没有，您可能希望相邻的社区聚集在一起。

如果您不需要相邻的邻域进行太多聚类，则将已分组到邻域中的顶点放在一边，并在剩余数据上重复该过程，直到所有顶点都被计算在内。您将每个顶点标识符更改为 (vertex,neighborhood)，然后就完成了：当跟随边缘时，您确切地知道要抓取哪个页面，并且它们中的大多数将在给定结构的情况下接近。

如果您确实需要相邻的社区，那么您需要跟踪您不断增长的社区。您重复前面的过程（随机挑选，增加邻域），但现在根据邻域内满足的边数以及离开邻域的边在现有组中的比例对邻域进行排名。您可能需要加权因子，但类似

score = (# edges within) - (# neighborhoods outside) - (# neighborhoodless edges outside)

可能会成功。

现在，这不是全局最优的，甚至不是局部最优的，但是这个或非常类似的东西应该提供一个很好的局部连接结构，并且应该让你产生一组具有相对较高互连性的邻域。

同样，这取决于您的广度优先搜索是否修剪分支。如果确实如此，那么廉价的做法是最大限度地提高本地互连性。如果它不应该做的就是最小化外部连接——在这种情况下，我建议只收集一定大小的广度优先集并保存它们（在集的边缘有重复——你'没有受到硬盘空间的严重限制，是吗？）。

score 2 · Accepted Answer

您可能想查看HDF5。尽管 H 代表 Hierarchical，但它可以存储图形，查看关键字“组”下的文档，它是为非常大的数据集设计的。如果我理解正确，HDF5“文件”可以分布在多个 o/s“文件”中。现在，HDF5 只是一种数据结构，加上一组用于对数据结构进行低级和高级操作的库。在我的脑海中，我对流式图形分区算法一无所知，但我坚持认为，如果你得到正确的数据结构，算法就会更容易实现。

您对巨型图了解多少？它是否自然地划分为密集的子图，这些子图本身是稀疏连接的？图的拓扑排序会比现有的空间排序更适合存储在磁盘上吗？

对这些问题没有清晰的答案，也许您只需要咬紧牙关并多次阅读图表来构建分区，在这种情况下，您只需要可以管理的最快 I/O，并且节点上分区的复杂布局很好但没有那么重要。如果您可以将图划分为子图，这些子图本身与其他子图有单边，您也许可以使问题更容易处理。

您想要一个适合 BFS 的布局，但 BFS 通常应用于树。你的图是否有一个唯一的根来启动所有 BFS？如果不是，那么来自一个顶点的 BFS 布局对于来自另一个顶点的 BFS 来说是次优的。

performance - 在磁盘/流图分区算法上存储非常大的图？

2 回答 2

Related

Reference