doc_z - 9:00 pm on Nov 17, 2003 (gmt 0)

ciml,

the question about the difference in PR between case I and II is quite complicate. It strongly depends on the iteration scheme as well as the number of iterations which are performed to compute the PR of the dangling pages (in case II). Consider, for example, a chain of pages (X1, X2, X3, ...), where the first page is linked to the second pages which is link to the third page and so on. The last page is a dead end. In case II, all these pages have to be taken out of the calculation. Thus, it takes n iterations where the dangling pages are included (in case II) until pages Xn get a non-zero PR if the simple Jacobi iteration is used. (I never had any problems whith such chains of pages. Thus I would conclude that Google is either using a different iteration schemes or computes PR according to case I. I would guess they are doing both.)

Also, the difference between case I and II depends on the question if PR of the non-dangling pages is fixed during the final PR computation or not. The first case is much faster, but less accurate.

Of course, for a global view the difference betwenn case I and II might be not important. However, for the own page/site the difference can be significant. Also, pages can be even affected if they are not in the neighbourhood of dangling pages.

The reason that Kamvar et. al. still remove dangling pages is that they still consider the PR calculation as the determination of eigen vectors. This requires a non zero determinante for the transition matrix, i.e. pages which have at least one outgoing links. They claim that this these technique is accelerating the compatation. However, there are well-known algorithms for sparse matrices which are faster.