Return to Answer

After reading MotiN's nice answer, I have decided to modify his procedure as follows:

Let $N(v)=\{\,w\mid w\in V, v\sim w\,\}$ be the neighborhood of $v$. Let $d(v,w)$ be the length of the shortest path between $v$ and $w$.

We draw samples from $V_k$ by means of a random walk from $v_0$ with $k$ steps. At each step $i$, we pick a random edge from $v_{i+1}\in N(v_i)\setminus\{v_{i-1}\}$ with $v_1$ picked from $N(v_0)$, i.e. we do not pick the edge we just came from. Further restrictions can be made (e.g. by means of FSM pruning) to improve the yield.

For each sample $v_k$, we determine all shortest paths to $v_0$ and thus $d(v_0, v_k)$. If $d(v_0, v_k)=k$, we accept the sample, otherwise we reject it. The probability of a sample being accepted is the yield $y=P\big(d(v_0, v_k)=k\big)$ which we compute during the sampling process.

For each accepted sample $v_k$, we have a set of shortest paths $S$ leading from $v_0$ to it. We can use this set to compute the probability $P(v_k)$ of having chosen this sample by summing over all shortest paths to $v_k$:

$$P(v_k)=\sum_{v_0,\dots,v_k\in S}{1\over|N(v_0)|}\prod_{i=1}^k{1\over|N(v_i)|-1}$$

Using the yield $y$, we can compute the chance $p$ of having chosen $v_k$ from all accepted samples:

$$p=P\big(v_k\mid d(v_0,v_k)=k\big)={P[v_k]\over y}$$

If $|V_k|$ is known, this can be used to compute a bias $b$ for the sample $v_k$

$$b=p\,|V_k|$$

This method allows us to sample vertices from $V_k$ and to compute the bias of each path leading to the sample picked. While we do not get a uniform sample this way, we can compensate for the bias later on.

After reading MotiN's nice answer, I have decided to modify his procedure as follows:

Let $N(v)=\{\,w\mid w\in V, v\sim w\,\}$ be the neighborhood of $v$. Let $d(v,w)$ be the length of the shortest path between $v$ and $w$.

We draw samples from $V_k$ by means of a random walk from $v_0$ with $k$ steps. At each step $i$, we pick a random edge from $v_{i+1}\in N(v_i)\setminus\{v_{i-1}\}$ with $v_1$ picked from $N(v_0)$, i.e. we do not pick the edge we just came from. Further restrictions can be made (e.g. by means of FSM pruning) to improve the yield.

For each sample $v_k$, we determine all shortest paths to $v_0$ and thus $d(v_0, v_k)$. If $d(v_0, v_k)=k$, we accept the sample, otherwise we reject it. The probability of a sample being accepted is the yield $y=P\big(d(v_0, v_k)=k\big)$ which we compute during the sampling process.

For each accepted sample $v_k$, we have a set of shortest paths $S$ leading from $v_0$ to it. We can use this set to compute the probability $P(v_k)$ of having chosen this sample by summing over all shortest paths to $v_k$:

$$P(v_k)=\sum_{v_0,\dots,v_k\in S}{1\over|N(v_0)|}\prod_{i=1}^{k-1}{1\over|N(v_i)|-1}$$

Using the yield $y$, we can compute the chance $p$ of having chosen $v_k$ from all accepted samples:

$$p=P\big(v_k\mid d(v_0,v_k)=k\big)={P[v_k]\over y}$$

If $|V_k|$ is known, this can be used to compute a bias $b$ for the sample $v_k$

$$b=p\,|V_k|$$

This method allows us to sample vertices from $V_k$ and to compute the bias of each path leading to the sample picked. While we do not get a uniform sample this way, we can compensate for the bias later on.

After reading MotiN's nice answer, I have decided to modify his procedure as follows:

Let $N(v)=\{\,w\mid w\in V, v\sim w\,\}$ be the neighborhood of $v$. Let $d(v,w)$ be the length of the shortest path between $v$ and $w$.

We draw samples from $V_k$ by means of a random walk from $v_0$ with $k$ steps. At each step $i$, we pick a random edge from $v_{i+1}\in N(v_i)\setminus\{v_{i-1}\}$ with $v_1$ picked from $N(v_0)$, i.e. we do not pick the edge we just came from. Further restrictions can be made (e.g. by means of FSM pruning) to improve the yield.

For each sample $v_k$, we determine all shortest paths to $v_0$ and thus $d(v_0, v_k)$. If $d(v_0, v_k)=k$, we accept the sample, otherwise we reject it. The probability of a sample being accepted is the yield $y=P[d(v_0, v_k)=k]$ which we compute during the sampling process.

For each accepted sample $v_k$, we have a set of shortest paths $S$ leading from $v_0$ to it. We can use this set to compute the probability $P[v_k]$ of having chosen this sample by summing over all shortest paths to $v_k$:

$$P[v_k]=\sum_{v_0,\dots,v_k\in S}{1\over|N(v_0)|}\prod_{i=1}^k{1\over|N(v_i)|-1}$$

Using the yield $y$, we can compute the chance $p$ of having chosen $v_k$ from all accepted samples:

$$p=P[v_k\mid d(v_0,v_k)=k]={P[v_k]\over y}$$

If $|V_k|$ is known, this can be used to compute a bias $b$ for the sample $v_k$

$$b=p\,|V_k|$$

