Algorithms For Dummies

 

   

  PART 3 

 Exploring the World of Graphs

This example has just 12 links out of 30 possible (without counting links to self, 

which is the current site). Another particular aspect of the transition matrix to 

note is that if you sum the columns, the result should be 1.0. If it is a value less 

than  1.0,  the  matrix  is  substochastic (which means that the matrix data isn’t 

 representing probabilities properly because probabilities should sum to 1.0) and 

cannot work perfectly with PageRank estimations.

Accompanying 

G

 is a vector 

p

, the initial estimate of the total PageRank score, 

equally distributed among the nodes. In this example, because the total PageRank 

is  1.0  (the  probability  of  a  random  surfer  being  in  the  network,  which  is 

100  percent), it’s distributed as 1/6 among the six nodes:

print(p)

[ 0.16666667  0.16666667  0.16666667  0.16666667

  0.16666667  0.16666667]

To estimate the PageRank, take the initial estimate for a node in the vector 

p

, 

multiply it by the corresponding column in the transition matrix, and determine 

how much of its PageRank (its authority) transfers to other nodes. Repeat for all 

nodes and you’ll know how PageRank transfers between nodes because of the 

network structure. You can achieve this computation using a matrix-vector 

multiplication:

print(np.dot(G,p))

[ 0.13888889  0.13888889  0.25        0.13888889

  0.16666667  0.16666667]

After  the  first  matrix-vector  multiplication,  you  obtain  another  estimate  of 

 PageRank that you use for redistribution among the nodes. By redistributing mul-

tiple times, the PageRank estimate stabilizes (results won’t change), and you’ll 

have the score you need. Using a transition matrix containing probabilities and 

estimation by successive approximation using matrix-vector multiplication 

obtains the same results as a computer simulation with a random surfer:

def PageRank_naive(graph, iters = 50):

    G, p = initialize_PageRank(graph)

    for i in range(iters):

        p = np.dot(G,p)

    return np.round(p,3)

print(PageRank_naive(Graph_A))

[ 0.154  0.154  0.231  0.154  0.154  0.154]

---

CHAPTER 11