ランダムグラフ生成の期待値を計算する方法

Question

こんにちは、これは私の最初の質問です。私は計算の手がかりを見つけることができないアルゴリズムと確率で宿題をしました。

質問：グラフ内の三角形の数を計算する：無向グラフG =（V、E）の場合、Gの三角形はサイズ3のクリークです（正式には、ノード{u、v、w }は、（u、v）、（v、w）、（u、w）がGのすべての辺である場合、Gの三角形です。グラフ内の三角形の数を近似するために、以下のアルゴリズムを考えてみる。まず、サンプリングされたグラフG '=（V、E'）を以下のように構築する。 G 'の頂点集合はGの頂点集合と同じである。全てのe∈Eに対して、eを確率p（Eのpを、例えば、0.1と考える）でE'に入れる。この新しいサンプリングされたグラフG 'では、三角形の数を数え、G'の三角形の数をT 'とする（G'の三角形の数を数えるために黒いボックスサブルーチンを与えたと仮定する）。次に、T = T '/ pを出力する。 T = T、Tの期待値が元のグラフGの三角形数であることを示します。

GのGまたはG 'のエッジがGの2つの隣接する三角形が独立している可能性があるため、エッジを共有する。そして、Gのすべての頂点のペアがG 'の中でエッジを形成することはできません。GのエッジだけがG'の中にpで存在します。 GやG 'の辺の数と三角形の数の関係を考えるのは難しいです。

誰かが私にいくつかのヒントを与えることができます、全体の解決策ではないこともできます。 G又はGで

Answer 1

エッジ」三角形を形成するGに隣接する2つの三角形がエッジに

を共有するかもしれないので問題ではない独立していません。期待値の合計は、相関関係に関係なく合計の期待値です。したがって、三角形について個別に推論することができます。