Давайте теперь обсудим частный случай блуждания длины три. Напомним, что у нас уже был простой способ находить ближайшие вершины к данной: просто смотреть на количество общих соседей у наших вершин. Оказывается, что этот простой подход близок к тому, что получается у нас при блужданиях длины три. Давайте посмотрим на три-усеченный момент достижения из нашей вершины, которая нас интересует, в вершину v. Нас при этом интересуют только не соединенные вершины, то есть нас интересуют только v, которые не соединены с нашей вершиной, поэтому мы не дойдем до v за один шаг. Давайте посмотрим, какие у нас шансы дойти за два хода. Нам для этого нужно два события: на первом шаге нам нужно перейти в соседа вершины v, а на втором шаге нам нужно перейти в саму вершину v. Первое событие означает, что мы перешли, на самом деле, в общего соседа нашей вершины A с вершиной v. Дальше, если мы попали в конкретную вершину u, то второе событие происходит с вероятностью единица делить на степень этой вершины u. Суммарная вероятность получается такой: мы суммируем по всем общим соседям наших вершин (число общих соседей мы обозначаем через N от A и v), и дальше мы должны перемножить вероятности каждого из шагов и вероятность первого шага — это единица на степень нашей вершины, вероятность второго шага — это единица на степень общего соседа. Теперь степень нашей вершины мы можем вынести наружу — получится единица на степень нашей вершины, умноженная на сумму единиц на степень вершины наших общих соседей. Итак, получается, что с вероятностью единица минус p, при этом длина пути будет равна трем. То есть мы с вероятностью p попадаем в вершину v за два шага, а с вероятностью единица минус p путь в любом случае будет равен трем. Получается, что средняя длина пути тем короче, чем больше p, то есть чем больше p, тем короче наш путь. И, по сути, что измеряет p? P измеряет число общих соседей у нашей вершины с вершиной v, но при этом каждый сосед учитывается с некоторым весом, то есть мы не просто считаем количество соседей, а мы берем такую взвешенную сумму. У каждого соседа вес — это единица делить на его степень. И чем меньше степень соседа, тем больший вклад он дает вот в эту нашу сумму. Это, в принципе, может быть естественно с точки зрения нашей задачи: у нас может быть общий друг (у наших двух вершин), у которого мало друзей, и тогда, наверное, естественно считать, что, возможно, он из этой же группы, и тогда наши вершины тоже тогда знакомы. Хорошо, если смотреть на блуждания в обратную сторону, в нашу вершину, то будет похожий результат. Единственное, что снаружи суммы у вас будет единица, деленная на степень вершины кандидата, а не нашей вершины. Тогда получается, что мы делим на степени вершины кандидата, и, по сути, мы говорим, что мы измеряем не общее число соседей у нашей вершины и кандидата, а долю общих соседей среди всех вершин кандидата. И это, в принципе, может быть естественно с точки зрения нашей задачи. В принципе, может так оказаться, что у нашего соседа и у кандидата много общих соседей не потому, что они знакомы, а потому что у кандидата просто очень много друзей, и поэтому, в частности, довольно много друзей общих с нашей вершиной. В принципе, мы, возможно, хотели бы контролировать эту ситуацию и смотреть не на абсолютное количество общих соседей, а на долю среди соседей вершин кандидата. Итак, у нас есть четыре способа искать вершины, с которыми нужно соединить нашу данную вершину, и есть один простой способ (просто число общих соседей), и есть три способа, основанных на случайных блужданиях. Давайте теперь попробуем посмотреть на практике, что из этого лучше работает.