在一个巨大的稀疏矩阵中寻找所有的周期

Question

首先，我是一个Java初学者，所以我不确定这是否可能！基本上，我有一个关系数据的巨大（3 +百万）数据源（即A是B + C + D的朋友，B是D + G + Z的朋友（但不是A - 即非互补）等等），我想找到这个（不一定是连接的）有向图中的每个周期。

我发现线程Finding all cycles in graph，它指出我是唐纳德约翰逊的（基本）周期寻找算法，它至少表面上看起来像它会做我以后（我要去尝试当我周二回到工作岗位时 - 认为在此期间提问并不会造成什么负面影响！）。

我不得不通过Java实现约翰逊的算法的代码快速扫描（在该线程），它看起来像关系的矩阵是第一步，所以我想我的问题是：

一） Java能够处理3百万* 3百万个矩阵吗？ （正在计划用二进制稀疏矩阵表示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-朋友-与-B < ==> B-朋友-与-A，如果真的有需要，我可以或许减少数据量，但实际上总是在1mil左右。

z）这是P还是NP任务？我咬得比我咀嚼的还多吗？

谢谢大家，任何帮助表示赞赏！ Andy

Answer 1

c）这实际上是一个合适的 解决方案的问题？我的“基本”循环 的理解是，在下面的图，而 比挑选出A-B-C-d-E-F，它会 挑选出A-B-F，B-C-d等，但是这 不是世界末日给出的 任务。

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

在唐纳德·约翰逊的纸感号“基本”是指简单，那就是，没有节点在圈中出现两次。这意味着该算法不会选择AFBCDBA，但会选择ABCDEF。

d）如果有必要，我可以通过在 关系执行相互关系简化 问题 - 即A-朋友-与-B < ==> B-朋友-与-A，而如果真的 必要我可以减少 的数据大小，但实际上它总是会在1mil 大关附近。

无向图具有（非简单）循环向量空间（它有一个很好的基础等），但我不知道它是否会帮助你。

z）这是P还是NP任务？

这是一个枚举问题，它本身不能在P和NP中。

Answer 2

找到每个周期听起来不合理。会有指数级的循环次数，所有循环都相互重叠。

至于P或NP，最慢的部分实际上是枚举每个周期（因为可能有这么多）。如果没有周期，则存在线性算法。

也许你真的想把图分成双连通分量？ 请参阅http://en.wikipedia.org/wiki/Biconnected_component

此外，在矩阵中存储图几乎是不合理的。理论上听起来不错，但在实践中没有扩展，使用邻接列表来代替（http://en.wikipedia.org/wiki/Adjacency_list）

Answer 3

你在做什么类似于数据挖掘中一个很好研究的问题，称为关联规则挖掘或更一般的频繁项目集挖掘。频繁项目挖掘可以找到什么，比你在做什么更具体，但也更有用。

我们将使用封闭的频繁项集挖掘，这样做的目的是找到所有的朋友组，每个人都是彼此的朋友。

我现在要说的是，Java不能做你想做的事情。它无法加载那么多的内存，并且它没有足够的效率在任何合理的时间内处理这些数据，您将需要使用C/C++。我建议使用LCM，它是一个封闭的频繁项目集矿工，但由于您拥有的数据量很大，您还需要设置相当高的支持。

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