Consider a finite, undirected, scale-free graph $\{G}$, with uniform edge weights. We define a truncated random walk on $\{G}$ as a random walk that continues for exactly $\{k}$ steps. For an arbitrary truncated random walk of $\{k}$ steps (i.e. beginning at an arbitrary node), what is the probability that a given node $\{n}$ in the graph is hit by the random walk?

Is this determined, as is my intuition, by $\{k}$ and the degree of $\{n}$? Has this been proved? Does the fact that this is a scale-free graph make the question of determining the probability that a node is hit by a random walk more or less difficult?

Edited to add: By scale-free, I mean that the degree distribution of the graph follows a power law. This characteristic is typical of "real-world" graphs. See, for example, scale-free network at Wolfram.

  • 1
    $\begingroup$ what does "scale-free" mean? The opposite of "kosher"? $\endgroup$ – Igor Rivin Nov 8 '11 at 17:33
  • $\begingroup$ Also sometimes known as small world graphs. $\endgroup$ – Andrew D. King Nov 8 '11 at 20:58

Section IX.3 of "Modern Graph Theory" by Béla Bollobás considers hitting and commute times on a simple undirected graph $G \triangleq (V, E)$ with $\lvert V \rvert = n$ and $\lvert E \rvert = m$. He works with "simple random walks" (SRWs), where the transition probability $P_{xy}$ is $\frac{1}{d(x)}$ if $xy \in E$ and 0 otherwise. He defines $\pi$ to be the stationary distribution $\pi_{x} \triangleq d(x)/2m$ and also fixes an arbitrary distribution $p$ over $X_0$, the starting node of the SRWs under consideration.

On page 311 he defines $S_k(i)$ as the number of times node $i$ is hit in the first $k$ steps of a given SRW. He shows

Theorem 15 We have $\lim_{k \to \infty} \mathrm{E}[S_k(x)/k] = d(x)/2m$, and $(S_k(x)/k)_{x \in V}$ tends to $\mathbf{\pi}$ in probability as $k \to \infty$.

So the answer above is more than an upper bound.

If we consider fixing the starting node $x_0$, then a natural question to ask is how quickly $(S_k(x)/k)_{x \in V}$ tends to the stationary distribution (how quickly you get "lost"). That notion is captured by the mixing time of the SRWs on $G$, discussed in section IX.4 of the same book. It's defined in terms of $\lVert p_t - \pi \rVert$, where $p_t$ is the distribution over $V$ of $x_t$, the node hit on step $t$. It turns out the mixing rate can be calculated in terms of the eigenvalues of the transition matrix $P$. If $\lambda_1 \geq \lambda_2 \geq \dots \lambda_n$ are the eigenvalues of $P$, then the mixing rate is $\max(\lambda_2, \lvert \lambda_n \rvert)$.

With respect to scale-free graphs, a reasonable approach would be to understand their spectra then work out what value of $k$ you want to guarantee you'll stop your walks before getting too lost. I don't know whether that's easy, hard, or done.

  • $\begingroup$ This is essentially what I was looking for, though I am still curious whether the scale-free-ness of the graph changes the game at all. $\endgroup$ – david Nov 11 '11 at 18:47
  • $\begingroup$ I think it will just change the mixing time, and I presume make it much faster than "other" graphs. $\endgroup$ – roman garnett Nov 11 '11 at 18:53

It sounds to me that since you start at an arbitrary node of the graph (i.e., chosen from the stationary distribution $\mu$ of the random walk), every step of your walk would still be stationary. So the probability that the given node $n$ is hit at a particular step $t$ is always $\mu(n)$. Thus $k \mu(n)$ is certainly an upper bound (union bound) of the probability that $n$ is hit at least once in the first $k$ steps.

If by hit you mean hit by the last step (kth step), then it's even easier. The probability would exactly be $\mu(n)$, since stationarity is preserved in each step. I also share Igor's question regarding "scale-free".

  • 2
    $\begingroup$ "Arbitrary" does not usually mean "chosen from the stationary distribution". $\endgroup$ – Ori Gurel-Gurevich Nov 8 '11 at 20:01

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.