Problem

  1. Let G=<V,E>G = \left< V, E \right> be an undirected graph with ∣V∣=n|V| = n vertices and ∣E∣=m|E| = m edges.

  2. The number of triangle in GG is denoted as Δ\Delta.

  3. For each v∈Vv \in V, let N(v)≐{u:(v,u)∈E}N(v) \doteq \{ u : (v, u) \in E \} be the set of neighbors of vv.

  4. The degree of vv is dv≐∣N(v)∣d_v \doteq | N(v) |.

  5. Define λ(v)\lambda(v) be the number of triangles whose vertices contains vv.

  6. Similarly, for each e=(u,v)∈Ee = (u, v) \in E, define λ(e)\lambda(e) the number of triangles whose edges contains ee.

Exact Algorithm

Theorem. The number of triangles in GG can be computed in O(m1.5)O \big ( m^{1.5} \big) time.

Proof.

WLOG, we assume that the vertices in VV are labelled from 11 to nn in increasing order according to their degrees, such that

d1≤d2≤...≤dn. d_1 \le d_2 \le ... \le d_n.

Each triangle in GG can be represented by a unique triple (u,v,w)∈[n]3(u, v, w) \in [n]^3 such that du≤dv≤dwd_u \le d_v \le d_w. To count the number of such triples, we can execute the following algorithm.

For each u∈[n]u \in [n] do
\quad For v∈N(u)v \in N(u) of uu s.t. dv≥dud_v \ge d_u do
\quad\quad For w∈N(u)w \in N(u) of uu s.t. dw≥dvd_w \ge d_v do
\qquad\quad Check whether (u,v,w)(u, v, w) is a triangle.

It is left to prove that the algorithm has complexity O(m1.5)O(m^{1.5}).

Lemma. For each (u,v)∈E(u, v) \in E, such that du≤dvd_u \le d_v, the number of w∈N(u)w \in N(u) such that dw≥dvd_w \ge d_v is bounded by O(m)O(\sqrt{m}).

  • The claim is trivial if du≤md_u \le \sqrt{m}.

  • Otherwise, suppose that du≥md_u \ge \sqrt{m}. But the number of w∈Vw \in V such that dw≥du≥md_w \ge d_u \ge \sqrt{m} is bounded by O(m/m)=O(m)O( m / \sqrt{ m }) = O(\sqrt{ m }).

□\square

Sampling Algorithms

Subgraph Sampling

  1. Sample each edge independently with some probability pp.
  2. Count the number of triangles, Δ~\tilde \Delta, in the sampled subgraph.
  3. X←(1/p3)⋅Δ~X \leftarrow \big( 1 / p^3 \big) \cdot \tilde \Delta.

Properties

Theorem (Unbiased Estimator). XX is an unbiased estimator of Δ\Delta.

Proof. For each triangle in GG, define the indicator random variable ZZ for its inclusion in teh sampled subgraph. Then E[Z]=p3\mathbb{E}[Z] = p^3. Let SS be the collection of such random variable. By linearity of expectation.

E[∑Z∈SZ]=∑Z∈SE[Z]=p3⋅Δ. \mathbb{E} \left[ \sum_{Z \in S } Z \right] = \sum_{Z \in S } \mathbb{E} \left[ Z \right] = p^3 \cdot \Delta.

It follows that (1/p3)∑Z∈SZ(1 / p^3) \sum_{Z \in S} Z is an unbiased estimator of Δ\Delta.

□\square

Let ΔN\Delta^N be the number of triangles that share an edge.

Theorem (Variance). XX has variance

(1/p6)⋅(Δ⋅(p3−p6)+2⋅ΔN⋅(p5−p6)). (1 / p^6) \cdot \left( \Delta \cdot \big( p^3 - p^6 \big) + 2 \cdot \Delta^N \cdot \big( p^5 - p^6 \big) \right).

Proof.

