Efficient PageRank approximation via graph aggregation

May combine two claims.

The experimental Web graph had 241 million host-to-host edges, 3.6% of the number of page-to-page links.

“with 241 million host-to-host edges (3.6% of the number of page-to-page links).”

May combine two claims.

The experimental Web graph contained over 1446 million pages and almost 6650 million links.

“Our experimental setup, presented in Section 4, exhibits similar ratios: we used a Webgraph containing over 1446 million pages with almost 6650 million links.”

Probably not a substantial claim: may not pass S3 (load-bearing). May combine two claims.

The sample contained 1298 pages distributed over the full range of PageRank values.

“The resulting sample contained 1298 pages distributed over the full range of PageRank values.”

• AssumptionRests on an assumption: PageRank values follow a power-law distribution, so the bulk of the population are pages with few or no inlinks.
• AssumptionRests on an assumption: Pages with low PageRank scores rarely appear as top ranking results for queries, so small fluctuations in their static scores are hardly noticed by search engine users.

May combine two claims.

Computing PageRank in this setting required 12.5 h, while computing the U-model scores took 5.8 h, a speedup factor of about 2.1.

“Computing PageRank in this setting required 12.5 h., while computing the U-model scores took 5.8 h.(a speedup factor of about 2.1).”

May combine two claims.

The graph has about 31 million unique hosts (just over 2% of pages) and 241 million host-to-host edges (3.6% of page-to-page links).

“The number of unique hosts in this graph is about 31 million (just over 2% of the number of pages), with 241 million host-to-host edges (3.6% of the number of page-to-page links).”

May combine two claims.

Most standardized residuals from the fit are very small, with more residuals close to zero than expected under a standard Gaussian distribution.

“Most of standardized residuals from the fit are very small.Indeed, there are more residuals close to zero than expected if the residuals are compared to a standard Gaussian distribution.”

May combine two claims.

The Spearman rank-order correlation between U-model and PageRank is 0.95, considerably higher than the Pearson correlation of 0.81.

“In fact, the Spearman rankorder correlation (Snedecor and Cochran, 1989) between U-model and PageRank is 0.95, considerably higher than the Pearson correlation of 0.81.”

• cites Snedecor and Cochran, 1989Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

Probably not a substantial claim: may not pass S3 (load-bearing).

The experiments use a Web-graph containing over 1446 million pages with almost 6650 million links, from an AltaVista crawl in September 2003.

“Our experiments are based on a Web-graph containing over 1446 million pages with almost 6650 million links, from a crawl of the Web conducted by AltaVista in September 2003.”

Probably not a substantial claim: may not pass S3 (load-bearing), S4 (based).

The model is much less sensitive to changes in the internal organization of hosts.

“Our model is much less sensitive to changes in the internal organization of hosts, which might be an advantage.”

May combine two claims.

Ruhl et al. (2001) reported that in a 604 million page snapshot from August 2000, the host graph had 10.37 million hosts and 5540 million page links induced less than 263 million host-graph links, below 5% of the original number.

“They report that the number of hosts in that snapshot was merely 10.37 million.Furthermore, the 5540 million links between Web pages induced less than 263 million links (below 5% of the original number) in the host-graph.”

• cites Ruhl et al., 2001Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

Probably not a substantial claim: may not pass S2 (checkable), S3 (load-bearing).

Larger speedup factors are probably possible.

“implying that larger speedup factors are probably possible.”

Probably not a substantial claim: may not pass S3 (load-bearing), S4 (based).

Pages on a given host will generally be assigned different scores.

“Nevertheless, it ultimately still derives static scores with page granularity, that is, pages on a given host will generally be assigned different scores.”

May combine two claims.

The algorithm calculates a distribution at page granularity while performing eigenvector calculations at host granularity.

“We have thus managed to calculate a distribution in page-granularity while performing eigenvector calculations in host-granularity.”

May combine two claims.

Outlying points with large residuals tend to correspond to pages with large PageRank values, suggesting U-Model could be a less precise approximation of PageRank in the very high end of the scale.

“However, the outlying points (with large residuals) tend to correspond to pages with large PageRank values, suggesting that U-Model could be a less precise approximation of PageRank in the very high end of the scale.”

Classified as probably not a substantial claim.

In general, the alternative random walk is not mathematically equivalent to the original random walk.

“Note that in general, this alternative walk is not mathematically equivalent to the original random walk T.”

Classified as probably not a substantial claim.

Kamvar et al. (2003b) reported that in a crawl containing 70 million pages with over 600 million interconnecting links, more than 93% of the links connected same-host pages.

