Suppose $G=\langle V,E \rangle$ is a directed graph consisting of $n\in \mathbb{N}$ vertices. Vertex $v_i \in V$ has an edge to vertex $v_j \in V$ with a probability of $P(i, j) = f(|i-j|)$ where $f$ is a descending "good enough" function.

What is probability to have a path of length $k$?

Update 1. Let us consider a simplified problem. Suppose the probability of having an edge between any two arbitrary vertices is fixed and equals $p$. Thus, the adjacency matrix $\bf A$ consists of elements $a_{ij} = \delta(p)$ equal $1$ with a probability of $p$.

It's well known that $({\bf A}^k)_{ij}$ gives the number of $k$-paths from $v_i$ to $v_j$. Can we employ that?

  • $\begingroup$ It is not exactly clear how arcs are distributed. Is it for a $fixed$ acyclic digraph $G$, each arc of $G$ is deleted with probability $1-P(i,j)$? Or do you not mean to include the term acyclic? $\endgroup$ – D Poole Oct 30 '13 at 14:07
  • $\begingroup$ @DPoole OK, let's remove the acyclicity requirement as irrelevant. $\endgroup$ – Yury Bayda Oct 30 '13 at 19:14
  • $\begingroup$ A few more questions. Do you want to know the probability that the digraph has a path of length $k$ or for some generic $v_i$ and $v_j$, the probability that there is a path of length $k$ between $v_i$ and $v_j$? Also are you looking for the exact probability or are asymptotic bounds for this probability sufficient? If asymptotic bounds are good, what range of $k$ and $p$ are you looking at? $\endgroup$ – D Poole Nov 1 '13 at 18:37
  • $\begingroup$ @DPoole 1) the probability that the digraph has a path of length $k$. 2) exact probability (nevertheless, an example of asymptotic estimation will be useful) $\endgroup$ – Yury Bayda Nov 1 '13 at 21:24
  • 1
    $\begingroup$ In the limit for large graphs, the result you are looking for is Theorem 2.1 of arxiv.org/pdf/1005.4104v1.pdf $\endgroup$ – ckoe Nov 25 '15 at 15:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.