matlab求无权无向网络的节点介数

Question

matlab程序怎么编写求无权无向网络的节点介数，注释详细一些。

Answer 1

function BC = betweenness_centrality(G)
% G为无权无向网络的邻接矩阵
n = size(G, 1);
BC = zeros(n, 1);
for s = 1:n
    % 初始化
    P = cell(n, 1);
    sigma = zeros(n, 1);
    sigma(s) = 1;
    d = -1 * ones(n, 1);
    d(s) = 0;
    Q = [];
    Q(end+1) = s;
    while ~isempty(Q)
        v = Q(1);
        Q(1) = [];
        for w = find(G(v, :))
            if d(w) < 0
                Q(end+1) = w;
                d(w) = d(v) + 1;
            end
            if d(w) == d(v) + 1
                sigma(w) = sigma(w) + sigma(v);
                P{w}(end+1) = v;
            end
        end
    end
    delta = zeros(n, 1);
    while ~isempty(Q)
        w = Q(end);
        Q(end) = [];
        for v = P{w}
            delta(v) = delta(v) + sigma(v) / sigma(w) * (1 + delta(w));
        end
        if w ~= s
            BC(w) = BC(w) + delta(w);
        end
    end
end

其中，变量G为无权无向网络的邻接矩阵，n为节点数，BC为节点介数。算法采用Brandes算法，时间复杂度为$O(n^3)$。