Проблема, которую вы описываете, называется предсказание ссылки . Здесь - это краткое руководство, объясняющее проблему и некоторые простые эвристические методы, которые можно использовать для ее решения.
Поскольку это открытая проблема, эти простые решения можно значительно улучшить, используя более сложные методы. Еще один подход к прогнозированию вероятности преимущества заключается в использовании машинного обучения, а не эвристики на основе правил.
В недавней статье под названием node2vec был предложен алгоритм, который отображает каждый узел в графе в плотный вектор (он же embedding ). Затем, применив некоторый бинарный оператор к паре узлов, мы получим представление ребер (другой вектор). Этот вектор затем используется в качестве входных данных для некоторого классификатора, который предсказывает вероятность края. В статье сравнивалось несколько таких бинарных операторов по нескольким различным наборам данных, и они значительно превосходили эвристические результаты тестов по всем этим наборам данных.
Код для вычисления вложений с учетом вашего графа можно найти здесь .