[ЗВУК] Давайте теперь обсудим, для чего нужны случайные блуждания. Оказывается, что у них есть много разных применений. Давайте обсудим несколько примеров. Во-первых, задачи ранжирования — тут, оказывается полезно случайное блуждание. И есть такой известный алгоритм ранжирования веб-страниц PageRank. Как он примерно работает? Он присваивает каждой странице число в соответствии с её важностью. И что он делает? Он рассматривает граф, в котором страницы соединены ребром, ориентированным, если есть ссылка с одной страницы на другую. И по сути, мы вычисляем для каждой страницы вероятность того, что мы её посетим при последовательных случайных переходах по ссылкам. То есть по сути, мы моделируем такую ситуацию, что у нас есть пользователь, который переходит по ссылкам случайным образом, и мы смотрим, насколько вероятно, что он попадёт на ту или иную страницу. В основе этого подхода — случайные блуждания. Другой пример: мы можем использовать случайные блуждания, чтобы анализировать окрестности объектов в графах. Например, это может быть полезно для задачи кластеризации, когда мы хотим находить похожие вершины и объединять их в некоторые группы. Что мы можем делать? Мы можем запускать много случайных блужданий из одной вершины, обычно коротких, и дальше можем смотреть на список вершин, в которых они заканчиваются. И мы можем для разных вершин сравнивать эти списки. Если они похожи, то значит, вершины похожи друг на друга — так мы можем сравнивать вершины по похожести. Это оказывается эффективнее, чем просто проанализировать полностью все окрестности вершин — такой метод эффективней. Давайте ещё один пример рассмотрим — это поиск близких вершин. Если у нас есть граф, то у нас есть понятие близости. Близкие вершины — это те, в которые есть короткий путь из одной в другую. То есть если у нас есть одна вершина, то близкие к ней — это те, в которые есть короткий путь. Но мы можем рассматривать другой тип близости. Давайте рассмотрим такой: насколько быстро случайные блуждания проходят из одной вершины в другую (в среднем, конечно). Вершины могут быть далеки в обычном смысле, то есть они могут быть далеко друг от друга в графе, но при этом если у вершин похожие окрестности, то случайное блуждание может заканчиваться быстро — оно выходит по этой окрестности и приходит на вторую вершину. Давайте рассмотрим пример. У нас есть вершина A и есть вершина E, которая в каком-то смысле близка к вершине A. Видно, что мы, скорее всего, попадём в вершину E из A раньше, чем в G. Ну, даже на первом шаге мы с вероятностью в 3/4 пойдём направо и только с вероятностью 1/4 пойдём в сторону вершины G, так что видно, что, скорее всего, мы в E придём раньше, чем в G. Что это позволяет нам делать? Это позволяет предсказывать, какие вершины близки в графе, а значит, может быть, их стоит в графе соединить. Ну, а это как раз — задача, которую мы обсуждали. Давайте теперь это всё формализуем — давайте формализуем меру, которую мы только что обсудили. Пусть у нас в графе есть две вершины u и v, и тогда моментом достижения вершины v из вершины u называется ожидаемое число ходов, то есть среднее число ходов случайного блуждания, стартующего из вершины u до его попадания в вершину v. То есть мы запускаем случайное блуждание из вершины u и ждём, пока оно попадёт в v. Матожидание этой величины мы и называем моментом достижения вершины v из вершины u. Эта величина характеризует, насколько близка вершина v к вершине u. Но у неё есть один минус: случайное блуждание может в принципе продолжаться бесконечно долго и не приходить в вершину v. Вероятность этого не очень высокая, если граф связен, то тем не менее, это возможно. Это означает, что эту величину может быть не очень удобно вычислять и не очень удобно работать, в общем, у неё есть такого рода минусы и с ней неудобно работать. Для этого мы рассмотрим некоторую модификацию этого определения. Мы скорректируем определение и заведём T-усечённый момент достижения (здесь T — это некоторое число). T-усечённый момент достижения вершины v из вершины u — это ожидаемое число ходов случайного блуждания длины T, стартующего из вершины u, до его попадания в вершину v. То есть мы делаем T ходов, и если попали в вершину v раньше, то у нас величина — это количество ходов до вершины v, а иначе у нас величина — это количество ходов во всём блуждании, это просто T. То есть если блуждание не попадает в вершину v за T ходов, то мы прерываем блуждание, и у нас сделано T ходов. И теперь какая от этого польза? Блуждание у нас теперь всегда конечно. Мы сделаем не больше, чем T ходов. Не просто конечно, но даже известно, сколько ходов у нас будет максимум, мы можем это регулировать, выбирая разные T. Давайте рассмотрим пример. Пусть мы хотим посчитать усечённый момент достижения из вершины A до вершины E для трёх ходов, то есть T у нас равно трём. Давайте посмотрим. На первом шаге с вероятностью 3/4 мы попадём в одну из вершин B, C и D (вот, есть три таких соседа: B, C и D, и с вероятностью 3/4 мы придём в них). И тогда на втором шаге мы попадём с вероятностью 1/2 в вершину E. В любом из этих случаев у нас два ребра — с вероятностью 1/2 мы переходим дальше в вершину E. Во всех остальных случаях, если мы этого не сделали (то есть либо мы не пошли в B, C и D на первом шаге, либо мы не пошли в E на втором шаге), нам придётся сделать три шага. Меньше, чем за три шага, мы до E уже не дойдём. Поэтому наши блуждания закончатся через три шага. А за два шага мы дойдём с вероятностью 3/4 * 1/2, то есть 3/8. И получается, что среднее число шагов с вероятностью 3/8 равно двум, с вероятностью оставшейся 5/8 оно равно трём (мы делаем только три шага). Считаем матожидание по определению, получается 21/8 или 2,625 — вот такое получается среднее число шагов до достижения вершины E. Хорошо. Эта величина несколько хуже характеризует близость вершин, потому что мы обрываем случайное блуждание, и она не такая точная, но, с другой стороны, с ней гораздо удобнее работать, и, опять же, можно регулировать длину блуждания. И у неё есть ещё такая особенность — эта величина несимметрична. То есть если мы посмотрим момент достижения из v в u, а также момент достижения из u в v, они могут быть существенно разными. Давайте посмотрим на пример. Пусть у нас теперь длина блуждания — 5, вот такой граф, и мы хотим посчитать момент из A в B. Ну, хорошо. Мы можем попасть за один шаг в вершину B, и вероятность этого — 1/5, а с вероятностью 4/5 мы попадём в какую-то другую вершину. На втором шаге всё предопределено — на втором шаге мы просто вернёмся в A, то есть с вероятностью в 4/5 мы за два шага вернёмся обратно в A. Дальше на третьем шаге вероятность попасть в B — снова 1/5, то есть если мы на втором шаге попали в вершину A, то вероятность перейти в вершину B — 1/5, и получается, что вероятность попасть в B за три шага — это 4/5 * 1/5 = 4/25. Во всех остальных случаях придётся делать пять шагов, и дальше уже неважно, попали мы в B через пять шагов или нет — в любом случае длина блуждания будет 5. Поэтому средняя величина у нас такая: у нас длина блуждания 1 с вероятностью 1/5, 3 — с вероятностью 4/25 и 5 с вероятностью оставшейся — это будет 16/25. Получается, что в среднем у нас будет 3,88 — это средняя длина пути из A в B. Но если мы посмотрим в другую сторону, то всё оказывается совсем просто. Из B в A мы дойдём с вероятностью 1 ровно за один шаг, то есть мы гарантированно дойдём из B в A за один шаг (у нас просто только один ход возможен, и мы сразу попадаем в A). То есть в одну сторону у нас момент достижения — это 3,88, а в другую это просто единица, видно, что они сильно разные. Понятно, что если бы мы рассмотрели такую вершину с гораздо большим числом лепестков, то разница была бы ещё больше. Хорошо. Величина несимметричная, но, с другой стороны, если мы хотим мерить близость вершин (по сути, мы хотим мерить расстояние между вершинами), нам естественно было бы иметь симметричную меру. В принципе, это не обязательно, но возможно и так — естественно. Давайте её заведём. Мы сделаем следующее. Мы назовём временем перемещения между вершинами u и v сумму моментов достижения из одной вершины в другую и обратно, то есть мы суммируем моменты достижения из u в v и из v в u, и это называем временем перемещения из u в v. То есть это сумма средних времён, которые требуются, чтобы дойти из u в v и чтобы дойти обратно. Аналогично мы можем ввести T-усечённое время перемещения — это сумма T-усечённых моментов достижения в одну сторону и в другую. Эта мера уже является симметричной и в этом смысле она лучше. Итак, что у нас получилось? У нас есть три метода нахождения похожих вершин. У нас есть усечённый момент из вершины, то есть если у нас есть фиксированная вершина и мы хотим находить похожие, чтобы предложить провести ребро в них, то первый вариант, что мы можем делать — мы можем посчитать усечённые моменты достижения из вершины во все остальные. Дальше мы можем сравнивать по усечённым моментам вершины: мы можем фиксировать нашу вершину и из других вершин смотреть, сколько занимает времени дойти в нашу. И наконец, у нас есть усечённое время перемещения между нашей вершиной и остальными. Таким образом для данной вершины мы можем посчитать близость ко всем остальным одним из трёх способов и можем тогда предложить добавить рёбра в самые близкие вершины, с которыми еще рёбер у нас нет. [ЗВУК]
