問題タブ [clique]

無向グラフ G = G(V, E) が与えられた場合、多項式時間で最大のクリークのサイズを見つけるにはどうすればよいですか? エッジの数がわかれば、最大クリーク サイズに上限を設定できます。

https://cs.stackexchange.com/questions/11360/size-of-maximum-clique-given-a-fixed-amount-of-edges

、そしてその上限から 1 まで下向きに繰り返すことができます。この上限は O(sqrt(|E|)) であるため、O(sqrt(|E|) * sqrt で最大クリーク サイズを確認できると思います。 (|E|) * sqrt(|E|)) 時間。

この NP 完全問題をより効率的に解決する方法はありますか?

解決しようとしている問題があります。クリークを受け取り、そのクリークを含む最大のクリークを返すメソッドを実装したいと考えています。私が取り組んでいる方法は再帰的であり、バックトラッキングを使用して、クリークの定義に従ってソリューションを受け入れたり拒否したりします。私の問題は、メソッドにパラメーターを 1 つだけ渡したいので、Bron-Kerbosch アルゴリズムを使用したくないことです。これが私がやったことの疑似コードです：

再帰を破る条件を選択する方法についてのアイデアを手伝ってもらえますか? 次の候補の値をメソッドのパラメータに渡さずに次のループまで保持する方法がわかりません!

~17000 の加重頂点と ~75% の密度を持つグラフで既知の頂点数を持つ最大クリークを (およそ) 見つけることができるソフトウェアまたはアルゴリズムの説明はありますか? Cliquer を使用しようとしましたが、遅すぎます (結果を得るのに数日かかりました)。

念のため、私の問題について少し-それはスケジューリングの問題です.18のタイムスロットがあり、それぞれが異なる数の選択肢で満たされる可能性があります. 各変数は、1 つのスロットの 1 つの選択肢を表します。したがって、1 つのスロットのすべての代替は相互に排他的であり、異なるスロットの一部の代替は互換性がありません。2 つの代替案に互換性がある場合、それらの間に優位性があります。重みは、代替の値を表します。

クリークによってバインドしたいネットワークがありますが、これを正しく行う方法がわかりません。kコアを使用してこれと同じプロセスを実行できますが、クリークのみを含むグラフを作成するための正しいプロセスがわかりません。

関数を使用してサブグラフを検索するプロセスを示したらk_core、誰かが関数を使用してサブグラフを検索するプロセスを変更するのを手伝ってくれることを期待していましたclique。

まず、空手クラブのグラフを使用してグラフを作成します。

iPython でグラフにプロットします。

次に、4 コア内にある (エッジが 4 つ以上ある) すべてのエッジを見つけます。

これらのエッジを新しいグラフに追加します。

4 コア グラフをプロットします。

これを行う方法についてのアイデアはありますが、k コアを使用してネットワークをバインドする代わりに、4 つ以上の頂点を持つクリークを使用しますか?

現実の問題:

私は多くの企業の取締役に関するデータを持っていますが、「XYZ の取締役であるジョン・スミス」と「ABC の取締役であるジョン・スミス」が同一人物である場合もあれば、そうでない場合もあります。また、「John J. Smith, director of XYZ」と「John Smith, director of ABC」は同一人物である場合もあれば、同一でない場合もあります。多くの場合、追加情報の調査 (たとえば、「XYZ のディレクター、ジョン・スミス」と「ABC のディレクター、ジョン・スミス」に関する伝記データの比較) により、2 つの観測が同一人物であるかどうかを解決できます。

問題の概念的なバージョン:

その精神で、一致するペアを特定するデータを収集しています。たとえば、次の一致するペアがあるとします: {(a, b), (b, c), (c, d), (d, e), (f, g)}. 「同一人物」という関係の推移性を利用して、 の「連結成分」を生成したい{{a, b, c, d, e}, {f, g}}。それは{a, b, c, d, e}一人であり、{f, g}別の人です。(質問の以前のバージョンでは、明らかに別のものである「クリーク」に言及していました。これは、(私の目的では)「間違った」結果を与えていた理由を説明します) find_cliques。networkx

次の Python コードがその役割を果たします。しかし、私は疑問に思います: より良い (計算コストの少ない) アプローチ (例えば、標準または利用可能なライブラリを使用する) はありますか?

関連すると思われる例があちこちにありますが (例: Cliques in python )、これらは不完全であるため、それらが参照しているライブラリや、それらを使用するためのデータのセットアップ方法がわかりません。

サンプル Python 2 コード:

これにより、目的の出力が生成されます: [Set(['a', 'c', 'b', 'e', 'd']), Set(['g', 'f'])].

サンプル Python 3 コード:

これにより生成されます[set(['a', 'c', 'b', 'e', 'd']), set(['g', 'f'])]):

150 万ペアの要素 (' ' で区切られている) で構成される配列があります。

要素の各ペアは一意であり、要素は 15 ～ 20 文字の文字列です。

私のパイプラインでは、この配列は [0] 「要素 1 が要素 2 に関連している」、[1] 「要素 2 が要素 3 に関連している」などを意味します。関連するすべての要素をまとめてクラスタ化し、次のような出力を得たいと考えています。

このタスクは非常に単純で、おそらくそれを行うための明らかな方法が欠けていると思いますが、要素をクラスター化する高速な方法 (つまり、数分から数時間) を見つけられませんでした。