グラフ内の三角形をカウントするためのストリーミングアルゴリズム

Question

参考文献に記載されているように、特定のグラフ内の三角形の＃の推定値 $ \ hat t $ を出力すると仮定してください。 $ g=（v、e）$ 、 $ t $ を表します。 「簡単に表示できる」と書かれています $$ e [\ hat t]= T. $$ しかし残念ながら、私はそれを見ていません。 $ e [\ hat t] $ を分析しようとしている、次のように考えます：

• 1行目で、ランダムに（そして一様に） $ p $ として三角形の一部であるエッジを選択します。三角形がエッジを共有できるので $$ \ frac t m \ le p \ le \ frac {3t} m $$ たとえば、次のような場合を考えてください。

  

  中央三角形は、三角形の一部であるエッジを選択する可能性のある新しいエッジを追加しません。 3つの外側の三角形があるだけで、互いに触れないように別の構成を想像できます（この構成では、4番目の三角形が表示されません）。どちらの場合（（ケースI）4画像に見られるように4つの三角形。（ケースII）3異なる三角形を除いて、三角形の一部であるエッジを選択する確率は1です（三角形の数は異なっていますが）。< / P>

• ライン2で、前のステップからのエッジで「三角形を閉じる」頂点をランダムにする確率は右 $ \ frac 1 {nです。 -2} $ 。

だから私はその

だけを見ます

$$ t \ le e [\ hat t] \ le 3t $$

私は何が足りないの？

---

もう1つの質問は行3に見られます3.ストリームは注文され、最初にランダムなエッジ $（u、v）$ （行1）を選びます。その後、ランダムな頂点 $ w $ から $ v \ backslash \ {u、v} $ （行> 2）。 4行目では、 $ と $をチェックすることを分析する必要があります。 v、w）$ は、ストリーム内の $（u、v）$ の後に表示されます。私の最初の質問に対する答えを理解した後、それはより明確になります。

---

アルゴリズム：

1. エッジ $（u、v）$ をストリームからランダムに均一に選択します。
2. vertex $ w $ $ v \ backslash \ {u、v \} $ < / span>
3. $（u、w）$ と $（v、w）$ が< SPAN CLASS="math-container"> $（u、v）$ 、 output $ m（n-2） $ 。 出力 $ 0 $ 。

また、私はそれが書かれていませんでしたが、 $ v $ が先に知られているという仮定があると思います。

---

リファレンス：データストリーム講演会AMIT CHAKRABARTI PROUS「15.3トライアングルカウント」、 https://www.cs.dartmouth.edu/~ac/teach/data-streams-lecnotes.pdf

---

ベストアンズ

Answer 1

$（u、v、w）$ には、ストリーム内の特定の三角形になり、エッジが最初に表示されます。最初のステップで $（u、v）$ を選択する確率は、 $ 1 / m $ です。 2番目の手順で $ w $ を選択する確率は、 $ 1 /（n-2）$ です。したがって、Triangle $（u、v、w）$ を選択する確率は $ 1 / [m（n-2）です。 ）] $ 。 $ e_ {u、v、w} $ でこのイベントを表現しましょう。

$（u_1、v_1、w_1）$ と $（u_2、v_2、w_2）$ イベント $ e_ {u_1、v_1、w_1} $ と $ e_ {u_2、v_2、$ e_2、v_2の2つの異なる三角形です。 $ は互いに素です（三角形が互いに違う必要はありません）。したがって、 $ t $ trianglesがある場合は、それらの1つを選択した確率は右 $ t / [mです。 n-2）] $ 。したがって、アルゴリズムの予想出力は右 $ t $ です。