1
$\begingroup$

I'm testing out a few different kind of metrics for a reranking application. I was curious and wanted to try running the PageRank algorithm to see if it could help at all. I used a similarity metric to generate "links" between items in the list that needed reranking.

The PageRank works by simulating a random web surfer. We create a matrix that represents the links between pages and then calculate the probability of surfing to another page. This is done by iterative multiplication of the NxN transition matrix by the 1xN matrix representing the probability of moving to each of the pages. I followed the simple implementation outlined here.

My first problem was that I had a symmetric similarity metric; a completely symmetrical link matrix resulted in equal ranks for every single page. I tried using a less symmetrical metric and produced the following matrix:

  7 -26 -32  -14   8 -14  -20 -14   8  

The transition matrix then was:

-0.09 0.49 0.60  0.66 -0.33 0.66   0.73 0.52 -0.24  

And after running the algorithm all three pages were ranked 0.39, which is useless. My question is how to tell if a matrix will end up producing equal PageRanks. If I knew the characteristics of the required matrix, I could search for suitable metric to fill the matrix and then experiment properly with the algorithm.

  • 2
    The document you link to does not include the term "similarity matrix", and a probability transition matrix always has *non-negative* entries and row sums equal to one. So I don't understand how you got your "transition" matrix above.2011-08-05
  • 0
    The link was just to explain the iterative multiplication of matrices that is supposed to yield a ranking. My application has nothing to do with the web, and I was attempting to use a similarity metric instead of a graph which indicates links between pages. I understand that the negative numbers are not normal in this application but the matrix still converges. Changing my example above to all positive yields a score of .33 for each page.2011-08-05
  • 3
    Nate I'm still a bit lost on what exactly you mean by "running the algorithm". Also, what do you mean when you say "the matrix converges"? Do you mean the powers of the matrix? In short, if you should explain your problem in more detail if you want to get good answers.2011-08-05
  • 1
    Not really necessary for this question, but I don't think it'll hurt to post it. AMS had a [feature column](http://www.ams.org/samplings/feature-column/fcarc-pagerank) on PageRank.2011-08-06

2 Answers 2