Betweenness Centrality for graphs with negative loops not giving an error?

[federico vaggi]

Hi everyone,

I am working on a directed graph with some negative weights and self loops.  As such, I figured that to calculate betweenness centrality I'd have to use the absolute value of the weights instead of the raw weights, because otherwise the graph has some paths of infinitely short length... but instead, nx doesn't seem to mind:

try:

    nx.shortest_path(G, weight = 'weight')

    print 'Shortest Path works ok!'

    # Throws a Value Error

except ValueError:

    print 'Error in Shortest Path'

try:

    nx.betweenness_centrality(G, weight = 'weight')

    print 'BC works ok!'

except ValueError:

    print 'Error in BC'

# Works ??  How?

Gives:

Error in Shortest Path BC works ok!

How is the shortest path algorithm actually working with negative cycles?  I tried digging into the bc algorithm, and it looks like it calls the _single_source_dijkstra_path_basic routine internally.  Is this intended?

Federico

[Dan Schult]

My understanding is that Djisktra should "work" with negative weights so long as there are no negative cycles (which includes negative self-loops). It finds the paths with minimal weight. But if there are negative cycles then there is no minimum. The documentation for single_source_djisktra says the algorithm is not guaranteed to work if edge weights are negative. But it doesn't say that it won't work.
Dan

> --
> You received this message because you are subscribed to the Google Groups "networkx-discuss" group.
> To post to this group, send email to networkx...@googlegroups.com.
> To unsubscribe from this group, send email to networkx-discu...@googlegroups.com.
> For more options, visit this group at http://groups.google.com/group/networkx-discuss?hl=en.