Можно ли добавить вес / вероятность к узлу в теории графов (используя сеть x)

Question

Я использую networkx (библиотека для python для работы с графиками).В основном у меня есть узлы с различными ребрами, но я хочу посмотреть, как будет выглядеть путь, если бы он использовал узлы, которые были наиболее подключены.

Я могу использовать эту команду для просмотра количества соединений:

len(G.edges(CurrentNode))

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

Мне интересно, какой подход используют другие люди, чтобы найти пути, основанные наопределенные характеристики узла?Если кто-то знает, как это сделать для networkx, отлично!но я думаю, что у networkx есть много возможностей, поэтому, если я смогу получить теорию или общий подход, я уверен, что смогу найти способ сделать это в python.

ОБНОВЛЕНИЕ: Извините, я мог бы объяснить это неправильно.Я понимаю, что могу добавлять атрибуты к узлам, но я не уверен, как принимать решения о путях на основе этих атрибутов.Так что в моем случае, основываясь на определенных условиях, я добавляю ребра между узлами.Каждая группа узлов представляет отдельный день (day1data .., day2data .., day3data ..), поэтому я соединяю несколько узлов из day1 с узлами в day2 только при условии соответствия определенных правил.После того, как у меня есть соединенные ребра, я хочу, чтобы они были учтены при выборе пути.Поэтому я добавил атрибут «вес» к каждому узлу текущего дня, который по сути является общим количеством ребер, соединяющих этот узел.Моя проблема в том, что атрибут веса не используется ни в одном из решений о пути, потому что его атрибут я создал и пометил сам (я мог бы создать метку с именем 'abc' = 'hello world', и он применил бы этот атрибут к узлу).Как я могу рассчитать этот вес при создании пути (ребра уже созданы, поэтому я не думаю, что могу вернуться и воссоздать их)?

Answer 1

Конечно, вы можете добавить веса к ребрам в NetworkX. Фактически, вы можете установить произвольные данные для ребер, так как это в основном dict.

In [30]: import networkx as nx

In [31]: G = nx.Graph()

In [32]: G.add_edge(1, 2, weight=3, type="green")

In [33]: G[1][2]
Out[33]: {'type': 'green', 'weight': 3}

In [34]: G[1][2]["weight"]
Out[34]: 3

Кроме того, вы можете изменить параметры ребер (или узлов) после их добавления.

In [35]: G[1][2]["weight"] = 5

In [36]: del G[1][2]["type"]

In [37]: G[1][2]["color"] = "green"

In [38]: G[1][2]
Out[38]: {'color': 'green', 'weight': 5}

И, конечно, вы можете рассчитать путь в соответствии с весами (или любым другим атрибутом, указанным в параметре веса).

In [39]: G.add_edge(1, 3, weight=1)

In [40]: G.add_edge(2, 3, weight=2)

In [41]: G.edges()
Out[41]: [(1, 2), (1, 3), (2, 3)]

In [42]: nx.shortest_path(G, source=1, target=2, weight="weight")
Out[42]: [1, 3, 2]

В вашем случае определение веса ребер может быть сложным. Имейте в виду, что взвешенный кратчайший путь обычно вычисляется с помощью Алгоритма Джикстры , и он поддерживает меньшие веса. Это также требует положительных весов. Одним из возможных решений было бы присвоение веса 1/max(k_i,k_j) ребру (i,j), где k_i, k_j - это степень узлов i и j.

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

Answer 2

Мой единственный способ учесть самодельные attribute s - редактировать файл в самой структуре.

Файл, который вы ищете, networkx/algorithms/shortest_paths/weighted.py

Там будет лямбда-объявление get_weight function, похожее на это:

if G.is_multigraph():
    get_weight = lambda u, v, data: min(
        eattr.get(weight, 1) for eattr in data.values())
else:
    get_weight = lambda u, v, data: data.get(weight, 1)

Я хотел придать своим node определенный вес, поэтому я изменил его следующим образом:

if G.is_multigraph():
    get_weight = lambda u, v, data: min(
        eattr.get(weight, 1) for eattr in data.values())
else:
    get_weight = lambda u, v, data: (data.get(weight,0) + nx.get_node_attributes(G, "node_weight").get(v,0)) 

Я установил вес ребра по умолчанию на 0: data: data.get(weight,0) и добавил значение моего собственного атрибута "node_weight" (по умолчанию 0).

data: (data.get(weight,0) + nx.get_node_attributes(G, "node_weight").get(v,0))

v является следующим достижимым node на графике.

Теперь вы можете установить attribute после создания графика.

nx.set_node_attributes(G, "node_weight", {1:3.5, 2:56})

Answer 3

Из NetworkX Tutorial

>>> G.add_edge(1, 2, weight=4.7 )
>>> G.add_edges_from([(3,4),(4,5)], color='red')
>>> G.add_edges_from([(1,2,{'color':'blue'}), (2,3,{'weight':8})])
>>> G[1][2]['weight'] = 4.7
>>> G.edge[1][2]['weight'] = 4

Похоже, веса могут быть добавлены после факта.