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

Question

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

该图本身看起来像一个意大利面条，想到任意随机连接的点的集合，有一些偏向于较短的边缘。

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

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

现在作为一个近似我使用的事实是，顶点有空间坐标附加到他们，并把顶点在希尔伯特排列顺序在磁盘上。这样，空间上靠近的顶点落在同一页面上，但它们之间边缘的存在或不存在完全被忽略。我可以做得更好吗？

作为一种替代方法，我可以使用希尔伯特排序顺序将图分割为多个顶点，划分子图，将它们缝合并接受缝隙上的不良分区。

有些事情，我都看着已经：

1. How to store a large directed unweighted graph with billions of nodes and vertices
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) 

可能会做到这一点。

现在，这是不全球，甚至局部最优，但这什么非常喜欢它应该给一个很好的本地连接的结构，应该让你产生一种覆盖集具有相对较高的互联互通的街区。

同样，这取决于您的广度优先搜索李子是否分支。如果是这样，便宜的事情是最大限度地提高本地互联性。如果无法做到的是最大限度地减少外部连接 - 在这种情况下，我建议只收集宽度优先的设置，并将其保存到一定的大小，并保存这些设置（在设置的边缘重复）硬盘空间不会受到严重限制，是吗？）。

Answer 2

你可能想看看HDF5。尽管H代表Hierarchical，但它可以存储图形，检查关键字'Groups'下的文档，并且它是为非常大的数据集设计的。如果我理解正确，HDF5'文件'可以分布在多个o/s'文件'中。现在，HDF5只是一种数据结构，还有一套用于数据结构低级和高级操作的库。关于流式图分区算法我一点都不知道，但我坚持这样一个观点，即如果您获得了数据结构，那么正确的算法会变得更容易实现。

你对超级图表有什么了解？它是否自然地划分为本身连接稀疏的稠密子图？图的拓扑排序是否会比现有的空间排序更适合在磁盘上存储？

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

你想好换BFS布局，但BFS通常适用于树木。您的图表是否具有启动所有BFS的唯一根目录？如果不是，那么来自一个顶点的BFS布局对于来自另一个顶点的BFS将是次优的。

Answer 3

检查这篇博客文章： “使用广度优先的图搜索迭代的map-reduce算法”

http://www.johnandcailin.com/blog/cailin/breadth-first-graph-search-using-iterative-map-reduce-algorithm