問題タブ [clique]

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 完全です。

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

ブール値の 2D 配列が与えられた場合、少なくとも 2 列と少なくとも 2 行で構成されるすべてのパターンを見つけたいと考えています。この問題は、グラフ内のクリークを見つけることにいくらか近いものです。

以下の例では、緑のセルは「真」のビットを表し、グレーは「偽」を表します。パターン 1 には列 1、3、4、5 と行 1、2 が含まれます。パターン 2 には列 2、4、行 2、3、4 のみが含まれます。

この背後にあるビジネス アイデアは、ソーシャル ネットワーク ユーザーのさまざまなグループ間で類似パターンを見つけることです。実際には、行数は 3E7 まで、列数は 300 までです。

ブルートフォースマッチング以外の解決策を実際に理解することはできません。

問題の適切な名前をアドバイスしてください。詳細を読むか、エレガントな解決策をアドバイスしてください。

クリーク、エンクルスなどのサブスペース クラスタリング アルゴリズムで高密度ユニットを計算するために高次元データを格納する方法。? たとえば、20 次元のポイントがあるため、配列が使用されている場合、20 次元を割り当てる必要があり、メモリが不足します。コードは「C」で書かれているので、高次元のポイントを保存するために何を使用できるかを提案してください。

私にグラフのクリークを与えるブラックボックス（/アルゴリズム）があるとしましょう。そこからクリークカバーを見つける方法はありますか？

私が見つけようとしている直感的なアイデアが写真に示されています。ブラックボックスの部分を探しています。さらに説明が必要な場合は、お気軽にお問い合わせください。クリークのエッジを削除してグラフを更新するアイデアがあります。うまくいくかはわかりません。他にもアイデアお待ちしております。

また、近似クリーク被覆アルゴリズムの良いリファレンスを教えていただけると大変助かります。

大きなグラフ (100000 ノード) があり、そのサイズ 5 のクリークを見つけたいと考えています。この目的のために次のコマンドを使用します。

この演算の計算には多くの時間がかかります。最初にグラフのすべての最大クリークを見つけようとし、次にサイズ 5 のクリークを選択しようとするようです。これは、これら 2 つのコマンドが同じジョブを実行しているにもかかわらず、これら 2 つのコマンドの実行時間に大きな違いがあるためだと思います。

adjacent.trianglesサイズ 5 のクリークを効率的に見つけるようなコマンドを探しています。

ありがとう

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

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

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

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

感謝

グラフ G を考えると、次の 2 つの情報が必要です。

1. G のクリークの数。
2. それらのクリークの相対的なサイズ。

たとえば、サイズ 3 のクリークが 3 つ、サイズ 4 のクリークが 10 個、サイズ 5 のクリークが 7 つなどです。

私は Python を使用しており、ライブラリ networkx で多くの関数が定義されていることを知っています。これらの結果を得るのを手伝ってくれる人はいますか?