This site is devoted to mathematics and its applications. Created and run by Peter Saveliev.

# PageRank: testing

## An example

If $E$ is the set of edges of a directed graph and $N$ the total number of nodes in the graph then the PageRank of the $i$-th node is: $$P_i=(1-\epsilon )\sum _{(i,j)\in E}\frac{P_j}{d_j}+\frac{\epsilon }{N},$$ where $\epsilon$ is the damping coefficient and $d_j$ is the degree of node $j$.

Suppose we have a circular directed graph as in the picture on the right. From the symmetry it follows that the page ranks of all the nodes should be equal. Since the PageRanks should add up to $1$, it follows that $$P_i=1/4,i=1,2,3,4.$$

Now, suppose whoever controls node 4 changes the link from 1 to 2. Then we have the second graph on the right. Then $$P_1=(1-\epsilon )[0]+\epsilon /4,$$ $$P_2=(1-\epsilon )[P_4+P_1]+\epsilon /4,$$ $$P_3=(1-\epsilon )[P_2]+\epsilon /4,$$ $$P_4=(1-\epsilon )[P_3]+\epsilon /4.$$ The result is a system of linear equations. One can plug this into Mathematica or similar algebra system to find the the exact solution. However, even without it we know that $$P_2>\epsilon /4=P_1.$$ So, someone who controls nodes 4 can move node 2 above node 1 at will.

To experiment with ideas like this I've created this little spreadsheet. The formula comes from the original Page/Brin paper from 1998.

Suppose we have these ten "pages": A, B, ..., J. They are listed in the table as both rows and columns. The links are the entries in the table.

First we suppose that they link to each other consecutively: A → B → C → ... → J.

The PageRank scores, as well as the positions, of the pages are computed and displayed on the right. The scores for A, ..., J are increasing in the obvious way: from 0 to .1. In particular, F is #5.

Next, suppose F adds a link to A: F → A. You can see that 1 has appeared in the first column of the table:

Now, suddenly F ranks first!