“Kamvar et al. (2003b) report that in a crawl containing 70 million pages with over 600 million interconnecting links, more than 93% of the links connected same-host pages.”

• cites Kamvar et al., 2003bNot matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

Probably not a substantial claim: may not pass S4 (based).

For many choices of the original walk, classes, and class distributions, the two random walks may result in very different stationary distributions.

“Furthermore, for many choices of T, H 1 , . . ., H m and π 1 , . . ., π m , the two random walks may result in very different stationary distributions.”

May combine two claims.

Same-host sources and destinations are indistinguishable in ST S, so iterations to find α can be carried out using m×m transition matrices and m-dimensional probability vectors.

“Therefore, same-host sources/destinations are indistinguishable and hence the iterations required to find a can be carried out using m × m transition matrices and m-dimensional probability vectors, whose columns correspond to the distinct hosts.”

May combine two claims.

The stationary distribution of the alternative walk can be derived from the principal eigenvector of an m by m stochastic matrix, which is generally less expensive than computing the principal eigenvector of the n by n stochastic matrix of the original walk.

“In what follows, we show that the stationary distribution of T can be derived from the principal eigenvector of a m × m stochastic matrix (recall that m is the number of classes), which is generally less expensive than computing the principal eigenvector of the n × n stochastic matrix T.”

May combine two claims.

For any irreducible, aperiodic n×n stochastic matrix T, both ST and ST S are irreducible and aperiodic and have uniquely defined positive normalized principal eigenvectors.

“Furthermore, for any irreducible, aperiodic n × n stochastic matrix T, both ST and ST S are also irreducible and aperiodic, and so both matrices have uniquely defined (positive, normalized) principal eigenvectors.”

• AssumptionThe authors state this as an assumption: The original page-to-page transition matrix T is irreducible and aperiodic.

May combine two claims.

Moving to smaller graphs such as the host graph may enable connectivity data to fit in the RAM of a single machine, so our algorithm will have to perform only two passes over the full list of links versus 25-40 passes for standard PageRank.

“Moving to smaller graphs such as the host graph may enable the connectivity data to once again fit in the RAM of a single machine.In such a case our algorithm will have to perform only two (inevitably slow) passes over the full list of links, versus 25-40 passes for standard PageRank.”

• AssumptionRests on an assumption: The standard power-iteration computation of PageRank converges in a few dozen iterations, and each iteration requires one pass over the complete list of links for the entire Web graph.

May combine two claims.

The power iterations part in our algorithm is linear in the number of links of the host-graph, which is typically much smaller (maybe by a factor of 20) than the number of links in the page-graph.

“The power iterations part in our algorithm is linear in the number of links of the host-graph, which typically is much smaller (maybe by a factor of 20), than the number of links in the page-graph.”

Classified as probably not a substantial claim. May combine two claims.

The PageRank computations used robust and optimized infrastructure of the connectivity server, while the modified algorithm was written in an ad-hoc, non-optimized manner.

“It should be noted that the PageRank computations use the robust and optimized infrastructure of the connectivity server, while our modified algorithm was written in an ad-hoc, non-optimized manner.”

May combine two claims.

In BlockRank, teleportations between hosts are uniform over all hosts, whereas in our approach teleportations land on each host in proportion to the number of pages on that host.

“The differences between v and the appropriate γ flavor concern the definition of teleportations in the random walk over the hosts: in BlockRank, teleportations between hosts are uniform over all hosts, whereas in our approach, it follows from Eq. ( 2) that teleportations land on each host in proportion to the number of pages on that host.”

• cites Kamvar et al. (2003b)Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

Probably not a substantial claim: may not pass S3 (load-bearing), S4 (based).

The method can be defined in terms of any equivalence relation that partitions the set of Web pages.

“One should note, however, that the method can be defined in terms of any equivalence relation that partitions the set of Web pages.”

Classified as probably not a substantial claim.

The method changes the semantics of random browsing on the Web by decoupling intra-host and inter-host steps.

“As defined in Section 3, our method changes the semantics of random browsing on the Web by decoupling intra-host and inter-host steps.”

May combine two claims.

Our model is almost insensitive to changes in the internal organization of hosts; a reorganization that modifies linkage patterns between pages on a host might change relative ranking of those pages but will have much less effect on pages outside the host, since the weight of the host is uniformly distributed over all its pages.

“One possible advantage of our model is that it is almost insensitive to changes in the internal organization of hosts.A reorganization that modifies the linkage patterns between the pages on a given host might change the relative ranking of these pages, but will have much less effect on pages outside the host, since the”