그래프의 삼각형 개수를 계산하는 스트리밍 알고리즘

Question

참조에 설명된 대로 알고리즘(하단 참조)은 추정기를 출력한다고 가정합니다. $\모자 T$ 주어진 그래프의 삼각형 수에 대해 $G = (V, E)$, 표시 $T$."쉽게 보여질 수 있다"고 쓰여 있다$$ e [ hat t] = t $$하지만 아쉽게도 볼 수는 없습니다.분석하는 중 $E[\모자 T]$, 나는 다음과 같이 생각합니다.

• 라인 1에서 삼각형의 일부인 모서리를 무작위로(그리고 균일하게) 선택할 확률을 다음과 같이 나타냅니다. $p$.삼각형은 모서리를 공유할 수 있으므로$$ frac t m le p le frac {3t} m $$예를 들어 다음과 같은 경우를 고려해보세요.

  

  중앙 삼각형은 삼각형의 일부인 가장자리를 선택할 수 있는 가능성의 수에 새 가장자리를 추가하지 않습니다.외부 삼각형 3개만 있고 서로 닿지 않는 다른 구성을 상상할 수 있습니다(이 구성에서는 중앙의 4번째 삼각형이 표시되지 않습니다).두 경우 모두 ((case i) 이미지에 표시된 대로 4개의 삼각형;(케이스 ii) 3개의 분리된 삼각형) 삼각형의 일부인 모서리를 선택할 확률은 1입니다(삼각형의 개수는 다르지만).

• 라인 2에서 이전 단계의 모서리와 "삼각형을 닫는" 꼭지점을 균일하게 무작위로 선택할 확률은 정확히 다음과 같습니다. $\frac 1 {n-2}$.

그러므로 나는 그것만 본다.

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

내가 무엇을 놓치고 있나요?

---

제가 가지고 있는 또 다른 질문은 3번째 줄에 관한 것입니다.스트림은 순서가 지정되어 있으며 먼저 임의의 가장자리를 선택합니다. $(유, v)$ (라인 1), 임의의 정점 $w$ ~에서 $V \백슬래시 \{u, v\}$ (라인 2).분석에서는 3행에서 다음 사항을 확인해야 한다는 점을 고려해야 한다고 생각합니다. $(유, 승)$ 그리고 $(v, w)$ 나타나다 ~ 후에 $(유, v)$ 스트림에서.아마도 첫 번째 질문에 대한 답을 이해하고 나면 더 명확해질 것입니다.

---

연산:

1. 가장자리를 선택하세요 $(유, v)$ 스트림에서 균일하게 무작위로.
2. 정점 선택 $w$ 균일하게 무작위로 $V \백슬래시 \{u, v\}$
3. 만약에 $(유, 승)$ 그리고 $(v, w)$ 이후에 나타남 $(유, v)$ 스트림에서 산출 $m(n-2)$.또 다른, 산출 $0$.

또한, 비록 쓰여진 것을 보지는 못했지만, 나는 다음과 같은 가정이 있다고 믿습니다. $V$ 앞서 알려져 있습니다.

---

참조:교수의 강의 노트를 데이터 스트리밍합니다.Amit Chakrabarti, 섹션 "15.3 삼각형 계산", https://www.cs.dartmouth.edu/~ac/Teach/data-streams-lecnotes.pdf

---

친애하는

Answer 1

허락하다 $(u,v,w)$ 하천의 특정 삼각형이 되고 가장자리가 다음과 같이 가정됩니다. $(유,v)$ 먼저 나타납니다.우리가 선택한 확률 $(유,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,w_2}$ 분리되어 있습니다(삼각형이 분리될 필요는 없습니다).그러므로 만약 있다면 $T$ 삼각형 중 하나를 선택할 확률은 정확히 다음과 같습니다. $T/[m(n-2)]$.따라서 알고리즘의 예상 출력은 정확히 다음과 같습니다. $T$.