Разработка системы моделирования поисковой оптимизации веб-сайта

курсовая работа

2.1 Графы состояний рейтинга сайта, виды состояний, вероятности состояний

Для описания процессов изменения состояния популярности сайта мы будем пользоваться теорией случайных процессов, а точнее Марковскими процессами с дискретными состояниями.

Строго говоря, в природе не существует совершенно не случайных, в точности детерминированных процессов, но есть процессы, на ход которых случайные факторы влияют так слабо, что при изучении явления ими можно пренебречь. Существуют и такие процессы, где случайность играет основную роль. Между этими двумя крайними случаями лежит целый спектр процессов, в которых случайность играет большую или меньшую роль. Учитывать (или не учитывать) случайность процесса зависит также и от того, какую практическую задачу мы решаем.

Случайный процесс, протекающий в любой физической системе S, представляет собой случайные переходы системы из состояния в состояние. Состояние системы может быть охарактеризовано с помощью каких-то численных переменных; в простейшем случае - одной, а в более сложных - нескольких.

Рассмотрим физическую систему S, в которой протекает случайный процесс с дискретными состояниями:

s1, s2, … si, …,(2.1.1)

число которых конечно (или счетно). Состояния si, s2,... могут быть качественными (т. е. описываться словами) или же каждое из них характеризуется случайной величиной (либо случайным вектором).

Прежде всего, рассмотрим множество состояний (2.1.1) с точки зрения его структуры - возможности системы S переходить из состояния si в данное состояние sj непосредственно или через другие состояния. Для этого удобно пользоваться наглядной схемой, так называемым графом состояний.

Имеется две основные разновидности графов: неориентированные и ориентированные. Неориентированный граф - совокупность точек (вершин графа) с соединяющими некоторые из них отрезками (ребрами графа). Ориентированный граф - это совокупность точек (вершин) с соединяющими некоторые из них ориентированными отрезками (стрелками).

В дальнейшем мы будем пользоваться только ориентированными графами.

Вершины графа будут соответствовать состояниям системы. Вершину будем изображать прямоугольником, в который вписано обозначение состояния; стрелка, ведущая из вершины si в вершину sj, будет обозначать возможность перехода системы S из состояния si в состояние sj непосредственно, минуя другие состояния. Стрелки графа могут изображаться не только прямолинейными, но и криволинейными отрезками.

Если привязывать вышеназванную систему к поисковой оптимизации сайта, то можно получить следующую картину: система S будет представлять собой собственно сайт, а его возможные состояния s1, s2, … si, … это нахождение сайта в каком-либо «топе популярности», например топ 5, топ 10, топ 50 и т.д. Граф состояний показан на рисунке 2.1.1. Будем считать далее, что переход системы S из состояния si в состояние sj осуществляется мгновенно и что в любой момент времени система может находиться только в одном из своих состояний.

Размещено на http://www.allbest.ru/

Рис. 2.1

Проведем некоторую необходимую для дальнейшего классификацию состояний.

Состояние si называется источником, если система S может выйти из этого состояния, но попасть в него обратно уже не может, т.е. на графе состояний в состояние si не ведет ни одна стрелка. На рисунке 2.2 состояния s1 и s2 являются источниками.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Рис. 2.2 Рис. 2.3

Состояние si называется концевым (или поглощающим), если система S может попасть в это состояние, но выйти из него уже не может. Для графа состояний это означает, что из состояния si не ведет ни одна стрелка (для графа, изображенного на рис. 2.3, состояния s4 и s7 - поглощающие; для графа состояний сайта, изображенного на рис. 2.1, поглощающих состояний нет; у графа, построенного на рис. 2.2, поглощающие состояния также отсутствуют).

Если система S может непосредственно перейти из состояния si в состояние sj, то состояние sj называется соседним по отношению к состоянию si. Если система S может непосредственно перейти из состояния si в состояние sj и из состояния sj в состояние si, то состояния si, sj называются соседними. На графе состояний нашего сайта все состояния можно считать соседними, т.к. сайт может переместиться, например, из «топа 50» и в «топ 10», и в «топ 5» или стать непопулярным сайтом.

Состояние si называется транзитивным, если система S может войти в это состояние и выйти из него, т. е. на графе состояний есть хотя бы одна стрелка, ведущая в si, и хотя бы одна стрелка, ведущая из si. На рис. 2.1 все состояния являются транзитивными; на рис. 2.3 все состояния, кроме источников s1, s5 и поглощающих s4, s7, транзитивны.

При анализе случайных процессов, протекающих в системах с дискретными состояниями, важную роль играют вероятности состояний.

