問題タブ [clique]

セミ クラスタリング アルゴリズムは、Google Pregel の論文で言及されています。セミクラスターのスコアは、以下の式を使用して計算されます

どこ

Ic はすべての内部エッジ
の重みの合計です Bc はすべての境界エッジの重みの合計です
Vc はセミ クラスター内の頂点の数であり、
fb は境界エッジ スコア係数です (ユーザーが 0 ～ 1 の間で定義)。

アルゴリズムは非常に簡単でしたが、上記の式がどのように得られたのか理解できませんでした。分母は Vc 個の頂点間で可能なエッジの数であることに注意してください。

誰か説明してくれませんか？

クリークカバー問題を解決するライブラリまたはコード（できればJava）を知っている人はいますか？

OCamlバージョンを見つけましたが、もっと簡単に統合できるものを使いたいです。

グラフで最大クリークを見つけるためのJavaコードとCコードも見つけましたが、このコードを利用してクリークカバーを見つける方法がわかりません（たとえば、ノードがなくなるまで最大クリークを繰り返し削除します）。最適なソリューションは得られません）。

私はRのフォロワー関係に基づいたTwitterネットワークに取り組んでいます。このネットワークでは、誰もが自分のタイムラインでお互いのツイートを読むことができる最大の派閥のサイズを確認したいと思います。したがって、largest.cliquesが必要になります。しかし、この関数は方向性を無視しています。igraphパッケージに統合されていないことは知っていますが、すべてのノードがアクティブかつパッシブに相互に接続されている有向ネットワークでクリークを見つける方法はありますか？

私は基本的なクリークの問題を解決しようとしていましたが、次のいくつかの点で立ち往生しています:

• what is is the minimum size of the largest clique in any graph with N nodes and M edges

• To Find the largest clique in a graph

上記の2つのステートメントの違いを教えてください。

クリーク問題 (特に k-clique) に関する質問です。そのようなクリークが存在する場合、接続されたグラフのプロパティを利用して特定のサイズのクリークを見つけるアルゴリズムはありますkか?

大学のプロジェクトでは、 Bron-Kerboschアルゴリズムを実装しようとしています。つまり、特定のグラフにすべての最大クリークをリストします。

私は最初のアルゴリズムを（ピボットせずに）実装しようとしていますが、ウィキペディアの例でテストした後、私のコードはすべての答えを生成しません。これまでの私のコードは次のとおりです。

答えの一部しか得られない理由はありますか？

ネットロゴについて質問があります。(無向) リンクで接続されたノードのグラフ構造がいくつかあります。これらの構造の 1 つに含まれる最小のサブグラフを特定する必要があります。基本的にサブグラフとは、どのノードがすべて相互に接続されているかを意味します。したがって、5 つのノードの構造があり、ノード 1 が 2 と 3 に接続されているとします。ノード 2 から 3、1 および 4。ノード 3 から 1、2、および 5 ノード 1、2、および 3 はすべて相互接続されているため、ノード 1、2、および 3 のサブグラフを検出する必要があります。

これを行う簡単な方法はありますか、それとも基本的に計算上不可能ですか?

編集: netlogo 拡張機能 nw を使用すると、 nw:maximal-cliques メソッドを使用して必要なものを計算できることがわかりました。今は別の問題がありますが。このようにして派閥のリストのリストを埋めようとしています

lista-cliques は通常長さ 2 ですが、clique のタートルのリストであるべき最初の要素は次のようなリストです

guild = g のタートルによって作成されたグラフの長さが約 2 ～ 8 タートルである場合、長さは 300 です。nw:maximal-cliques の呼び出しは適切に行われていますか?

私が間違っていることのアイデアはありますか?

編集2:これを行うことでリストの長さを修正する方法を考え出しました

現在、リストは 300 ノードではなく、ギルド = g のノードを含むグラフ上のノードの数と同じです。

つまり、

に等しい

ノードが 1 つまたは 2 つのノードにしか接続されていないグラフが表示されるため、これも明らかに間違っています。近づいていると思いますが、nw:maximal-cliques が最大クリークのリストではなく、グラフ上のすべてのノードのリストを作成する理由がわかりません。

何か案は？

ありがとう

私の問題はこれです：

私は人々のリストを持っています。各人は特定の数の Facebook のいいねを持っています。これらの人々を N 個のグループに分割し、各グループのすべてのメンバーが少なくとも 1 つの「いいね」を共有するようにします (つまり、このグループの全員が Daft Punk が好きです)。グループは 3 人または 4 人以外のサイズにすることはできず、グループに属さない人の数を最小限に抑えたいと考えています。（ただし、不一致の人をさらに最小限に抑えることができるという意味であれば、固定サイズのルールを破ってもかまいません）

ビンパッキングとクリークを調べるように言われましたが、それらは私の問題にはまったく適していません。

以前の質問を検索すると、属性に基づいて入力データをセットに分類する このようなものは機能するように見えますが、グループのすべてのメンバーには複数の値 (いいね! の配列) があります。また、除外される人の数が最小限に抑えられるかどうかもわかりません。

前もって感謝します！

s-clique を s-independent セットに変換することに関するアルゴリズム クラスの宿題の質問があります。以下はコードで、一番下の関数independent_set_decision(H,s)は私が完了する必要があるものです。私は困惑しています。