Python中的介数中心性

Question

你好，我是Python的新手，我想写一段代码来计算图的介数中心性。
我在这个链接上找到了Brandes算法的代码，但我不太明白，特别是V和A是什么意思，能帮帮我吗？
这是代码：

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 1

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]

请注意，下面这一部分代码不应该放在for循环里面：

如果w不等于s，那么就把C[w]的值加上e[w]。

我用Python的networkx库检查过结果。

Answer 2

我自己实现了Corey Abshire的代码，发现Unni的回答是正确的。比如说，V = ['A','B','C']，还有A = {'A' : ['B'], 'B' : ['A','C'], 'C' : ['B']}。

这表示的网络是：A--B--C。运行brandes.py后，会输出一个字典C = {'A': 0, 'B': 2, 'C':0}，因为从A到C和从C到A的两条最短路径都经过了B。

Answer 3

这里，V 是一个顶点的列表，而 A 是一个字典，用来表示图的邻接表，格式是 节点 : 邻居1, 邻居2，等等。

Answer 4

根据这篇论文《一种更快的介数中心性算法》，代码中的评论提到，V 是一个顶点的集合，而 A 是一个 n x n 的邻接矩阵，用于表示这些顶点之间的关系。