Обозначим S(t) состояние системы S в момент t.

Вероятностью i-го состояния в момент t называется вероятность события, состоящего в том, что в момент t система S будет в состоянии si; обозначим ее pi(t):

pi(t) = P{S (t) = si},(2.1.2)

где S(t) - случайное состояние системы S в момент t.

Очевидно, что для системы с дискретными состояниями s1, s2,.... si,... в любой момент t сумма вероятностей состояний равна единице:

(2.1.3)

как сумма вероятностей полной группы несовместных событий.

В ряде задач практики нас интересует так называемый установившийся или стационарный режим работы системы, который в ней устанавливается, когда от начала процесса прошло достаточно большое время.

В некоторых случайных процессах по прошествии достаточно большого времени устанавливается стационарный режим, во время которого состояния системы хотя и меняются случайным образом, но их вероятности pi(t) (i=1,2,...) остаются постоянными.

Обозначим эти постоянные вероятности рi:

(2.1.4)

Вероятности pi (i=l, 2,...), если они существуют, называются финальными (предельными) вероятностями состояний. Финальную вероятность pi можно истолковать как среднюю долю времени, которую в стационарном режиме проводит система S в состоянии si.

Введем очень важное для дальнейшего понятие марковского случайного процесса.

Случайный процесс, протекающий в системе S с дискретными состояниями s1, s2,..., si,..., называется марковским, если для любого момента времени t0 вероятность каждого из состояний системы в будущем (при t > t0) зависит только от ее состояния в настоящем (при t = t0) и не зависит от того, когда и как она пришла в это состояние; т. е. не зависит от ее поведения в прошлом (при t<t0). Не надо понимать марковское свойство случайного процесса как полную независимость «будущего» от «прошлого»; нет, в общем случае «будущее» зависит от «настоящего», т. е. вероятности pi(t) при t > t0 зависят от того, в каком состоянии si находится система в настоящем (при t = t0); само же это «настоящее» зависит от «прошлого», от того, как вела себя система S при t<t0. Это можно сформулировать следующим образом: для марковского случайного процесса «будущее» зависит от «прошлого» только через «настоящее». При фиксированном «настоящем» условные вероятности всех состояний системы в «будущем» не зависят от предыстории процесса, т.е. от того, когда и как система S к моменту t0 пришла в состояние si.

Марковские процессы с дискретными состояниями и дискретным временем имеют сравнительно мало приложений, так как довольно редко на практике моменты возможных переходов системы S из состояния в состояние заранее известны и фиксированы. Гораздо типичнее случай, когда переходы системы из состояния в состояние могут происходить не в фиксированные моменты t0, t1, t2…, а в случайные моменты.

На практике довольно редко встречаются марковские процессы в чистом виде, но довольно часто - процессы, которые с тем или иным приближением можно считать марковскими.

Для дальнейших рассуждений нам нужно такие понятия, как поток событий, интенсивность потока и поток событий без последействия. Потоком событий называется последовательность однородных событий, появляющихся одно за другим в случайные моменты времени. Поток событий называется потоком без последействия, если вероятность попадания любого числа событий на один из участков времени не зависит от того, сколько их попало на другие.

Интенсивностью (плотностью) потока событий в момент t называется следующая величина:

программа ранжирование сайт скрипт

,(2.1.5)

где X(t,?t) - случайное число событий, попадающих на элементарный участок (t, t+?t);

M - математическое ожидание.

Физический смысл интенсивности л(t) потока событий - это среднее число событий, приходящееся на единицу времени, для элементарного участка ?t, примыкающего к t.

Нам будет удобно считать, что переходы («перескоки») системы S из состояния в состояние происходят под воздействием каких-то потоков событий. Как только произошло первое после момента t0 событие, переход из состояния в состояние осуществляется (последующие события потока не учитываются никак). Отсутствие последействия в пуассоновском потоке позволит нам при фиксированном настоящем (состояние si системы в момент t) не заботиться о том, когда и как система оказалась в этом состоянии. Вероятность перехода системы S из состояния si, в котором она находилась в момент t, в состояние sj за элементарный промежуток времени ?t, непосредственно примыкающий к t, приближенно равна лij(t)?t, где лij(t)- интенсивность пуассоновского потока событий, переводящего систему из si в sj. Если все потоки событий, переводящие систему из состояния в состояние,- пуассоновские и независимые, то процесс, протекающий в системе S, будет марковским. Если известны все интенсивности пуассоновских потоков событий, переводящих систему из состояния в состояние, то можно составить дифференциальные уравнения для вероятностей состояний. Об этом и пойдёт речь в следующей части.

Делись добром ;)