0
$\begingroup$

Suppose a vector x of size n in real numbers such that the sum of all elements is equal to 1, is it possible to construct a graph with n nodes such that every element in x corresponds to the PageRank of the enumerated nodes? Since an exact solution is less likely, is it possible to create an approximate solution?

My assumptions for this problem:

  1. The PageRank algorithm has a damping factor.
  2. The input vector is normalized.

My initial idea was to start by ordering the nodes by the difference between their present and desired Pagerank, then 'donating' Pagerank by adding links from nodes that are above their desired Pagerank value. I implemented a version in C++, but it does not converge; instead, the first iteration is the closest iteration to the desired Pagerank vector. I wanted to pick the math stackexchange community's brains to see whether anyone had any better ideas.

$\endgroup$
1
$\begingroup$

Hint You are really asking this. Given a vector $\vec{x} \in \mathbb{R}^n$ with $x_i \ge 0$ and $\sum x_i = 1$, can we construct a matrix $A \in \mathbb{R}^{n \times n}$ such that $$A \vec{x} = \vec{x} \Leftrightarrow (A-I_n)\vec{x} = \vec{0}$$

$\endgroup$
  • $\begingroup$ Wow! Yes, that totally makes sense. Let me get back to you when I think I've proven or disproven that I can. $\endgroup$ – Nikhil Shinday Jul 21 '15 at 13:51
  • $\begingroup$ @NikhilShinday new question did not come through. consider posting it as a separate question and pasting the link here $\endgroup$ – gt6989b Jul 21 '15 at 13:52
  • $\begingroup$ I'll post the next question when I've proven it to myself. $\endgroup$ – Nikhil Shinday Jul 21 '15 at 13:53
  • $\begingroup$ Right, this is obvious. To prove that the first implies the second, Ax - x = 0, then (A-I)*x = 0. The other way around Ax-I_n*x = 0, Ax = x. Now, I need to prove that the matrix must exist. $\endgroup$ – Nikhil Shinday Jul 21 '15 at 15:31
  • $\begingroup$ The trivial solution is $$A=I_{n}$$, but that's unsatisfactory because it's a poor representation of the web -- it is not constructed by exclusively self-referring pages. So I suppose that a more stringent restriction to put on A is that $$\sum_i^n{A_{ij}}=1\forall j\in n,A_{ii}=0 \forall i\in n$$ then, A is a stochastic matrix with no links referring to itself. $\endgroup$ – Nikhil Shinday Jul 21 '15 at 15:45

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.