python calculation error for graph with networkx

Question

I made a huge graph from the data which is collected from data mining.

I used 'networkx' for making graph and I'd like to change huge graph to another graph.

that for each node, the sum of weighted edge is 1.

So I write my code as below:

ng=nx.Graph()  
for n in g.nodes():  
    s=0.0  
    for nb in g.neighbors(n):  
         s=s+1.0/g[n][nb]['weight']  
    for nb in g.neighbors(n):  
        ng.add_edge(n,nb,weight=1.0/s/g[n][nb]['weight'])

After I check the result by the code like below

for n in ng.neighbors('100002950636410'):
    print str(n) + ' : ' + str(ng[n]['100002950636410']['weight'])

the sum of the neighbors are not 1 and also there are lots of edge whose 'weight' is 1.

Did I something wrong? I think my calculation and code is correct but if the problem is the size of graph, then what should I do?

daedalus · Accepted Answer · 2013-06-04 20:02:31Z

The Problem with your Problem

I do not think your solution can work in the way you are trying to do it. I demonstrate why first, then I propose an alternative solution below.

Consider this code:

import networkx as nx
import matplotlib.pyplot as plt
import random

# Set up a graph with random edges and weights

G = nx.barabasi_albert_graph(6, 2, seed= 3214562)
for u,v in G.edges_iter():
    G[u][v]['weight'] = int(random.random() * 10)

pos = nx.spring_layout(G)

nx.draw(G, pos)
nx.draw_networkx_edge_labels(G,pos)
plt.show()

It produces this figure:

enter image description here

Consider node 1. It has two edges whose weights are 2 and 9 respectively. We should adjust the weights to 2/11 and 9/11 respectively.

Next consider node 4. It now has two edges with weights 2/11 and 8 respectively. The first weight is fixed from the previous calculation so we basically adjust the second weight to be 8/(8+2/11).

We now have three edges whose weights are adjusted and fixed. We now repeat this for nodes 0, 3, and 5. By the end of the process, all the edges around node 2 have been readjusted and fixed, but they will not sum up to 1, unless by a remarkable coincidence. In a larger graph, of course, this problem would arise much faster.

The Solution

Instead of re-weighting the edges themselves, I propose that you attach to each node a new data attribute containing a dictionary of re-weighted edges. This is the relevant code for demonstration:

for n in G.nodes_iter():
    total = sum([ attr['weight']
                  for u,v,attr in G.edges(n, data=True) ])
    total = float(total)
    weights = dict([(nb, G[n][nb]['weight']/total)
                    for nb in G.neighbors(n)])
    G[n]['adj_weights'] = weights

# Print out the adjusted weights

for n in G.nodes_iter():
    for nb,w in G[n]['adj_weights'].iteritems():
        w = int(w*1000)/1000.
        print '{} to {}: {}'.format(n, nb, w)

This produces:

0 to 2: 0.272
0 to 3: 0.727
1 to 2: 0.818
1 to 4: 0.181
2 to 0: 0.081
2 to 1: 0.243
2 to 3: 0.243
2 to 4: 0.216
2 to 5: 0.216
3 to 0: 0.363
3 to 2: 0.409
3 to 5: 0.227
4 to 1: 0.2
4 to 2: 0.8
5 to 2: 0.615
5 to 3: 0.384

Thus the edges to node 0 sum up to one, as do the edges attached to node 3, for example. But edge (0,3) has a weight of 0.727 when seen from node 0, and 0.363 when seen from node 3.

I hope this gets you going.

This looks like an amazing answer, but could perhaps use a quick word on why re-weighting the edges is the incorrect approach? (possible that it has been addressed, and I'm just not familiar enough with the problem domain).
Thanks @Hannele. Naively re-weighing the edges will result in conflicts such as illustrated in the conclusion of my answer. Edge (0,3), for example, should have a different weight when normalised from the point of view of node 0 or of node 3. As I demonstrate in the solution, of course it is possible to normalise the edge weights around each node as long as the weight attributes are stored separately for each node. Another solution might be to store two weights on each edge.

Collectives™ on Stack Overflow

python calculation error for graph with networkx

1 Answer 1

The Problem with your Problem

The Solution

2 Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

The Problem with your Problem

The Solution

2 Comments

Related