图形分区算法与Neo4j图数据库

Question

我知道有一些着名的图形分区算法工具,如METIS,由karypis Lab实施(http://glaros.dtc.umn.edu/gkhome/metis/metis/overview)

但我想知道是否有任何方法来分割存储在Neo4j中的图形？或者我必须转储Neo4j的数据并手动转换节点和边缘格式以适应METIS输入格式？

Answer 1

关于新的和有趣的算法,这绝不是详尽的或现有的,但这些是我看的第一个地方:

特定算法:DiDiC(分布式扩散聚类) - 我在论文中使用过一次(分区图数据库)

迭代所有节点,然后为每个节点检索所有邻居,以便将一些"某个单元"传播给所有邻居
易于实施.
可以做出确定性的
迭代 - 因为它基于迭代(如Pregel中的Super Steps),您可以随时停止它.从理论上讲,离开它的时间越长,结果越好(尽管在某些情况下,在某些图形上它可能不稳定)
当我们实现这一点时,我们在具有~30GB RAM的机器上运行了100次迭代,最多可达400万个节点 - 完成时间不超过两天.

难以实施
本地算法 - 类似BFS的访问模式(随机漫游)
我阅读那篇论文已经有一段时间了,但我记得它建立在干净的抽象基础之上:
- EvoNibble(可插拔 - 决定要添加到当前群集的邻域数量
- EvoCut(多次调用EvoNibble以查找本地群集)
- EvoPartition(反复调用EvoCut来划分整个图形)
不确定

通用算法族:分层图聚类

从高层次:

笔记:

一般限制 - 几乎没有聚类算法的事情:

Answer 2

过去我曾独立使用 METIS 和 Neo4j，所以不知道有任何工具可以从 Neo4j 生成 METIS 文件。话虽这么说，编写这样一个工具应该是一项简单的任务，并且将是对社区的巨大贡献。

将 METIS 与 Neo4j 集成的另一种方法可能是通过 JNI 将 METIS 从 C++ 连接到 Neo4j。然而，这将涉及更多的事情，因为它必须处理事务、并发等问题。

在分割图这个更普遍的问题上，很可能通过合理的努力来实现一些更已知和简单的算法。