How can I compute the betweenness centrality of a single node in NetworkX?

user_8351952 0
Viewed 2753

I'm trying to compute betweenness centrality for a few nodes in a very large graph. I've been using NetworkX. The problem is that it won't let me choose which nodes I need the centrality for. I tried modifying the source code, but it's giving me errors. Here's what I've done:

betweenness = dict.fromkeys(G, 0.0)  # b[v]=0 for v in G
if k is None:
    nodes = G
    #nodes = nx.Graph()
    #for indx in range(0, G.size()):
        #if indx in subset:
            #nodes.add_node(allNodes[indx])
else:
    random.seed(seed)
    nodes = random.sample(G.nodes(), k)
for s in nodes:
    n = nodes.nodes().index(s)
    if n in subset:
        # single source shortest paths
        if weight is None:  # use BFS
            S, P, sigma = _single_source_shortest_path_basic(G, s)
        else:  # use Dijkstra's algorithm
            S, P, sigma = _single_source_dijkstra_path_basic(G, s, weight)
            # accumulation
            if endpoints:
                betweenness = _accumulate_endpoints(betweenness, S, P, sigma, s)
            else:
                betweenness = _accumulate_basic(betweenness, S, P, sigma, s)
# rescaling
betweenness = _rescale(betweenness, len(interCommNodes),
                       normalized=normalized,
                       directed=G.is_directed(),
                       k=k)
return betweenness

Subset contains all the node indices in the original graph. Though "index" appears to be an invalid function and I cannot find a way to obtain it.

Can someone take a look at this?

Thanks!

networkx python
1 Answers

I'm afraid this won't directly address your question.

Presumably the reason you're trying to do this calculation is to speed things up because betweenness centrality is a slow calculation (Networkx never finishes calculating Betweenness centrality for 2 mil nodes).

The part that makes it slow is that it has to find the shortest paths between every single pair of nodes, and then see what fraction go through each node whose centrality you want. So even if you just want to know this for a few nodes, you still have to find all of the shortest paths, which is by far the most expensive part of the calculations. So there isn't much point in giving the option to do all of that work and then report the centrality for just a few nodes.

If you do need to speed up the calculation, there is a way to do an approximation. Instead of taking every single pair of nodes and finding the shortest paths between them, instead take a sample of all the nodes and look at the shortest paths between them. See this answer for the details: https://stackoverflow.com/a/32468942/2966723

user_29667230
Related