Я считаю, что проблема, которую вы выдвигаете во многих терминах, соответствует сценарию использования алгоритма PageRank .
Я не буду обсуждать, как работает алгоритм в целом, поскольку в Интернете доступно много блогов / видео, которые уже объясняют его в деталях.Одно из моих любимых коротких видео на эту тему - this .
Теперь давайте посмотрим, как алгоритм подходит для вашего варианта использования.Давайте определим connectedness узла x как C (x) .Мы можем перефразировать ваше заданное утверждение «как дешево достичь других узлов из этого узла» до », насколько вероятно, что мы окажемся на данном узле в случайном обходе графа, так чтомы склонны брать ребра, стоимость которых меньше ".
Это утверждение в значительной степени относится к идеологии, лежащей в основе алгоритма PageRank.Нам просто нужно рассмотреть, как включить стоимость фронта для нашей работы.
Исходный алгоритм PageRank равномерно делит ранг страницы данного узла на все его соседние узлы (обозначается как PR (y) /OUT (y) в формуле) .Мы, с другой стороны, должны быть более склонны к краям с более низкой стоимостью, для которой я рекомендую изменить формулу на
(SUM-EDGES-COST (y) - EDGE-COST (x, y)) * (C (y) / СУММА-СТОИМОСТЬ (y))
вместо традиционных C (x) / OUT (x) .Мы берем разницу (SUM-EDGES-COST (y) - EDGE-COST (x, y)) , поскольку в нашем сценарии более низкая стоимость означает больше connectedness.Другая возможность заключается в применении функции softmax к стоимости границы для каждого узла в качестве стратегии нормализации.
Что касается ответа на вопрос о наличии коэффициента надежности, определяемого как R (x) для узла x мы можем просто умножить его непосредственно на C (x) в формуле.
Чтобы обернуть вещи,
должно соответствовать вашему заданному сценарию.
То, что я представил здесь, является лишь одной возможностью, о которой я могу подумать, исходя из моих соображений, и весьма вероятно,что это может не сработать.Все, на что я могу надеяться, это то, что это поможет вам тем или иным способом.Ура!:)