Алгоритм BlockRank: использование компонентов двусвязности веб-графа для вычисления Google PageRank
Граф веб-ссылок имеет вложенные компоненты двусвязаности: подавляющее большинство гиперссылок связывают страницы на хосте с другими страницами того же хоста, но многие из них не связывают страницы в пределах
одного домена. Мы покажем, как можно использовать эту связь, чтобы ускорить вычисления Google PageRank 3-этапным алгоритмом при котором (1) локальный PageRank страниц для каждого хоста рассчитываются независимо, используя
связь ссылок этого хоста, (2) эти локальные PageRank затем анализируются касательно «важности» соответствующего хоста, и (3) затем выполняется стандартный алгоритма PageRank с использованием, в качестве исходного вектора,
взвешенной сети локального PageRank. Эмпирически, этот алгоритм в реальных условиях ускоряет вычисления PageRank в 2 раза. Кроме того, мы разрабатываем вариант данного алгоритма, который эффективно вычисляет множество
различных «персонализированных» PageRank, и вариант, который эффективно пересчитывает PageRank после обновлений узла.