使用Neo4j图形数据库的图形分区算法

Question

我知道有一些著名的图分区算法工具，比如由Karypis实验室开发的METIS (http://glaros.dtc.umn.edu/gkhome/metis/metis/overview)

但是我想知道是否有办法对存储在Neo4j中的图进行分区？ 还是说我必须要导出Neo4j的数据并手动转换节点和边的格式以适应METIS的输入格式？

- Arvin

Answer 1

关于新颖且有趣的算法，这并不是穷尽所有，也不是最先进的，但这些是我首先会查看的地方：

具体算法：DiDiC（分布式扩散聚类） - 我在论文中使用过它（分区图数据库）

• 您可以遍历所有节点，然后对于每个节点检索所有邻居，以便将“某个单位”传播到所有邻居
• 易于实现。
• 可以使它确定性。
• 迭代-因为它基于迭代（如Pregel中的超级步骤），您可以随时停止它。理论上，您离开它的时间越长，结果就越好（尽管在某些情况下，在某些图形形状上可能不稳定）
• 当我们实施此操作时，在具有〜30GB RAM的机器上运行了100次迭代，达到了〜4百万个节点-完成所需的时间不超过两天。

具体算法：EvoCut "使用演化集合在本地找到稀疏切割" - 来自微软的本地概率算法 - 与这些论文有关

• 难以实现
• 本地算法 - BFS-类似的访问模式（随机游走）
• 我读过那篇论文已经有一段时间了，但我记得它是建立在干净的抽象之上的：
  • EvoNibble（可插拔 - 决定向当前聚类添加多少邻域）
  • EvoCut（多次调用EvoNibble来查找本地聚类）
  • EvoPartition（重复调用EvoCut来对整个图进行分区）
• 不确定性的

算法家族: 分层图聚类

从高层次来看：

• 通过将节点折叠成聚合节点来粗化图形
  • 粗化策略可选择
• 在粗化/较小的图中查找聚类
  • 聚类策略可选择
• 逐步解除图形的粗化，每个步骤都会改善聚类
  • 细化策略可选择

注：

• 如果图形变化缓慢（或结果不需要实时更新），可能可以粗略一次（或不经常粗略），然后使用粗略的图形-以节省计算量
• 我不知道具体推荐哪种算法

一般限制 - 很少有聚类算法能够做到的事情：

• 未确认节点类型-即所有节点被视为相同
• 未确认关系类型-即所有关系被视为相同
• 未确认关系方向-即将关系视为无向关系

- Alex Averbuch

---

谢谢你的帮助！ 目前我不打算自己实现算法，但这是一个我可以跟进的好资源。 谢谢。 - Arvin

Answer 2

我过去曾独立使用METIS和Neo4j工具，但我并不知道如何从Neo4j生成一个METIS文件。话虽如此，编写这样的工具应该是一项简单的任务，并且将是社区做出的伟大贡献。

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

关于图分区的更普遍的问题，实现一些已知的较简单算法是完全可能的，只需要付出合理的努力即可。

- boggle

---

如果您不想自己实现算法，可以将数据导出到分区库（例如METIS），然后再导入到Neo4j中。这样做可以让您的工作更加高效。 - Alex Averbuch

如果你想要实现一个算法，我建议先将其导出到像http://giraph.apache.org、http://uzh.github.io/signal-collect、http://graphlab.org、https://01.org/graphbuilder这样的框架中进行分区，然后再将其导入到Neo4j中。其中一些框架还具有内置的分区算法。这将会是一个很好的社区贡献！ - Alex Averbuch