This method allows us to sample vertices from $V_k$ and to compute the bias of each path leading to the sample picked. While we do not get a uniform sample this way, we can compensate for the bias later on.

After reading MotiN's nice answer, I have decided to modify his procedure as follows:

Let $N(v)=\{\,w\mid w\in V, v\sim w\,\}$ be the neighborhood of $v$. Let $d(v,w)$ be the length of the shortest path between $v$ and $w$.

We draw samples from $V_k$ by means of a random walk from $v_0$ with $k$ steps. At each step $i$, we pick a random edge from $v_{i+1}\in N(v_i)\setminus\{v_{i-1}\}$ with $v_1$ picked from $N(v_0)$, i.e. we do not pick the edge we just came from. Further restrictions can be made (e.g. by means of FSM pruning) to improve the yield.

For each sample $v_k$, we determine all shortest paths to $v_0$ and thus $d(v_0, v_k)$. If $d(v_0, v_k)=k$, we accept the sample, otherwise we reject it. The probability of a sample being accepted is the yield $y=P\big(d(v_0, v_k)=k\big)$ which we compute during the sampling process.

For each accepted sample $v_k$, we have a set of shortest paths $S$ leading from $v_0$ to it. We can use this set to compute the probability $P(v_k)$ of having chosen this sample by summing over all shortest paths to $v_k$:

$$P(v_k)=\sum_{v_0,\dots,v_k\in S}{1\over|N(v_0)|}\prod_{i=1}^k{1\over|N(v_i)|-1}$$

Using the yield $y$, we can compute the chance $p$ of having chosen $v_k$ from all accepted samples:

$$p=P\big(v_k\mid d(v_0,v_k)=k\big)={P[v_k]\over y}$$

If $|V_k|$ is known, this can be used to compute a bias $b$ for the sample $v_k$

$$b=p\,|V_k|$$

This method allows us to sample vertices from $V_k$ and to compute the bias of each path leading to the sample picked. While we do not get a uniform sample this way, we can compensate for the bias later on.

After reading MotiN's nice answer, I have decided to modify his procedure as follows:

Let $N(v)=\{\,w\mid w\in V, v\sim w\,\}$ be the neighborhood of $v$. For $v\in V_i$ let $C(v)=N(v)\cap V_{i+1}$ be the neighbors of $v$ that are farther away from $v_0$ as in MotiN's answer and let $\bar C(v)=N(v)\cap V_{i-1}$ be the vertices that are nearer to $v_0$. The graph I care about is bipartite so $C(v)\mathbin{\dot\cup}\bar C(v)=N(v)$, but that's not particularly important to the algorithm.

The algorithm works as follows:

1. Compute $W$ as a set of $n$ vertices reached from $k$ step random walks from $v_0$ such that $W\subset V_k$.
2. For each $v_n\in W$ with $v_0\sim v_1\sim \ldots\sim v_n$ being the path taken to reach $v_n$, let $$b(v_n)=\frac{|\bar C(v_1)|}{|C(v_0)|}\frac{|\bar C(v_2)|}{|C(v_1)|}\cdots\frac{|\bar C(v_n)|}{|C(v_{n-1})|}$$ be the bias of $v_n$.
3. Let $c>1$ be the oversampling factor and take $n\over c$ weighted random samples $S\subset W$ with weights $w(v)=b(v)^{-1}$ for each $v\in W$.
4. Return $S$.

The key idea behind this algorithm is to instead of rejecting samples during the random walk (and thus getting a very low yield), we compute the bias of each sample and compensate for it by taking a random sample weighted by reciprocal bias out of the samples gained through the random walk. This should cancel the bias, giving uniformly random samples.

I am not exactly sure how to choose $c$ though.

After reading MotiN's nice answer, I have decided to modify his procedure as follows:

Let $N(v)=\{\,w\mid w\in V, v\sim w\,\}$ be the neighborhood of $v$. Let $d(v,w)$ be the length of the shortest path between $v$ and $w$.

We draw samples from $V_k$ by means of a random walk from $v_0$ with $k$ steps. At each step $i$, we pick a random edge from $v_{i+1}\in N(v_i)\setminus\{v_{i-1}\}$ with $v_1$ picked from $N(v_0)$, i.e. we do not pick the edge we just came from. Further restrictions can be made (e.g. by means of FSM pruning) to improve the yield.

For each sample $v_k$, we determine all shortest paths to $v_0$ and thus $d(v_0, v_k)$. If $d(v_0, v_k)=k$, we accept the sample, otherwise we reject it. The probability of a sample being accepted is the yield $y=P[d(v_0, v_k)=k]$ which we compute during the sampling process.

For each accepted sample $v_k$, we have a set of shortest paths $S$ leading from $v_0$ to it. We can use this set to compute the probability $P[v_k]$ of having chosen this sample by summing over all shortest paths to $v_k$:

$$P[v_k]=\sum_{v_0,\dots,v_k\in S}{1\over|N(v_0)|}\prod_{i=1}^k{1\over|N(v_i)|-1}$$

Using the yield $y$, we can compute the chance $p$ of having chosen $v_k$ from all accepted samples:

$$p=P[v_k\mid d(v_0,v_k)=k]={P[v_k]\over y}$$

If $|V_k|$ is known, this can be used to compute a bias $b$ for the sample $v_k$

$$b=p\,|V_k|$$

This method allows us to sample vertices from $V_k$ and to compute the bias of each path leading to the sample picked. While we do not get a uniform sample this way, we can compensate for the bias later on.