7

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

但我想知道有什么方法可以对存储在 Neo4j 中的图进行分区吗？或者我必须转储 Neo4j 的数据并手动转换节点和边缘格式以适应 METIS 输入格式？

4

2 回答 2

8

关于新奇有趣的算法，这绝不是详尽无遗或最先进​​的，但这些是我首先要看的地方：

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

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

特定算法：EvoCut“使用演化集在本地查找稀疏切割” ——微软的局部概率算法——与这些论文相关

  • 难以实施
  • 本地算法 - 类似 BFS 的访问模式（随机游走）
  • 自从我阅读那篇论文已经有一段时间了，但我记得它是建立在干净的抽象之上的：
    • EvoNibble（可插入 - 决定要添加到当前集群的邻域数量
    • EvoCut（多次调用 EvoNibble 以查找本地集群）
    • EvoPartition（反复调用 EvoCut 对整个图进行分区）
  • 非确定性

通用算法系列：层次图聚类

从高层次来看：

  • 通过将节点折叠成聚合节点来粗化图形
    • 粗化策略可选
  • 在粗化/更小的图中查找集群
    • 聚类策略可选
  • 逐步去粗化图，在每一步细化聚类
    • 精炼策略可选

笔记：

  • 如果图形变化缓慢（或结果不需要是最新的），则可以粗化一次（或不经常）然后使用粗化的图形 - 以节省计算
  • 我不知道要推荐的具体算法

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

  • 未确认的节点类型 - 即，所有节点均被平等对待
  • 未确认的关系类型 - 即所有关系均平等对待
  • 未确认关系方向 - 即，将关系视为无向
于 2013-08-08T14:35:14.693 回答
4

过去曾独立使用 METIS 和 Neo4j，我不知道有任何工具可以从 Neo4j 生成 METIS 文件。话虽如此，编写这样一个工具应该是一件容易的事，并且会是一个伟大的社区贡献。

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

在划分图的更一般的问题上，很可能通过合理的努力来实现一些更知名和简单的算法。

于 2013-08-08T13:46:05.383 回答