Link Prediction — прогнозирование ребер в сети с помощью Networkx.

Прогнозирование ссылок — ключевая идея в области сетевого анализа. Это предполагает предвидение возможности установления связи между узлами сети. Мощным инструментом сетевого анализа, включая задачи прогнозирования ссылок, является модуль NetworkX для Python. Это подробное руководство поможет вам использовать NetworkX для прогнозирования ссылок и изобилует краткими и понятными примерами.

Введение в прогнозирование ссылок

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

Начало работы с NetworkX

Прежде чем переходить к прогнозированию ссылок, убедитесь, что библиотека NetworkX установлена. Если нет, используйте pip для его установки –

pip install networkx

Нам также необходимо установить библиотеки numpy и pandas, чтобы прогнозировать ссылки:

pip install numpy pandas

Основы создания сети в NetworkX

Давайте начнем с создания фундаментальной сети в NetworkX —

import networkx as nx

# Create an empty graph
G = nx.Graph()

# Add nodes
G.add_node(1)
G.add_node(2)
G.add_node(3)

# Add edges
G.add_edge(1, 2)
G.add_edge(1, 3)

# Draw the graph
nx.draw(G, with_labels=True)

В этой простой сети всего три узла и два ребра.

Прогнозирование ссылок в NetworkX

Для прогнозирования ссылок NetworkX предлагает ряд функций. Они основаны на различных методах и теориях.

Пример 1: Общие соседи

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

# Create a graph
G = nx.complete_graph(5)
G.remove_edge(1, 3)

# Perform link prediction
preds = nx.common_neighbors(G, 1, 3)
print(len(list(preds)))  # Output: 3

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

Пример 2: Коэффициент Жаккара

Количество общих соседей делится на общее количество соседей, чтобы вычислить коэффициент Жаккара, который оценивает вероятность ребра.

# Create a graph
G = nx.complete_graph(5)
G.remove_edge(1, 3)

# Perform link prediction
preds = nx.jaccard_coefficient(G, [(1, 3)])
for u, v, p in preds:
   print(f'({u}, {v}) -> {p}')  # Output: (1, 3) -> 0.6

На этой иллюстрации вычисляется коэффициент Жаккара удаленного ребра.

Пример 3: Предпочтительное прикрепление

Согласно теории предпочтительного прикрепления, узлы с высокой степенью (больше соединений) с большей вероятностью соединятся в будущем.

# Create a graph
G = nx.complete_graph(5)
G.remove_edge(1, 3)

# Perform link prediction
preds = nx.preferential_attachment(G, [(1, 3)])
for u, v, p in preds:
   print(f'({u}, {v}) -> {p}')  # Output: (1, 3) -> 12

В этом примере рассчитывается оценка предпочтительного прикрепления для удаленного ребра.

Пример 4: Индекс Адамика/Адара

Подобно обычным соседям, индекс Адамика/Адара уделяет меньше внимания узлам с высокой степенью.

# Create a graph
G = nx.complete_graph(5)
G.remove_edge(1, 3)

# Perform link prediction
preds = nx.adamic_adar_index(G, [(1, 3)])
for u, v, p in preds:
   print(f'({u}, {v}) -> {p}')  # Output: (1, 3) -> 1.8204784532536746

В этом случае рассчитывается десятичное значение, известное как индекс Адамика/Адара, которое измеряет исключенное ребро.

Пример 5: Индекс распределения ресурсов

Еще одна метрика, которая создает оценку на основе общих соседей двух узлов, — это индекс распределения ресурсов.

# Create a graph
G = nx.complete_graph(5)
G.remove_edge(1, 3)

# Perform link prediction
preds = nx.resource_allocation_index(G, [(1, 3)])
for u, v, p in preds:
   print(f'({u}, {v}) -> {p}')  # Output: (1, 3) -> 0.6666666666666666

Здесь рассчитывается индекс распределения ресурсов удаленного ребра.

Заключение

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

В этом руководстве мы применили практический подход к пониманию прогнозирования ссылок в NetworkX. Были обсуждены фундаментальные идеи и на простых примерах проиллюстрированы различные методы прогнозирования каналов. Но это только самая верхушка айсберга. Возможности для исследования сети и прогнозирования соединений открываются по мере более глубокого изучения NetworkX.