2
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ Well, if you choose $\alpha'(v) = 0$ for all vertices $v$, you can achieve any stationary distribution you would like to have by simply choosing $P'$ to be that stationary distribution. So I suspect you want to impose an additional restriction on the parameters? $\endgroup$ Jun 1, 2021 at 9:05
  • 1
    $\begingroup$ @JochenGlueck You are right! Surely, I do not want to have to compute the initial stationary distribution, but being more specific is not so easy. Let me say that I want to find solutions in time and space $O(|N(v)|)$, the degree of removed vertex $v$. $\endgroup$ Jun 1, 2021 at 12:21
  • $\begingroup$ Thanks for your response! I think it's not possible in general to find a solution within the time constraints that you specified; indeed, assume that it was possible. Every stochastic $d \times d$-matrix $M$ can be interpreted as a transition matrix as given in your model, and it takes $O(d^2)$ time to compute the corresponding model parameters from $M$. The number $|N(v)|$ is bounded by $d$, so we can remove vertex $1$ and build, by assumption, a $(d-1) \times (d-1)$ model in $O(d)$ time such all remaining components of the stationary distribution are the same. [...] $\endgroup$ Jun 1, 2021 at 23:03
  • $\begingroup$ [...] Computing the stationary distribution of the $d \times d$-matrix when $d-1$ components are already known also takes $O(d)$ time. By iterating this argument $d-1$-times we can reduce the problem to a $1 \times 1$-situation and from this, we can thus compute the stationary distrubution of $M$ in $O(d^2)$ time; but I don't think $O(d^2)$ is possible for computation of stationary distrubtions, in general (admittedly, though, I'm not an expert in numerical mathematics). $\endgroup$ Jun 1, 2021 at 23:03

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.