グラフ理論（ネットワークxを使用）でノードに重み/確率を追加することは可能ですか？

Question

私はnetworkx（グラフを扱うためのPythonライブラリ）を使用しています。私は基本的にはさまざまなエッジのノードを持っていますが、最も接続されているノードを使用した場合のパスがどのように見えるかを見たいと思っています。

私は接続の数を確認するには、このコマンドを使用することができます

：

len(G.edges(CurrentNode)) 

を、私はエッジの数を取得することができますが、私はパスとしてリストにこれを適用するかどうかはわかりません。たとえば、この数値を属性として追加できますが、パスを見つけるときに属性が考慮されていないと考えられます。エッジが接続された後にこれを追加するため、エッジ自体にウェイトを追加できません。もう1つの問題は、スコアが高ければ高いほど私はパスを辿りたいが、エッジは最も低い重み付けエッジに従うと思う。

ノードの特定の特性に基づいて他の人がどのようなアプローチでパスを見つけるのでしょうか？誰かが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} 

もちろん、重み（またはweightパラメータで指定された他の属性）に従ってパスを計算することもできます。

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つの可能な解決策は、1/max(k_i,k_j)の重みをエッジ(i,j)に割り当てることであり、k_i,k_jはノードiおよびjの次数である。

遷移確率で最短経路を計算する正しい方法は、驚くべきことを表すためにエッジ重みを変換することです。すなわち、確率の負の対数です。これにより、正の重みが得られ、与えられた最短経路は驚くべき最小化として解釈されます。ダイクストラのアルゴリズムは重みを集計するので、ログ空間ではそうなります。つまり、実際に確率が倍増しています。与えられた最短経路を観測する結合確率を回復するには、負の驚くべきものの指数関数を取るだけです。

Answer 2

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 

から重みが事実後に添加することができるように見えます。

Answer 3

自作のattributeを考慮する唯一の方法は、フレームワーク自体のファイルを編集することでした。このように見ているget_weightfunctionのラムダ宣言があるだろうに

あなたが探してファイルがnetworkx/algorithms/shortest_paths/weighted.py

です：

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 SA一定の重みを与えたいと思ったので、私は修正しましたそれは次のようになります：

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) ndは自分の属性 "node_weight"（デフォルトは0）の値を追加しました。グラフ内の次の到達nodeある

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

v。

グラフを作成した後にattributeを設定できるようになりました。

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