Algorithms For Dummies

  Getting the Right Web page 

     217

The Python code creates the function 

initialize_PageRank

 that extracts both 

the transition matrix and the initial vector of default PageRank scores.

G, p = initialize_PageRank(Graph_A)

print (G)

[[ 0.     0.     0.33333333  0.     0.     0.5 ]

 [ 0.5    0.     0.33333333  0.     0.     0.  ]

 [ 0.5    1.     0.          0.     0.     0.  ]

 [ 0.     0.     0.33333333  0.     0.5    0.  ]

 [ 0.     0.     0.          0.5    0.     0.5 ]

 [ 0.     0.     0.          0.5    0.5    0.  ]]

The printed transition matrix 

G

 represents the transition matrix of the network 

described  in  Figure  11-1.  Each  column  represents  a  node  in  the  sequence  1 

through 6. For instance, the third column represents node 3. Each row in the col-

umn shows the connections with other nodes (outbound links toward nodes 1, 2, 

and 4) and values that define the probability of a random surfer using any of the 

outbound links (that is, 1/3, 1/3, 1/3).

The diagonal of the matrix is always zero unless a page has an outbound link 

toward itself (it is a possibility).

The matrix contains more zeros than values. This is also true in reality because 

estimates show that each site has only ten outbound links on average. Because 

billions of sites exist, the nonzero values in a transition matrix representing the 

web are minimal. In this case, it’s helpful to use a data structure such as an 

 adjacency list (explained in Chapter 8) to represent data without wasting disk or 

memory space with zero values:

from scipy import sparse

sG = sparse.csr_matrix(G)

print (sG)

  (0, 2)   0.333333333333

  (0, 5)   0.5

  (1, 0)   0.5

  (1, 2)   0.333333333333

  (2, 0)   0.5

  (2, 1)   1.0

  (3, 2)   0.333333333333

  (3, 4)   0.5

  (4, 3)   0.5

  (4, 5)   0.5

  (5, 3)   0.5

  (5, 4)   0.5

---

218