python - 是否可以在图论中为节点添加权重/概率(使用 networkx)

Question

我正在使用 networkx(用于处理图形的 python 库)。我基本上有具有各种边缘的节点，但想看看如果它使用连接最紧密的节点，路径会是什么样子。

我可以使用这个命令来查看连接数:

len(G.edges(CurrentNode))

我可以获得边的数量，但我不确定如何将其应用到列表中作为路径。例如，我可以将此数字添加为属性，但我认为在查找路径时不会考虑属性，并且因为我是在边连接后添加的，所以我无法将权重添加到边本身。另一个问题是分数越高，我越希望遵循路径，但对于边，我认为它遵循最低权重的边。

我想知道其他人采用什么方法来根据节点的某些特征找到路径？如果有人知道如何为 networkx 执行此操作，那就太好了!但我认为 networkx 有很多特性，所以如果我能得到理论或一般方法，我相信我能找到一种在 python 中实现它的方法。

更新:对不起，我可能解释错了。我知道我可以向节点添加属性，但我不确定如何根据这些属性做出路径决策。所以在我的例子中，基于某些条件，我在节点之间添加边。每组节点代表不同的一天(day1data.., day2data.., day3data..)，因此仅当某些规则匹配时，我才将第 1 天的几个节点连接到第 2 天的节点。一旦我连接了边缘，我希望在选择路径时更多地考虑这些边缘。所以我为当天的每个节点添加了一个属性“权重”，它基本上是连接该节点的边的总数。我的问题是，权重属性没有用于任何路径决策，因为它是我自己创建并标记的属性(我可以创建一个名为'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]

对于您的情况，确定边缘权重可能很棘手。请记住，加权最短路径通常使用 Djikstra's Algorithm 计算得出。它有利于较小的重量。它还需要正权重。一种可能的解决方案是将 1/max(k_i,k_j) 的权重分配给边 (i,j)，其中 k_i, k_j是节点i和j的度数。

计算转移概率上的最短路径的正确方法是转换边权重以表示意外:即概率的负对数。这导致权重为正，然后任何给定的最短路径都被解释为最小化意外。由于 Dijkstra 算法对权重求和，因此它在对数空间中这样做，这意味着它实际上是在乘以概率。为了恢复观察任何给定最短路径的联合概率，您只需取负意外的指数。