問題タブ [clique-problem]

クリークの問題を解決しようとしています。私は Bron Kerbosch Clique アルゴリズムを使用しています。これは Java で適切に記述されており、巧妙な実装がここにあります。ただし、クリーク硬度のおかげで、非常に遅くなる可能性があり、

私がやりたいことは、それらが接続されていることがわかっている頂点の初期セットを使用することです。次にメソッドを呼び出します。私の人生では、結果が派閥ではないということで、ここで何が間違っているのかわかりません。

注: コメント付きのコードは、元のコード (上記のリンク) からのものです。

要するに、私の唯一の変更はgetAllMaximalCliques方法です。ここで再帰呼び出しメソッドがどのように機能するかはよくわかりません。

何か助けや指示をいただければ幸いです。

Pregel/spark-pregel の実装を利用して、Scala を使用して無向グラフのクリークを見つけたいと考えています。それを行うための提案やアルゴリズムは高く評価されます。

サブグラフ同型

グラフ G_1=(V_1,E_1), G_2=(V_2,E_2) があります。

質問: グラフ G_1 は G_2 の部分グラフと同形ですか?

(つまり、|V|=|V_1| および |E|=|E_1| となる G_2、V ⊆ V_2 の頂点のサブセット、および G_2 のエッジのサブセット、E ⊆ E_2 があり、1 対{u,v} ∈ E_1 <=> { f(u),f(v) } ∈ E) となる、G_2 の頂点 V のサブセットでの G_1 の頂点の 1 つの一致、f:V_1 -> V

• 問題のサブグラフ同型が NP に属することを示します。
• 問題が NP 完全であることを示し、問題の Clique をそれに還元します。(ヒント: グラフ G_1 が完成していると考えてください)

私は次のことを試しました：

• 非決定論的チューリング マシンは、最初にノード V のサブセットと G_2 のエッジ E のサブセットを「推測」し、その後、|V|=|V_1| であることを検証します。および |E|=|E_1| {u,v} ∈ E_1 <=> { f(u), f(v) } ∈ E となるような 1 対 1 の対応 f: V_1 -> V があること。

O(|V_2|^2) 個の異なる頂点のペアがあるため、チェックには多項式時間が必要です。したがって、問題は NP に属します。

• (G,k) をクリーク問題の任意のインスタンスとします。ここで、k はクリークの頂点の数です。

サブグラフ同型問題のインスタンスを多項式時間で次のように構成できます。 G_2 は n 頂点上のグラフです。

G_1 は、いくつかの k <= n について、k 個の頂点の完全なグラフです。G=G_2 とします。問題 Subgraph Isomorphism には、G_2 に k 個の頂点を持つ完全な部分グラフがある場合、つまり、グラフ G に k 個の頂点を持つ完全な部分グラフがある場合に解があります。

したがって、問題 Clique の最初のインスタンスに解がある場合、Subgraph Isomorphism の問題のインスタンスには解があります。

したがって、Subgraph Isomorphism の問題は NP 完全です。

それが正しいかどうか、または何か改善できるかどうか教えていただけますか?

隣接行列の連結要素をグループ化する並べ替え手法を探しています。

たとえば、青と緑の 2 つのグループでイラストを作成しました。最初に、'1' のエントリがマトリックスの行と列に分散されます。行と列を並べ替えると、すべての「1」がマトリックスの 2 つの連続したセクションに配置され、青と緑のコンポーネントがより明確になります。

この並べ替え手法が何と呼ばれているか思い出せません。隣接行列、クリーク、並べ替え、並べ替えのさまざまな組み合わせを検索しました。

私が見つけた最も近いヒットは

1. symrcm要素を対角線に近づけますが、グループは作成しません。

2. Rで密なコーナーを作成するために行列の行と列を並べ替える方法はありますか? 完全に空の行と列を削除することに焦点を当てています

より効果的にグーグルできるように、この手法の一般的な名前を提供するか、Matlab 関数の方向を教えてください。

まず、これは私の宿題だと言いたい。ただし、私の問題を解決するために、必要な文献を使用できます。

問題はその名前から明らかだと思いますが、次のように説明します。サイズK.」

からおよび から3-SATへの多項式簡約について知っています。( http://mlnotes.com/2013/04/29/npc.html ) ただし、これら 2 つの削減を組み合わせることができないため、これには問題があります。からへの削減も試みましたが、あまり成功しませんでした。CLIQUE3-SATINDEPENDENT-SETCLIQUECLIQUE-OR-INDEPENDENT-SET

だから私は本当にヒントをいただければ幸いです！

前もって感謝します。

~200 のノードと ~3500 のエッジのグラフを扱っています。このグラフのすべてのクリークを見つける必要があります。networkx を使用enumerate_all_cliques()すると、最大 100 ノードの小さなグラフでは問題なく動作しますが、大きなグラフではメモリが不足します。

「しかし、このアルゴリズムはメモリ内に候補サブリストを保持するだけで、使い果たされたサブリストを継続的に削除するため、メモリ不足にならないことを願っています。」enumerate_all_cliques() のソースコード

メモリを節約するために、すべてのクリークではなく、長さ k のすべてのクリークのジェネレーターを返す方法はありますか?

Ka,b biclique の定義に依存するBiclique Communities メソッド ( Lehmann, Schwartz, & Hansen, 2008 ) を R で再現しようとしています。次の例は、隣接する 2 つの K2,2 バイクリークを示しています。最初のクリークは {A,B,1,2} で、2 番目のクリークは {B,C,2,3} です。これをより広範なデータセットに適用できるように、R を使用してこれらのクリークを識別できるようにしたいと考えています。

これまでの試行を R に含めましたが、次の 2 つの問題に悩まされています。

1. 標準の walktrap.community を使用すると、コミュニティは認識されますが、セット {B,2} が両方のクリークに属することは許可されません
2. 更新されたclique.community関数を使用すると、これはクリークを識別していないように見えるか、正しく理解していません (またはその両方)。

コード例:

私はグラフを持っており、それはノードに隣接するマトリックスです。問題は、「すべてからすべて」に隣接するすべてのノードを見つけることです。たとえば、(写真で) 結果は[1,2,3,7]、このすべてのノードが一緒に接続されている必要があります。どのような種類のグラフでも、すべての「すべてからすべて」のノード コレクションのリストを取得する必要があります。それを解決する方法は？ありがとう。

私は理論計算機の初心者で、K-CLIQUE が P に属していることを証明するために多項式時間で機能するようなアルゴリズムを実行するように依頼されました。

n 頂点のグラフを取るアルゴリズムについて考えていました。各頂点、たとえば S0 について、たとえば (s1 、 s2 、 s5) などのクリークの数を確認し、次に S1 でクリークがあるかどうかを確認しますs2, s5 次に、s2 に移動し、s5 とのクリークがあるかどうかを確認します。

しかし、私は自分の人生を複雑にしていると思いますよね？

アルゴリズムに関する提案はありますか? 私はそれが簡単であることを知っており、アルゴリズムを見つける方法がどのように機能するかを理解するために、誰かが私を助けてくれるかもしれません.

感謝