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

Question

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

图表本身看起来像一个意大利面,想到随机互连的随机点集,一些偏向于较短的边缘.

问题是,一个分区图如何大？我发现可用的图形分区器可以处理仅适合内存的图形.我找不到任何流图分区算法的描述和实现.

或者,也许有一种替代分区图,以获得适合BFS的磁盘布局？

现在作为近似,我使用这样的事实:顶点具有附加到它们的空间坐标,并以Hilbert排序顺序将顶点放在磁盘上.这种方式在空间上靠近顶点落在同一页面上,但它们之间的边缘的存在与否完全被忽略.我可以做得更好吗？

作为替代方案,我可以使用顶点的希尔伯特排序顺序将图形拆分为多个,将子图划分,将它们缝合并接受接缝处的不良分区.

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

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

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

1. http://glaros.dtc.umn.edu/gkhome/views/metis
2. http://www.sandia.gov/~bahendr/chaco.html
3. http://staffweb.cms.gre.ac.uk/~c.walshaw/jostle/
4. http://www.cerfacs.fr/algor/Softs/MESHPART/

编辑:关于图表的样子以及BFS可以在任何地方开始的信息.编辑:分区子图的想法

Answer 1

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

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

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

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

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

如果您不需要相邻邻域进行太多聚类，则可以将已分组为邻域的顶点放在一边，并对剩余数据重复该过程，直到考虑到所有顶点。您将每个顶点标识符更改为（顶点，邻域），然后您就完成了：当沿着边缘时，您确切地知道要抓取哪个页面，并且大多数页面将在给定的构造下接近。

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

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

可能会成功。

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

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