大きなグラフ (100000 ノード) があり、そのサイズ 5 のクリークを見つけたいと考えています。この目的のために次のコマンドを使用します。
cliques(graph, min=5, max=5)
この演算の計算には多くの時間がかかります。最初にグラフのすべての最大クリークを見つけようとし、次にサイズ 5 のクリークを選択しようとするようです。これは、これら 2 つのコマンドが同じジョブを実行しているにもかかわらず、これら 2 つのコマンドの実行時間に大きな違いがあるためだと思います。
adjacent.triangles (graph) # takes about 30s
cliques(graph, min=3, max=3) # takes more than an hour
adjacent.trianglesサイズ 5 のクリークを効率的に見つけるようなコマンドを探しています。
ありがとう
と の間には大きな違いがadjacent.triangles()ありcliques()ます。三角形を数えるadjacent.triangles()だけで済み、それらをすべて保存する必要があります。多くの三角形がある場合、これは時間差を簡単に説明できます。(もう 1 つの要因は、 のアルゴリズムが汎用的であり、三角形に限定されていないことです。三角形のみに関心があることがわかっているため、いくつかの最適化が含まれている可能性があります)。cliques()cliques()adjacent.triangles()
価値があるのは、すべての最大クリークを見つけるわけでcliques()はありません。2 クリーク (エッジ) から開始し、指定した最大サイズに達するまで、それらを 3 クリーク、4 クリークなどにマージします。しかし、繰り返しますが、グラフに多くの 3-クリークがある場合、これは簡単にボトルネックになる可能性があります。なぜなら、アルゴリズムにはすべての 3-クリークを保存しなければならないポイントが 1 箇所あるからです (それらに興味がない場合でも)。 4-クリークを見つけるためにそれらが必要です。
maximal.cliques()グラフ内の最大クリークがどのくらい大きいかを大まかに把握するには、おそらく最初に使用する方がよいでしょう。ここでの考え方は、サイズkの最大クリークがあり、サイズ 5 のすべてのサブセットが 5-クリークであるということです。これは、最大のクリークを検索し、少なくともサイズ 5 のものを保持し、サイズ 5 のすべてのサブセットを列挙するだけで十分であることを意味します。ただし、いくつかのクリークが複数回カウントされる可能性があるため、別の問題が発生します。
更新: ソースコードをチェックしましたが、基本的には、すべての頂点をループし、頂点vadjacent.trianglesごとに、隣接するすべての(u, w)ペアを列挙し、uとwが接続されているかどうかをチェックするだけです。もしそうなら、頂点vに隣接する三角形があります。n個の頂点があり、平均次数がdの場合、これは O(nd 2 ) 演算ですが、任意のサイズの頂点のグループには一般化されません (コード for でk -1 ネストされた for ループをハードコーディングする必要があるため)サイズkのグループ)。