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

Question

我正在使用networkx（一个用于处理图形的Python库）。我基本上有一些节点和各种连接，但我想看看如果使用连接最多的节点，路径会是什么样子的。

我可以用这个命令来查看连接的数量：

len(G.edges(CurrentNode))

我可以得到边的数量，但我不太确定如何将这个数量应用到路径列表中。例如，我可以把这个数字作为一个属性添加上去，但我觉得在寻找路径时并不会考虑这些属性。而且因为我是在边连接后添加的这个属性，所以我不能把权重直接加到边上。另一个问题是，分数越高，我越希望这个路径被优先选择，但我觉得在边的选择上，系统是跟随权重最低的边。

我想知道其他人是如何根据节点的某些特征来寻找路径的？如果有人知道如何在networkx中做到这一点，那就太好了！不过我觉得networkx有很多功能，所以如果我能了解一些理论或一般的方法，我相信我能在Python中找到解决办法。

更新：抱歉，我可能解释得不太清楚。我明白我可以给节点添加属性，但我不太确定如何根据这些属性来做路径决策。在我的例子中，根据某些条件，我在节点之间添加了边。每组节点代表不同的一天（day1data.., day2data.., day3data..），所以我只在某些规则匹配时，把day1的一些节点连接到day2的节点。一旦我连接了这些边，我希望在选择路径时能更重视这些边。所以我给当前日期的每个节点添加了一个'weight'属性，这个属性基本上是连接到该节点的边的总数量。我的问题是，这个权重属性在路径决策中没有被使用，因为这是我自己创建并标记的属性（我可以创建一个名为'abc'的标签，值为'hello world'，并将这个属性应用到节点上）。我该如何让这个权重在创建路径时被考虑进去（因为边已经创建了，所以我觉得我不能回去重新创建它们）？

Answer 1

我唯一考虑自己创建的 attribute 的方法，就是直接修改框架里的一个文件。

你需要找的文件是 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)

我想给我的 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 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中，你当然可以给边添加权重。实际上，你可以为边设置任意数据，因为边本质上就是一个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]

对于你的情况，决定边的权重可能会有点棘手。要记住，加权最短路径通常是通过Dijkstra算法来计算的，它更倾向于较小的权重，并且要求权重为正数。一个可能的解决方案是给边(i,j)分配一个权重1/max(k_i,k_j)，其中k_i和k_j是节点i和j的度数。

计算基于转移概率的最短路径的正确方法是将边的权重转换为惊讶度：也就是说，取概率的负对数。这会导致权重为正数，并且任何给定的最短路径都可以理解为最小化惊讶度。而且，由于Dijkstra算法是对权重进行求和，它实际上是在对数空间中进行的，这意味着它实际上是在乘以概率。因此，要恢复观察到任何给定最短路径的联合概率，你只需取负惊讶度的指数。