Search code examples
pythonopenstreetmapnetworkx

How to add edge length as a weight in betweeness centrality using OSMNx/Networkx?


I'm using Python library OSMNx to get the betweenness centrality of a given street network G. Form what I see, the module osmnx.stats.extended_stats(G, bc=True) computes betweenness using NetworkX module networkx.betweenness_centrality(G, normalized=True, weight=None) setting all edge weights as equal. Since the edge length is already embedded in G, it would be straightforward to use it as a weight. Still I'm not able to find a way to do it.

How can I set the weight to be 1/length using these two libraries?

Please consider the graph given by the following example

import osmnx as ox
import networkx as nx

#Using OSMNx
G = ox.graph_from_bbox(37.79, 37.78, -122.41, -122.43, network_type='drive')
stats = ox.extended_stats(G,bc=True)
bet1 = stats["betweenness_centrality"]

#Using NetworkX
bet2 = nx.betweenness_centrality(G, weight=None)

Here is what I have tried so far:

import pandas as pd

l = nx.get_edge_attributes(G, 'length')
l = pd.Series(l).to_frame()
w=1/l
w = w.to_dict(orient="index")
nx.set_edge_attributes(G, w, 'w')
bet3 = nx.betweenness_centrality(G, weight='w')

But I'm arriving to exactly the same result as using no weights.


Solution

  • You have detected a bug in networkx handling of MultiDiGraph in the shortest path algorithms. See following example:

    import networkx as nx
    
    graph = nx.Graph()
    graph.add_weighted_edges_from([(1,2,1), (2,3,2), (1,3,1)])
    print(nx.betweenness_centrality(graph))
    # {1: 0.0, 2: 0.0, 3: 0.0}
    print(nx.betweenness_centrality(graph, weight="weight"))
    # {1: 0.5, 2: 0.0, 3: 0.0}
    
    
    multi_di_graph = nx.MultiDiGraph()
    multi_di_graph.add_weighted_edges_from([(1,2,1), (2,3,2), (1,3,1)])
    print(nx.betweenness_centrality(multi_di_graph))
    # {1: 0.0, 2: 0.0, 3: 0.0}
    print(nx.betweenness_centrality(multi_di_graph, weight="weight"))
    # {1: 0.0, 2: 0.0, 3: 0.0}
    

    The error is in the _single_source_dijkstra_path_basic especially the following code lines

    for w, edgedata in G[v].items():
        vw_dist = dist + edgedata.get(weight, 1)
    

    I'm not sure if the shortest path algorithms in networkx should work for multigraph, but since I've found no note, I think it's a bug. I would suggest, you open an issue on the networkx GitHub. If it is possible for the regarding part, you could think about casting to a usual DiGraph, too.