Шишигин Михаил Иванович : другие произведения.

Особенности Page Rank технологии, обеспечивающей лидирующее положение крупномасштабной гипертекстовой поисковой системе Google (Часть 1)

Самиздат: [Регистрация] [Найти] [Рейтинги] [Обсуждения] [Новинки] [Обзоры] [Помощь|Техвопросы]
Ссылки:


Оценка: 1.00*2  Ваша оценка:
  • Аннотация:
    Математические и информационные аспекты PR технологии


Особенности Page Rank технологии, обеспечивающей лидирующее положение крупномасштабной гипертекстовой поисковой системе Google

  
  

(Математические и информационные аспекты PR технологии)

  
  
  
   На ниве Интернета трудится многочисленный отряд поисковых роботов. Задача этих поисковых роботов весьма непростая - обработать огромные пласты информации, размещенной в Сети, и сделать эту информацию доступной многочисленным пользователям Интернета.
   Безусловно эта задача чрезвычайно усложняется по причине лавинообразного накопления сетевых документов, веб-сайтов.
   Особое признание у пользователей Сети заслужил поисковый робот Googlebot, действительно предоставляющий возможность осуществлять поиск в Интернете, обеспечивая обширный обхват документов Международной Сети, а не какой-то её отдельной части.
   Цель статьи - пояснить математические и информационные аспекты Page Rank технологии, позволяющие поисковому роботу Googlebot успешно обрабатывать документы в Сети, веб-сайты.
   Следует отметить, что теоретическая концепция Page Rank технологии веб-сайт представляет в виде направленного мультиграфа, вершинами которого являются страницы.
  
   Робот поисковой системы исследует сайт, отслеживает связи между страницами и формирует матрицу связей, которая содержит всю информацию о топологии веб-сайта
   Запишем элементы матрицы связей || akm ||, (k=1,...,n), (m = 1,...,n).
   Поясним обозначения.
  
   T1,T2,...,Tn - обозначения страниц сайта (n - количество страниц сайта)
  
   Компоненты akm, находящиеся в матрице связей на пересечении k-ой строки и m-ого столбца, определяет количество связей, идущих от Tk страницы на страницу Tm (количество ссылок на страницу Tm от страницы Tk)
  
   Cr(Tk) - общее количество ссылок, исходящих от страницы Tk
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  

T1

T2

  
  

Tn

  
  
  
  
  
  

T1

a 11

a 12

...

...

a 1n

Cr(T1)

  
  
  
  
  

T2

a 21

a 22

...

...

a 2n

Cr(T2)

  
  
  
  
  
   .
   .
   .
   .
   .
   .
  
  
   .
   .
  
  
  
  
  
   .
   .
   .
   .
   .
   .
  
  
   .
   .
  
  
  
  
  

Tn

a n1

a n2

...

...

a nn

Cr(Tn)

  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
   В математическом смысле вычислительная схема PR представляет собой рекурсивную процедуру, особенностью которой является то, что выходные значения, полученные на определенном этапе итерации, становятся входными для последующей итерации.
   Запишем уравнения рекурсивной вычислительной схемы:
  
   ...............................n
   PR I+1 (Tm) = (1-d) + d *Sakm PR I (Tk)/ Cr(Tk),
   ..............................k=1
   где
   PR I+1 (Tm) - Page Rank страницы Tmна (I+1) - ой итерации (оценочное значение страницы Tm (m = 1,...,n)
  
   PR I (Tk) - Page Rank страницы Tk на I - ой итерации (оценочное значение страницы Tk (k = 1,...,n)
  
   Cr(Tk) - общее количество ссылок, исходящих от страницы Tk,
  
   Cm(Tk) = akm - количество индивидуальных ссылок, исходящих от страницы Tk на страницу Tm (k=1,...,n), (m=1,...,n).
   d - демпфирующий коэффициент (обычно 0,85),
   (1 - d) - нормировочный коэффициент,
   n - количество страниц в сайте
  
   Сходимость рекурсивной вычислительной схемы обеспечивается простым условием:

d < 1.

   Важно то, что какие бы ни были стартовые значения (будем задавать стартовые значения 1) рекурсивная процедура, после выполнения конечного числа итеративных циклов, вычислит предельные значения. Для предельных оценочных величин характерно то, что эти величины не изменяются при дальнейших итерациях, и итеративный процесс на этом завершается.
  
Оценка: 1.00*2  Ваша оценка:

Связаться с программистом сайта.

Новые книги авторов СИ, вышедшие из печати:
О.Болдырева "Крадуш. Чужие души" М.Николаев "Вторжение на Землю"

Как попасть в этoт список

Кожевенное мастерство | Сайт "Художники" | Доска об'явлений "Книги"