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

Question

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

图本身看起来像意大利面，想想随机互连的随机点集，偏向于较短的边。

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

或者，也许有一种替代分区图的方法来获得与 BFS 配合良好的磁盘布局？

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

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

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

How to store a large directed unweighted graph with billions of nodes and vertices

http://neo4j.org/ - 我发现关于它如何在磁盘上进行图形布局的零信息

分区实现(除非我弄错了，所有这些都需要将图形放入内存中):

http://glaros.dtc.umn.edu/gkhome/views/metis

http://www.sandia.gov/~bahendr/chaco.html

http://staffweb.cms.gre.ac.uk/~c.walshaw/jostle/

http://www.cerfacs.fr/algor/Softs/MESHPART/

编辑:有关图表的外观以及 BFS 可以在任何地方启动的信息。
编辑:关于分区子图的想法

Answer 1

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

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

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

从整个数据集中选择一组随机顶点作为起点。

对于每个顶点，收集所有相邻顶点(对数据集进行一次扫描)。

对于每组相邻顶点，收集一组邻居的邻居，并根据连接到它们的边的数量对它们进行排名。如果页面中没有空间来存储它们，请保留连接最多的顶点。如果您确实有空间来保存它们，您可能希望扔掉最不实用的那些(例如，如果保留在页面内的边缘部分/需要存储比率的顶点部分下降“太低”——其中“太低”将取决于您的搜索真正需要多少广度，以及您是否可以进行任何修剪等等 - 然后不要包括附近的那些。

重复收集邻居并对其进行排名的过程，直到您的邻居已满(例如，填充适合您的某些页面大小)。然后检查随机选择的开始之间的重复。如果两个顶点中都出现少量顶点，请将它们从一个或另一个中删除，以破坏边较少的那个为准。如果您有大量的顶点出现在两者中，请保留具有最佳(邻域中的顶点/断边的顶点)比率的邻域并将另一个丢弃。

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

如果您不需要相邻的邻域进行过多的聚类，则可以将已分组到邻域中的顶点放在一边，并对剩余数据重复该过程，直到所有顶点都被考虑在内。您将每个顶点标识符更改为 (vertex,neighborhood)，然后就大功告成了:当沿着边缘移动时，您确切地知道要抓取哪个页面，并且根据构造，它们中的大多数将被关闭。

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

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

可能会成功。

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

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