Грубо говоря, если существует много возможных путей между двумя узлами, то случайное обходе будет более вероятным между этими двумя узлами по сравнению с другой парой узлов с небольшим количеством возможных путей между ними. В этом смысле вероятность случайного обхода между двумя узлами расширяет отношение подобия к узлам, которые не связаны в графе.
Два аспекта довольно важны. Во-первых, обычно рассматривается конкретный случайный граф, а именно граф, полученный путем нормализации всех весов ребер (дуг), исходящих из узла, к сумме в единицу. Существуют также подходы, в которых некоторая процедура выборки выполняется с использованием исходных весов ребер, но я считаю, что конструкция explicity более полезна. Это приводит к марковскому графу, который можно просто представить как марковскую матрицу. Во-вторых, этот подход нормализации изменяет значение весов ребер в том смысле, что выбросы могут внезапно стать ближе к другим узлам. То есть, если узел A связан со сходствами 10 и 40 с узлами B и C (и без других узлов), а узел Z связан со сходствами 1 и 4 с узлами B и C (и без других узлов), то оба A и Z закончится с вероятностями перехода 0,2 и 0,8 к B и C соответственно. С этим нужно быть осторожным.
Преимущество этого подхода состоит в том, что веса ребер естественно учитываются; веса с более высокими краями будут переводиться в более высокие вероятности, а вероятности блужданий длиной более одного выпадают очень естественно как умножение марковских матриц. Для сравнения, общее количество путей между двумя узлами (или их взвешенная версия), вычисленное без шага нормализации случайного блуждания, может очень быстро взорваться и сильно искажаться из-за локальных вариаций плотности ребер или треугольников.
Одним из алгоритмов, использующих такую формулировку, является алгоритм кластеризации MCL. Другое приложение - это случайная обходность, которая снова может быть применена для использования кластеризации. Методы распространения меток, похоже, используют аналогичную идею.