用于计算图中三角形的流算法

Question

如参考文献中所述，算法（参见底部）假设输出估计器 $ \ hat t $ 在给定图中的三角形＃ $ g=（v，e）$ ，表示 $ t $ 。写了“它很容易被证明” $$ e [\ hat t]= t $$ 但不幸的是，我没有看到它。试图分析 $ e [\ hat t] $ ，我认为如下：

• 在第1行，表示随机（和均匀）选择一个边缘，该边缘是三角形的一部分作为 $ p $ 。由于三角形可以共享边缘， $$ \ frac t m \ le p \ frac {3t} m $$ 例如，考虑以下情况：

  

  中央三角形不会将新边缘添加到可能性的数量，以选择是三角形的一部分的边缘。您可以想象一种不同的配置，其中只有3个外三角形，它们不会互相接触（在这种配置中，我们不会看到中央第4三角形）。在两种情况下（（案例I）4中所见的4个三角形;（案例II）3个不相交的三角形），选择是三角形的一部分的边缘的概率为1（尽管三角形的＃是不同的。< / p>

• 在第2行，在随机选择的概率均匀的顶点，该顶点是“关闭三角形”，与前一步的边缘完全是 $ \ frac 1 {n -2} $ 。

因此我只看到

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

我缺少什么？

---

另一个关于第3行的问题。订购流，我们首先选择一个随机边缘 $（u，v）$ （第1行），然后一个随机顶点 $ w $ 从 $ v \ backslash \ {u，v \} $ （行2）。我觉得分析应该考虑到第3行我们检查 $（u，w）$ 和 $（ v，w）$ 出现 $（u，v）$ 在流中。也许在我将理解我的第一个问题的答案之后，它将更清楚。

---

算法：

1. 从流中随机地选择边缘 $（u，v）$ 。
2. 选择一个顶点 $ w $ 随机从 $ v \ backslash \ {u，v \} $ < / span>
3. 如果 $（u，w）$ 和 $（v，w）$ 在< Span Class=“Math-Container”> $（u，v）$ 在流中，然后输出 $ m（n-2） $ 。否则，输出 $ 0 $ 。

也，虽然我没有看到它写了，但我相信有一个假设 $ v $ 是领先的。

---

参考：数据流讲义由amit chakrabarti教授的讲义说明，部分“15.3三角形计数”， https://www.cs.dartmouth.edu/~ac/teach/data-streams-lecnotes.pdf

---

最好的问候

Answer 1

let $（u，v，w）$ 是流中的特定三角形，并假设边缘 $（u，v）$ 首先出现。我们选择 $（u，v）$ 在第一步中的概率是 $ 1 / m $ 。我们选择 $ w $ 的概率是 $ 1 /（n-2）$ 。因此，我们选择三角形 $（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， $ 是不相交的（请注意，三角形不必不相交）。因此，如果存在 $ t $ 三角形，那么我们选择其中一个的概率正好是 $ t / [m（ n-2）] $ 。因此，算法的预期输出正是<跨度类=“数学容器”> $ t $ 。