user3578723 - 1 year ago 117

Python Question

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 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.