SEOgramota.Ru блог о SEO, продвижении, заработке в интернете

Учите матчасть. Поскольку PageRank, имеет отношение к вероятности просмотра страниц, то для лучшего понимания, стоит обратиться к такому разделу теории случайных процессов как теории Марковских процессов. Под Марковским процессом подразумевается процесс, для которого вероятность находиться в данном состоянии, на данном этапе процесса можно вывести из информации о предшествующем состоянии. Цепью Маркова называется Марковский процесс, для которого каждое конкретное состояние зависит только от непосредственно предыдущего. Число состояний цепи Маркова конечно, а вероятности перехода из одного состояния в другое не зависят от времени. Следуя из определения можно сказать, что рассматриваемый нами процесс поведения абстрактного пользователя сети является Марковским, и даже более того, является Цепью Маркова. Теперь рассмотрим, какие условия определяют цепь Маркова: Во-первых, у цепи имеется матрица вероятностей перехода:

  (3). где pij – вероятность перехода из состояния i в состояние j за один шаг процесса. Матрица (3) обладает следующими свойствами:   а) ∑pij = 1 j=1…N.  (свойство, вытекающее из замкнутости системы);   б) pij ³ 0 ” i, j. Во-вторых, у цепи Маркова имеется вектор начальных вероятностей, который описывает начальное состояние системы: P(0) = < P01, P02,..,P0n >  (4) Обозначим шаги (этапы) процесса за t = 0, 1,….. Если P(0) это вектор начальных вероятностей, то P(t) – это вероятностный вектор на шаге t. Значение P(t+1) зависит от P(t). Формула расчета в матричном виде выглядит следующим образом: P(t+1) = P(t) ∙P  (5). Отсюда следует, что: P(t) = P(0) ∙Pt   (6). В теории цепей Маркова показано, что в пределе, при t стремящемся к бесконечности, вероятности состояний стремятся к определенным предельным значениям, которые удовлетворяют соотношению: P(*)=P(*)∙P  (7). Из (7) становится очевидным, следующее важное свойство предельных векторов вероятностей P(*). Заключается оно в том, что P(*) является единственным и не зависит от вектора начальных вероятностей P(0) и определяются только матрицей вероятностей перехода. Теперь рассмотрим применение данной теории для системы из нашего примера (Рис. 1. Часть I). Матрица вероятностей перехода будет выглядеть следующим образом, т. е. также как и матрица при расчете PageRank матричным способом:

(9)  Первая строка матрицы свидетельствует о следующем: со страницы A можно перейти на B, C, и D. Вероятность того, что после A пользователь выберет C равна 1/3. Вероятность выбора D или C тоже равна 1/3. Вторая строка значит, что со страницы B можно попасть только на A, вероятность этого перехода равна 1. Третья строка – с C можно попасть только на A, вероятность перехода равна 1. Четвертая строка – с D можно попасть только на  B, вероятность перехода равна 1. Для нашей системы вектор начальных вероятностей выглядит следующим образом (поскольку в нашей сети четыре страницы и пользователь может оказаться на люьбой из них с одинаковой вероятностью): P(0) = < 1/4, 1/4, 1/4, 1/4>. Для расчета вектора P(1) применим формулу (5), т. е. P(0) умножим на матрицу вероятностей перехода. Получим P(1) = <0,5; 0,3333; 0,0833; 0,0833>. Для вектора P(2) формула (5) имеет следующий вид: P(2) = P(1) ∙P. После расчета получаем значения P(2) = <0,4167; 0,25; 0,167; 0,167>. Рассчитывая значения P(t) по формуле (5) мы найдем t, для которого выполняется равенство (7). Т. е. мы рассчитаем значение предельного вектора вероятностей P(*), который не зависит от вектора начальных вероятностей P(0) и определяется только матрицей вероятностей перехода. В нашем случае P(*) = <0,429; 0,286; 0,143; 0,143>. Таким образом, после достаточно большого количества переходов со страницы на страницу уже не имеет значения с какой страницы пользователь начал просмотр, поскольку в результате он окажется на странице A с вероятностью 0,429, на странице B с вероятностью 0,286, на страницах C и D с вероятностями 0,143 (или можно сказать, что 42% пользователей будут на странице A, 29% будут на странице B и на страницах C и D будет по 14% посетителей). Теперь с полученным вектором P(*)  произведем следующие действия: 0.85∙4P(*) + (1-0,85) Проведем расчеты: Для А:  0,85∙4∙0,429 + 0,15 = 1,607. Для B:  0,85∙4∙0,286 + 0,15 = 1,12. Для C:  0,85∙4∙0,143 + 0,15 = 0,635. Для D: 0,85∙4∙0,143 + 0,15 = 0,635. Получается что, рассчитав предельный вектор вероятностей P(*), умножив его на единичный вектор, умноженный на 4d, и прибавив к нему единичный вектор, умноженный на (1-d), мы получили значении практически равные значениям PR, рассчитанным в первой части статьи. Сравним два алгоритма (расчет PageRank матричным способом и нахождение предельного вектора P(*) Цепи Маркова) в общем случае. Различие заключается лишь в том, что при расчете значений PR за начальный берется единичный вектор и вводится зависимость PR от коэффициента затухания.

А  для расчета P(*) начальный вектор состоит из значений 1/N, где N – количество страниц. Именно поэтому, умножив полученный вектор P(*) на N и d, а также прибавив (1-d) мы получили значения близкие к значениям PR. Статья любезно предоставлена mediacraft. ru