probability of having cycle in a random directed graph with a given in-degree distribution

1.2k Views Asked by At

Consider directed graph $G \left(V, E\right)$. Let random variable $N$ be the in-degree of a vertex. We assume that in-degree values are i.i.d random variables with PMF $f_N(n)$.

1- What is the probability of having no directed cycle of size $k$ in graph $G$?

2- Is there any tight bound? A trivial but very loose upper bound is $\binom{|V|}{k}\big(f_N(k)\big)^k$.

PS: if it helps, we can assume that $N$ has a discrete Weibull distribution.

1

There are 1 best solutions below

0
On BEST ANSWER

To get a handle on the probability that there is a cycle of length $k$, let's first find the probability that a particular edge is present in the graph. Let $n=|V|$.

Let $\mathcal{N}$ denote the random in-degree of a vertex $y$ and let $x$ be a vertex other than $y$. Then \begin{align*} P(\vec{xy} \in G) &= \sum_{k=1}^{n-1} P(\vec{xy} \in G | \mathcal{N}=k) P(\mathcal{N}=k) \\ &= \sum_{k=1}^{n-1} \frac{k}{n-1} P(\mathcal{N}=k) = \frac{\mu}{n-1}, \end{align*} where $\mu$ is the expected in-degree of a generic vertex. In the argument above, I use the fact that conditioned on $\mathcal{N}=k$, the set of vertices with edges leading into $y$ is uniformly distributed on all $k$-sets of $V \setminus \{y\}$. In particular, $$ P(\vec{xy} \in G | \mathcal{N}=k) = \frac{{n-2 \choose k-1}}{{n-1 \choose k}} = \frac{k}{n-1}. $$

Now fix a potential cycle of length $k$. What is the probability that $x_1 \to x_2 \to \ldots \to x_k \to x_1$ is present? Now, because each of these potential edges lead into distinct vertices, whether or not the edges of the form $\vec{x_1 x_2}, \vec{x_2 x_3}, \ldots, \vec{x_k x_1}$ are present are independent events. Therefore $$ P(x_1 \to x_2 \to \ldots \to x_k \to x_1 \text{ is present}) = \left(\frac{\mu}{n-1} \right)^k. $$

Now \begin{align*} P(\exists \text{ cycle of length }k) &\leq E[\#\text{ of cycles of length }k] \\ &= {n \choose k} (k-1)! \left(\frac{\mu}{n-1} \right)^k \leq \left(\frac{n}{n-1}\right)^k \frac{\mu^k}{k}. \end{align*}

This bound is "tight" in the following sense: If $f_N(n)$ is binomially distributed with $n-1$ trials and success probability $p=\frac{c}{n}$, where $c$ is fixed, then we are looking at the random graph $G(n, p=c/n)$. The number of cycles of length $k$ is asymptotically Poisson distributed with mean $\mu^k/k$ [$k$ is fixed here].

To find a workable lower bound, it depends on the range of the parameters that you are interested in. If $k$ is small and $\mu$ is large enough, then you may suspect that the number of cycles of length $k$ is asymptotically Poisson distributed with mean about $\mu^k/k$. In this case, the probability that there are no cycles of length $k$ tends to $e^{-\mu^k/k}$. Using the Chen-Stein method, you can find an upper bound on $|P(\text{no cycle})-e^{-\lambda}|,$ where $\lambda = E[\#\text{ of cycles of length }k]$.

See Theorem 1 in this paper for the Chen-Stein method.