PageRank (cont)
V = # pages in Web, E = # hyperlinks in Web
Costs for computing PageRank for each representation:
| Representation | |
linkExists(v,w) | |
Cost |
| Adjacency matrix | |
edge[v][w] | |
1 |
| Adjacency lists | |
inLL(list[v],w) | |
≅ E/V |
Not feasible …
- adjacency matrix … V ≅ 1014 ⇒ matrix has 1028 cells
- adjacency list … V lists, each with ≅10 hyperlinks ⇒ 1015 list nodes
So how to really do it?
|
![[prev]](icon/prev.gif){kind=icon}
![[next]](icon/next.gif){kind=icon}