In [1]:

    

import networkx as nx
import random

n = 500
p = (n * 20.) / (n * (n - 1) * 0.5)

print("N={}, p={}".format(n, p))

def erdos_renyi_graph(n, p):
    graph = {k: [] for k in range(n)}
    
    for i in range(n):
        for j in range(i + 1, n):
            if random.random() < p:
                graph[i].append(j)
                graph[j].append(i)
    return graph

graph_adj = erdos_renyi_graph(n, p)
graph = nx.Graph(graph_adj)


    

    




N=500, p=0.0801603206413

In [2]:

    

def singe_source_shortes_paths(graph, s):
    pred = {k: [] for k in graph}
    dist = {k: float("inf") for k in graph}
    sigma = {k: 0. for k in graph}
    
    dist[s] = 0
    sigma[s] = 1.
    
    queue = [s]
    stack = []
    
    while queue:
        v = queue.pop(0)
        stack.append(v)
        
        for w in graph[v]:
            if dist[w] == float("inf"):
                dist[w] = dist[v] + 1
                queue.append(w)
            if dist[w] == dist[v] + 1:
                sigma[w] += sigma[v]
                pred[w].append(v)
                
    return pred, dist, sigma, stack


def accumulation(graph, s, stack, pred, sigma, btw):
    delta = {k: 0. for k in graph}
    
    while stack:
        w = stack.pop()
        
        for v in pred[w]:
            delta[v]+= float(sigma[v] * (1 + delta[w])) / sigma[w]
        
        if w != s:
            btw[w] += delta[w]
    
    return btw


    

In [3]:

    

%%time
betweenness = {k: 0. for k in graph}

for s in graph_adj:
    pred, dist, sigma, stack = singe_source_shortes_paths(graph_adj, s)
    betweenness = accumulation(graph_adj, s, 
                               stack, pred, sigma, betweenness)

betweenness = {k: betweenness[k] / 2. for k in betweenness}
my_version = betweenness.values()


    

    




CPU times: user 3.48 s, sys: 12 ms, total: 3.49 s
Wall time: 3.47 s

In [4]:

    

%%time
nx_version = nx.betweenness_centrality(graph, normalized=False).values()


    

    




CPU times: user 1.7 s, sys: 4 ms, total: 1.7 s
Wall time: 1.7 s

In [5]:

    

import numpy as np
np.testing.assert_almost_equal(my_version, nx_version, 10)