user3578723 user3578723 - 1 year ago 106
Python Question

betweennes centrality python

hello im new with python and i want to write a code to calculate the betweennes centrality for a graph .
i found brandes algorithm code on , but i dont understand it, specially what is V, and A, help please.
here is the code:

from collections import deque
def brandes(V, A):
"Compute betweenness centrality in an unweighted graph."
# Brandes algorithm
# see
C = dict((v,0) for v in V)
for s in V:
S = []
P = dict((w,[]) for w in V)
g = dict((t, 0) for t in V); g[s] = 1
d = dict((t,-1) for t in V); d[s] = 0
Q = deque([])
while Q:
v = Q.popleft()
for w in A[v]:
if d[w] < 0:
d[w] = d[v] + 1
if d[w] == d[v] + 1:
g[w] = g[w] + g[v]
e = dict((v, 0) for v in V)
while S:
w = S.pop()
for v in P[w]:
e[v] = e[v] + (g[v]/g[w]) * (1 + e[w])
if w != s:
C[w] = C[w] + e[w]
return C

Answer Source

According to the paper A Faster Algorithm for Betweenness Centrality cited by the comments of the code, it appears as if V is the set of vertices and A is an n x n adjacency matrix for the given vertices.