12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182 |
- function [EBC,BC]=edge_betweenness_wei(G)
- %EDGE_BETWEENNESS_WEI Edge betweenness centrality
- %
- % EBC = edge_betweenness_wei(L);
- % [EBC BC] = edge_betweenness_wei(L);
- %
- % Edge betweenness centrality is the fraction of all shortest paths in
- % the network that contain a given edge. Edges with high values of
- % betweenness centrality participate in a large number of shortest paths.
- %
- % Input: L, Directed/undirected connection-length matrix.
- %
- % Output: EBC, edge betweenness centrality matrix.
- % BC, nodal betweenness centrality vector.
- %
- % Notes:
- % The input matrix must be a connection-length matrix, typically
- % obtained via a mapping from weight to length. For instance, in a
- % weighted correlation network higher correlations are more naturally
- % interpreted as shorter distances and the input matrix should
- % consequently be some inverse of the connectivity matrix.
- % Betweenness centrality may be normalised to the range [0,1] as
- % BC/[(N-1)(N-2)], where N is the number of nodes in the network.
- %
- % Reference: Brandes (2001) J Math Sociol 25:163-177.
- %
- %
- % Mika Rubinov, UNSW/U Cambridge, 2007-2012
- n=length(G);
- % E=find(G); G(E)=1./G(E); %invert weights
- BC=zeros(n,1); %vertex betweenness
- EBC=zeros(n); %edge betweenness
- for u=1:n
- D=inf(1,n); D(u)=0; %distance from u
- NP=zeros(1,n); NP(u)=1; %number of paths from u
- S=true(1,n); %distance permanence (true is temporary)
- P=false(n); %predecessors
- Q=zeros(1,n); q=n; %order of non-increasing distance
- G1=G;
- V=u;
- while 1
- S(V)=0; %distance u->V is now permanent
- G1(:,V)=0; %no in-edges as already shortest
- for v=V
- Q(q)=v; q=q-1;
- W=find(G1(v,:)); %neighbours of v
- for w=W
- Duw=D(v)+G1(v,w); %path length to be tested
- if Duw<D(w) %if new u->w shorter than old
- D(w)=Duw;
- NP(w)=NP(v); %NP(u->w) = NP of new path
- P(w,:)=0;
- P(w,v)=1; %v is the only predecessor
- elseif Duw==D(w) %if new u->w equal to old
- NP(w)=NP(w)+NP(v); %NP(u->w) sum of old and new
- P(w,v)=1; %v is also a predecessor
- end
- end
- end
- minD=min(D(S));
- if isempty(minD), break %all nodes reached, or
- elseif isinf(minD) %...some cannot be reached:
- Q(1:q)=find(isinf(D)); break %...these are first-in-line
- end
- V=find(D==minD);
- end
- DP=zeros(n,1); %dependency
- for w=Q(1:n-1)
- BC(w)=BC(w)+DP(w);
- for v=find(P(w,:))
- DPvw=(1+DP(w)).*NP(v)./NP(w);
- DP(v)=DP(v)+DPvw;
- EBC(v,w)=EBC(v,w)+DPvw;
- end
- end
- end
|