Как найти вероятность прогнозируемого веса ссылки в весовом графике

Question

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

Я могу предсказать вес, найдя возможные пути и их средний вес, но как я могу найти вероятность этого

Answer 1

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

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

В недавней статье под названием node2vec был предложен алгоритм, который отображает каждый узел в графе в плотный вектор (встраивание). Затем, применив некоторый бинарный оператор к паре узлов, мы получим представление ребер (другой вектор). Этот вектор затем используется как входной признак для некоторого классификатора, который предсказывает вероятность края. В статье сравнивалось несколько таких бинарных операторов по нескольким различным наборам данных, и они значительно превосходили эвристические результаты тестов по всем этим наборам данных.

Код для вычисления вложений с учетом вашего графа можно найти здесь.