在一個巨大的稀疏矩陣中尋找所有的週期

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不會削減它。你也無法找到你的數據中的所有循環（除非它非常稀疏），它們將會有太多。它們也將會重疊並且不是很有意義，你可能會發現的是幾個最大的週期。