3 ms·

What does G signify? I'm a bit confused as to why taking its eigenvector gives you the pagerank vector.

• jamessb 13y ago
  In essence, pagerank sorts pages by the probability that you'd arrive at them by randomly following links form other pages. G is a matrix of transition probabilities - each entry is the probability of moving directly from a particular page to another particular page. It is composed of 3 terms: - the hyperlink matrix: the probabilities obtained by assuming a user randomly selects a link to follow from their current page, with an equal probability for each - the dangling nodes matrix: to ensure that it is possible to leave every page, this adds an equal probability for moving from a page with no outgoing links to every other page - the matrix U of all ones: this provides G with 2 desirable properties, by ensuring it is both irreducible/strongly-connected and aperiodic. It does this by making it possible to move from any page to any other page, with some small probability (exactly how small is determined by the damping factor d). The pagerank vector represents the equilibrium probability distribution - in other words, the probability of being on a particular page after starting on a random page then spending a long time randomly moving between pages according to the probabilities in G. Now, if at a given time your probability of being on each page is given by some vector X, the probability of being on each page after one random move is the transition matrix multiplied by X. The equilibrium probability vector thus has the property that it is unchanged by multiplication by the transition matrix - it is therefore an eigenvector of the transition matrix, with an eigenvalue of 1. Edit: After typing this, I see that explanatory hypertext appears when you mouse over the blue words.