是否可以在图论中为节点添加权重/概率（使用networkx）

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]

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

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

Answer 2

从 NetworkX 教程

>>> 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

看来权重可以在事后添加。

Answer 3

我考虑自制属性的唯一方法是在框架本身中编辑文件。

您要查找的文件是 networkx/algorithms/shortest_paths/weighted.py

其中将有一个 get_weight function 的 lambda 声明，如下所示：

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)

我想给我的节点一定的权重，所以我修改它如下：

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 是图中下一个可到达的节点。

现在，您可以在创建图表后设置属性。

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