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

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

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

如果边缘不偏向于局部交互,那么将很难分离图。如果它们偏向于局部交互,那么我建议使用如下算法:

• 从整个数据集中选取一组随机顶点作为起点。
• 对于每个顶点,收集所有相邻顶点(对数据集进行一次扫描)。
• 对于每个相邻顶点集,收集相邻顶点集,并根据连接到相邻顶点的边数对其进行排序。如果页面中没有空间存储所有顶点,请保留连接最紧密的顶点。如果你有足够的空间来保存它们,你可能会想扔掉那些最不有用的(例如,如果保留在一页内的边的分数/需要存储率的顶点的分数“太低”——那里“太低”将取决于你的搜索真正需要的宽度,以及你是否可以进行任何修剪等等——那么不要将那些包含在邻居。
• 重复收集和排列邻居的过程,直到您的邻居已满(例如,填充适合您的页面大小)。然后检查随机选择的开始之间的重复。如果有少量顶点出现在两个顶点中,请将它们从一个或另一个顶点中删除,以破坏较少的边为准。如果有大量的顶点出现在这两个区域中,请保持最佳的邻域(邻域/断边中的顶点)比例,并丢弃另一个。

现在,您有一些本地社区,在广度优先搜索中几乎是本地最优的。如果广度优先搜索有效地删除了无用的分支,那么这就足够了。如果不是,你可能希望相邻的社区聚集。

如果不需要相邻的邻域进行过多的群集,可以将已分组到邻域中的顶点放在一边,然后对剩余数据重复此过程,直到所有顶点都被计算在内。您将每个顶点标识符更改为(顶点、邻域),然后就完成了:当沿着边移动时,您确切地知道要抓取哪个页面,并且在给定构造的情况下,它们中的大多数都将接近。

如果你确实需要邻近的社区,那么你就需要跟踪你不断增长的社区。重复前面的过程(随机选取,增加邻里),但现在根据邻里满足的边数对邻里进行排名。 和 它们离开邻居的边中有多少部分在现有的组中。你可能需要加权因子,但是

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

可能会成功。

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

同样,这取决于广度优先搜索是否删除分支。如果是这样,那么最便宜的做法就是最大限度地提高本地互联性。如果不是这样做的话,那就是尽量减少外部连接——在这种情况下,我建议只收集宽度优先设置到一定大小,然后保存这些设置(在设置的边缘进行复制——您不会受到硬盘空间的严重限制,是吗?).

你可能想看看 HDF5 .尽管H代表分层,但它可以存储图表,检查关键字“groups”下的文档,并且它是为非常大的数据集设计的。如果我理解正确,HDF5“文件”可以跨多个O/S“文件”分布。现在,HDF5只是一个数据结构,加上一组库,用于对数据结构进行低级和高级操作。在我的头脑中,我对流图分区算法一无所知,但我坚持这样的观点,即如果您获得了数据结构,正确的算法就更容易实现。

你对超大图形已经了解多少?它是否自然地划分成密集的子图,这些子图本身是稀疏连接的?图的拓扑排序是否比现有的空间排序更适合磁盘存储?

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

你想要一个好的bfs布局,但bfs通常应用于树。你的图表是否有一个唯一的根来启动所有的BFSE?如果不是,那么一个顶点的bfs布局对于另一个顶点的bfs将是次优的。

查看此日志:

“使用迭代地图缩减算法的广度优先图搜索”

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