user3578723 user3578723 - 7 months ago 38
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 https://github.com/coreyabshire/tron/blob/master/brandes.py , 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 http://www.cs.ucc.ie/~rb4/resources/Brandes.pdf
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([])
Q.append(s)
while Q:
v = Q.popleft()
S.append(v)
for w in A[v]:
if d[w] < 0:
Q.append(w)
d[w] = d[v] + 1
if d[w] == d[v] + 1:
g[w] = g[w] + g[v]
P[w].append(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

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.