2
$\begingroup$

I'm reading Newman's Networks: An Introduction. Generally, this is a fantastic book but there's an argument in the development on graph random walks where I feel like technical details are being glossed over and I'd like to understand them better.

Suppose our undirected graph with no self-loops is represented by the adjacency matrix $A_{N \times N}$ of binary elements. Further suppose the degree of node $i \in \{1, 2, \ldots, N \}$ is denoted $k_i$. The random walk is defined such that the next step is chosen discrete-uniformly from the neighbor set of a given vertex. Last, from a fixed starting point, let $p_i(t)$ denote the probability of being on node $i$ at time $t \in \mathbb{N}$.

With this development, it's not too hard to see that

$$ p_i(t)=\sum_{j=1}^{N}\frac{A_{ij}}{k_j}p_j(t-1) $$

or $$ \mathbf{p}(t)= \mathbf{A}\mathbf{D}^{-1}\mathbf{p}(t-1)$$ where $D$ is a diagonal matrix such that $(D)_{ii}=k_{i}$.

Here's the weird part

The author wants to evaluate $\lim_{t\rightarrow \infty} \mathbf{p}(t)$ and writes

$$ p_i(\infty)= \sum_{j=1}^{N}\frac{A_{ij}}{k_j}p_j(\infty)$$

or in mattrix form

$$ \mathbf{p} = \mathbf{A}\mathbf{D}^{-1}\mathbf{p}$$

This is not a rigorous argument. One concern I have is that the walk need not be ergodic in general, in which case there is no stationary distribution. Is the author simply assuming the graph is not bipartite (in which case we know the graph is periodic) and further that it's completely connected, or is there something deeper going on?

$\endgroup$
1
  • $\begingroup$ How does he go on? That condition is necessary, but not sufficient. (Besides the problems you mention, $\mathbf{p} = 0$ is a solution.) $\endgroup$ – Fabio Somenzi Apr 2 '17 at 4:36

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.