Is it possible to add a weight/probability to a node in graph theory(using networkx)

Question

I'm using networkx(library for python to deal with graphs). I basically have nodes with various edges but want to see what a path would look like if it used the nodes that were the most connected.

I can use this command to see the number of connections:

len(G.edges(CurrentNode))

and I can get the number of edges, but I'm not sure how to apply this to list as a path. For example, I can add this number as an attribute but I don't think attributes are taken into consideration when finding a path and because I'm adding this after the edges are connected, I cannot add the weights to the edges themselves. The other problem is the higher the score the more I want the path to be followed but with edges I think it follows the lowest weighted edge.

I'm wondering what approach do other people take to find paths based on certain characteristics of the node? If someone knows how to do this for networkx, great! but I think networkx has many features so if I can get the theory or general approach I'm sure I can find a way to do it in python.

UPDATE: Sorry I might be explaining it wrong. I understand I can add attributes to nodes, but I'm not sure how to make path decisions based on those attributes. So in my case, based on certain conditions I am adding edges between nodes. Each group of nodes represents a different day(day1data.., day2data.., day3data..), so I'm connecting a few nodes from day1 to nodes on day2 only if certain rules are matched. Once I have the edges connected, I want those ones to be considered more heavily when choosing a path. So I added an attribute 'weight' to each node of the current day which is basically the total number of edges connecting that node. My problem is, the weight attribute is not used in any of the path decision making because its an attribute I created and labeled myself(I could create a label named 'abc'='hello world' and it would apply that attribute to the node). How can I get this weight to be considered when creating the path(the edges are already created so I don't think I can go back and recreate them)?

Answer 1

You can certainly add weights to edges in NetworkX. In fact, you can set arbitrary data for edges, since it is basically a 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

Furthermore you can change the parameters of edges (or nodes) after you added them.

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}

And you can of course calculate path according to weights (or any other attribute specified in the weight parameter).

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]

For your case, deciding edge weights might be tricky. Bear in mind that weighted shortest path is calculated usually with Djikstra's Algorithm and it favors smaller weights. It also requires positive weights. One possible solution would be assigning a weight of 1/max(k_i,k_j) to edge (i,j) where k_i, k_j is the degree of nodes i and j.

The correct way to compute shortest paths over transition probabilities is to transform the edge weights to represent surprisal: that is, the negative log of the probability. This results in weights that are positive, and any given shortest path is then interpreted as minimizing surprisal. And since Dijkstra's algorithm sums up weights, it does so in log space, which means it really is multiplying probabilities. To recover the joint probability of observing any given shortest path, then, you just take the exponential of the negative surprisal.