Var[1p3∑Z∈SZ]=1p6⋅(∑Z∈SVar[Z]+∑Z,Z′∈SCov[Z,Z′])=1p6⋅(∑Z∈SVar[Z]+∑Z,Z′∈S∧Z shares an edge with Z′Cov[Z,Z′])=1p6⋅(∑Z∈S(p3−p6)+∑Z,Z′∈S∧Z shares an edge with Z′(p5−p6))=1p6⋅(Δ⋅(p3−p6)+2⋅ΔN⋅(p5−p6)). \begin{aligned} \mathbb{Var} \left[ \frac{1}{p^3} \sum_{Z \in S } Z \right] &= \frac{1}{p^6} \cdot \left( \sum_{Z \in S } \mathbb{Var} \left[ Z \right] + \sum_{Z, Z' \in S } \mathbb{Cov} \left[ Z, Z' \right] \right) \\ &= \frac{1}{p^6} \cdot \left( \sum_{Z \in S } \mathbb{Var} \left[ Z \right] + \sum_{Z, Z' \in S \wedge Z \text{ shares an edge with } Z' } \mathbb{Cov} \left[ Z, Z' \right] \right) \\ &= \frac{1}{p^6} \cdot \left( \sum_{Z \in S } \big( p^3 - p^6 \big) + \sum_{Z, Z' \in S \wedge Z \text{ shares an edge with } Z' } \big( p^5 - p^6 \big) \right) \\ &= \frac{1}{p^6} \cdot \left( \Delta \cdot \big( p^3 - p^6 \big) + 2 \cdot \Delta^N \cdot \big( p^5 - p^6 \big) \right). \end{aligned}

□\square

Vertex Sampling

  1. Sample a vertex vv uniformly at random from VV.
  2. Compute λ(v)\lambda(v).
  3. X←(n/3)⋅λ(v)X \leftarrow \big( n / 3 \big) \cdot \lambda(v).

Properties

Theorem (Unbiased Estimator). XX is an unbiased estimator of Δ\Delta.

Proof.

E[X]=n3⋅∑v∈V1n⋅λ(v)=13⋅∑v∈Vλ(v)=Δ. \mathbb{E}[X] = \frac{n}{3} \cdot \sum_{v \in V} \frac{1}{n} \cdot \lambda(v) = \frac{1}{3} \cdot \sum_{v \in V} \lambda(v) = \Delta.

□\square

Theorem (Variance). XX has variance ((n/9)⋅∑v∈Vλ(v)2)−Δ2\left( (n / 9) \cdot \sum_{v \in V} \lambda(v)^2 \right) - \Delta^2.

Proof.

Var[X]=E[X2]−E[X]2=(n9⋅∑v∈Vλ(v)2)−Δ2. \begin{aligned} \mathbb{Var} \left[ X \right] = \mathbb{E}[X^2] - \mathbb{E}[X]^2 = \left( \frac{n}{9} \cdot \sum_{v \in V} \lambda(v)^2 \right) - \Delta^2. \end{aligned}

□\square

Edge Sampling

  1. Sample an edge ee uniformly at random from EE.
  2. Compute λ(e)\lambda(e).
  3. X←(m/3)⋅λ(e)X \leftarrow \big( m / 3 \big) \cdot \lambda(e).

Properties

Theorem (Unbiased Estimator). XX is an unbiased estimator of Δ\Delta.

Proof.

E[X]=m3⋅∑e∈E1m⋅λ(e)=13⋅∑e∈Eλ(e)=Δ. \mathbb{E}[X] = \frac{m}{3} \cdot \sum_{e \in E} \frac{1}{m} \cdot \lambda(e) = \frac{1}{3} \cdot \sum_{e \in E} \lambda(e) = \Delta.

□\square

Theorem (Variance). XX has variance ((m/9)⋅∑e∈Eλ(v)2)−Δ2\left( (m / 9) \cdot \sum_{e \in E} \lambda(v)^2 \right) - \Delta^2.

Proof.

Var[X]=E[X2]−E[X]2=(m9⋅∑e∈Eλ(e)2)−Δ2. \begin{aligned} \mathbb{Var} \left[ X \right] = \mathbb{E}[X^2] - \mathbb{E}[X]^2 = \left( \frac{m}{9} \cdot \sum_{e \in E} \lambda(e)^2 \right) - \Delta^2. \end{aligned}

□\square

Triangle Sampling

  1. Sample an edge e=(u,v)e = (u, v) uniformly at random from EE.
  2. Sample a vertex uniformly at random from {N(u),w.p.du/(du+dv),N(v),w.p.dv/(du+dv).\begin{cases} N(u), & \text{w.p.} & d_u / (d_u + d_v) , \\ N(v), & \text{w.p.} & d_v / (d_u + d_v) . \end{cases}
  3. I←{1,if(u,v,w) constitutes a triangle,0,otherwise.I \leftarrow \begin{cases} 1, & \text{if} (u, v, w) \text{ constitutes a triangle}, \\ 0, & \text{otherwise}. \end{cases}
  4. X←(m/6)⋅(du+dv)⋅IX \leftarrow \big( m / 6 \big) \cdot \big( d_u + d_v \big) \cdot I.

Properties

Theorem (Unbiased Estimator). XX is an unbiased estimator of Δ\Delta.

Proof. Conditioned on the sampled edge e=(u,v)e = (u, v),

E[I∣e=(u,v)]=2⋅∣N(u)∩N(v)∣du+dv=2⋅λ(e)du+dv. \mathbb{E}[ I \mid e = (u, v) ] = \frac{ 2 \cdot |N(u) \cap N(v) | }{d_u + d_v} = 2 \cdot \frac{ \lambda(e) }{d_u + d_v}.

Hence, (1/2)⋅(du+dv)⋅I(1 / 2) \cdot (d_u + d_v) \cdot I is an unbiased estimator of λ(e)\lambda(e). It follows that

E[(m/6)⋅(du+dv)⋅I]=m3⋅E[(1/2)⋅(du+dv)⋅I]=m3⋅∑e∈E1m⋅E[(1/2)⋅(du+dv)⋅I∣e=(u,v)]=13∑e∈Eλ(e)=Δ. \begin{aligned} \mathbb{E}[(m / 6) \cdot (d_u + d_v) \cdot I] &= \frac{m}{3} \cdot \mathbb{E}[(1 / 2) \cdot (d_u + d_v) \cdot I] \\ &= \frac{m}{3} \cdot \sum_{e \in E} \frac{1}{m} \cdot \mathbb{E}[(1 / 2) \cdot (d_u + d_v) \cdot I \mid e = (u, v) ] \\ &= \frac{1}{3} \sum_{e \in E} \lambda(e) = \Delta. \end{aligned}

□\square

Theorem (Variance). XX has variance (m/18)⋅∑e=(u,v)∈E(du+dv)⋅λ(e)−Δ2(m / 18) \cdot \sum_{e = (u, v) \in E} (d_u + d_v) \cdot \lambda(e) - \Delta^2.

Proof.

Var[X]=E[X2]−E[X]2=m236⋅∑e=(u,v)∈E1m⋅(du+dv)2⋅2⋅λ(e)du+dv−Δ2=m18⋅∑e=(u,v)∈E(du+dv)⋅λ(e)−Δ2. \begin{aligned} \mathbb{Var} \left[ X \right] &= \mathbb{E}[X^2] - \mathbb{E}[X]^2 \\ &= \frac{m^2}{36} \cdot \sum_{e = (u, v) \in E} \frac{1}{m} \cdot (d_u + d_v)^2 \cdot \frac{ 2 \cdot \lambda(e) }{d_u + d_v} - \Delta^2 \\ &= \frac{m}{18} \cdot \sum_{e = (u, v) \in E} (d_u + d_v) \cdot \lambda(e) - \Delta^2. \end{aligned}

□\square

Wedge Sampling

A wedge is a triple (u,v,w)∈V3(u, v, w) \in V^3 such that (u,v),(v,w)∈E(u, v), (v, w) \in E. If a wedge is closed, i.e., (v,w)∈E(v, w) \in E, then it constitutes a triangle. Note that each triangle contains 33 wedges. Denote WW the number of wedges in GG.

  1. Sample a wedge (u,v,w)(u, v, w) uniformly at random.
  2. I←{1,if(u,v,w) constitutes a triangle,0,otherwise.I \leftarrow \begin{cases} 1, & \text{if} (u, v, w) \text{ constitutes a triangle}, \\ 0, & \text{otherwise}. \end{cases}
  3. X←(W/3)⋅IX \leftarrow \big( W / 3 \big) \cdot I.

Properties

Theorem (Unbiased Estimator). XX is an unbiased estimator of Δ\Delta.

Proof.

E[I]=3⋅ΔW. \mathbb{E}[ I ] = \frac{ 3 \cdot \Delta }{ W }.

Therefore, X=(W/3)⋅IX = (W / 3 ) \cdot I is an unbiased estimator of Δ\Delta.

□\square

Theorem (Variance). XX has variance W⋅Δ/3−Δ2W \cdot \Delta / 3 - \Delta^2.

Proof.

Var[I]=3⋅ΔW−(3⋅ΔW)2 \begin{aligned} \mathbb{Var}[ I ] = \frac{ 3 \cdot \Delta }{ W } - \left( \frac{ 3 \cdot \Delta }{ W } \right)^2 \end{aligned}

Therefore,

Var[X]=W⋅Δ/3−Δ2 \begin{aligned} \mathbb{Var}[ X ] = W \cdot \Delta / 3 - \Delta^2 \end{aligned}

□\square

Reference

[1]. CS167: Reading in Algorithms Counting Triangles∗^∗ Tim Roughgarden†^\dagger
[1] B. Wu, K. Yi, and Z. Li, “Counting Triangles in Large Graphs by Random Sampling,” IEEE Transactions on Knowledge and Data Engineering, 2016.