Network Graphs and the PageRank Algorithm

 The PageRank algorithm is by Google and used to rank certain webpages. Matrices represent network graphs.  

Adjacency matrixes describes the topology of the connections in the particular network. We put a “1” in the matrix if there is a connection from the column to that row. Node 5 to Node 4 represents “From column 5 to row 4”.

A transition probability matrix is where the columns will sum to 1. A transition probability matrix predicts the “Paths that might be taken using a network”.

This sort of behavior is known as a Markov Chain, where the next state depends solely on the current state.

1.      Start at Node 1, assign p0 to [1 0 0 0 0]T

2.      A is the matrix. P1 = A  * P0, P2 = A * P1, and the resulting matrix is the chance of staying in a particular column state

The following print will illustrate the PageRank Algorithm

It turns out that the Eigenvector of Q ranks pages.

 

Q is column stochastic, because the columns of the Matrix Q all sum to 1. Its largest eigenvalue is 1 and the corresponding eigenvector has all positive entries, and the sum of all Pi = 1.  P is a distribution on where to spend the time after going through the node long enough, after many, many, MANY iterations.