% Betweenness centrality measure: number of shortest paths running though a vertex
% Compute for all vertices, using Dijkstra's algorithm, using 'number of shortest paths through a node' definition
% Note: Valid for a general (connected) graph.
% INPUTS: adjacency (distances) matrix (nxn)
% OUTPUTS: betweeness vector for all vertices (nx1)
% Other routines used: dijkstra.m
% GB, December 22, 2009
function betw = node_betweenness_faster(adj)
n = length(adj);
spaths=inf(n,n);
adjk = adj;
% calculate number of shortest paths
for k=1:n-1
for i=1:n
for j=1:n
if adjk(i,j)>0; spaths(i,j)=min([spaths(i,j) adjk(i,j)]); end
end
end
adjk=adjk*adj;
end
betw = zeros(1,n);
for i=1:n
[dist,P]=dijkstra(adj,i,[]);
for j=1:n
if dist(j)<=1; continue; end % either i=j or i,j are 1 edge apart
betw(P{j}(2:dist(j))) = betw(P{j}(2:dist(j))) + 1/spaths(i,j);
end
end
betw=betw/nchoosek(n,2); % further normalize by the number of all node pairs