java - 在一个巨大的稀疏矩阵中找到所有循环

Question

首先，我是一个 Java 初学者，所以我不确定这是否可行!基本上我有一个巨大的(3+百万)关系数据数据源(即 A 是 B+C+D 的 friend ，B 是 D+G+Z 的 friend (但不是 A - 即非互惠)等)我想要在这个(不一定连接的)有向图中找到每个循环。

我找到了线程 Finding all cycles in graph ，这让我想到了 Donald Johnson 的(初级)循环查找算法，至少从表面上看，它看起来会做我想做的事情(我打算在星期二回来工作时尝试 - 认为在此期间问一下也没什么坏处!)。

我快速浏览了 Johnson 算法的 Java 实现代码(在那个线程中)，看起来关系矩阵是第一步，所以我想我的问题是:

a) Java 是否能够处理 3+million*3+million 矩阵？ (计划用二进制稀疏矩阵表示 A-friends-with-B)

b) 我是否需要将找到每个连接的子图作为我的第一个问题，或者循环查找算法是否会处理不相交的数据？

c) 这实际上是解决问题的适当方法吗？我对“基本”循环的理解是，在下图中，不是选择 A-B-C-D-E-F，而是选择 A-B-F、B-C-D 等，但这并不是任务的世界末日。

    E
   / \
  D---F
 / \ / \
C---B---A

d) 如有必要，我可以通过加强关系中的相互关系来简化问题 - 即 A-friends-with-B <==> B-friends-with-A，如果真的有必要，我可以减少数据大小，但实际上它总是在 100 万左右。

z) 这是 P 还是 NP 任务？!我是否贪多嚼不烂？

谢谢大家，感谢任何帮助! 安迪

Answer 1

您正在做的事情类似于数据挖掘中一个经过深入研究的问题，称为关联规则挖掘或更普遍的频繁项集挖掘。您可以通过频繁的项目集挖掘找到的东西比您正在做的要具体一点，但也更有用。

我们将进行封闭式频繁项集挖掘，这会找到所有 friend 组，其中每个人都是彼此的 friend 。

我现在要说的是，Java 不能做你想让它做的事。它不能加载那么多内存，而且在任何合理的时间内处理该数据的效率都不够高，您将需要使用 C/C++。我建议使用 LCM，它是一个封闭的频繁项集挖掘器，但由于您拥有的数据量，您还需要将支持设置得相当高。

您可能要考虑的另一件事是阅读大图挖掘，这也是一个相当大的研究领域，但 Java 不会削减它。此外，您将无法找到数据中的所有循环(除非它非常稀疏)，它们将会太多。它们也会重叠并且意义不大，您可能会发现几个最大的周期。