In short: if a Markov chain models a (generalized) pagerank, is it always possible to remove any of its state and obtain a Markov chain that models a pagerank close to the initial one?
Full details.
Given:
- a finite directed graph $G=(V,E)$ with $E \subseteq V\times V$,
- two functions $P$ and $\alpha$ over vertices in $V$ such that $\sum_v P(v) = 1$ and $\alpha(v) \in [0,1]$ for all $v$, and
- a weight function $\omega$ over $V\times V$ such that for all $u$, $\sum_v \omega(u,v) = 1$, and $\omega(u,v) = 0$ if $(u,v) \not\in E$,
we define the pagerank Markov chain of $G$, $\omega$, $P$ and $\alpha$ by its transition matrix $M$ defined for all $u$ and $v$ in $V$ by: $M_{u,v} = \alpha(u)\cdot\omega(u,v) + (1-\alpha(u))\cdot P(v)$. Such Markov chains are generalizations of the classical (personalized) pagerank.
Now let us consider any vertex $v$ in $V$, denote by $V'$ the set $V\setminus \{v\}$, and by $E'$ the set $(E \cap V'\times V') \cup \{u, (u,v)\in E\} \times \{w, (v,w)\in E\}$. In other words, the graph $G'=(V',E')$ is obtained from $G$ by removing vertex $v$ and its edges, and adding edges from its predecessors to its successors only.
Question: Is it always possible to find functions $\omega'$, $P'$, and $\alpha'$ such that the pagerank Markov chain of $G'$, $\omega'$, $P'$ and $\alpha'$ has stationary distribution proportional to the one defined above?
Notice that it is always possible to find a Markov chain with stationary distribution proportional to the initial one; my question is: it is always possible to find one that is a pagerank Markov chain on $G'$?
If $v$ is a bridge node, i.e. $|\{u, (u,v)\in E\}| = |\{w, (v,w)\in E\}| = 1$, then I am able to prove that the answer is positive. I use Section 3 of the paper Stochastic Complementation, Uncoupling Markov Chains, and the Theory of Nearly Reducible Systems by Carl D. Meyer to obtain the wanted Markov chain and then exhibit (quite terrible) expressions for $\omega'$, $P'$, and $\alpha'$.
The general case however seems much more complex. Maybe a better characterization of pagerank Markov chains would help finding a counter-example?