function C=clustering_coef_bd(A) %C=clustering_coef_bd(A); clustering coefficient C, for binary directed graph A % %Reference: Fagiolo, 2007, Phys Rev E 76:026107. % %Mika Rubinov, UNSW, 2007 (last modified July 2008) %In directed graphs, 3 nodes generate up to 8 triangles (2*2*2 edges) %The number of existing triangles is the main diagonal of S3/2 %The number of all (in or out) neighbour pairs is K(K-1)/2 %Each neighbour pair may generate two triangles %“False pairs“ are ij edge pairs (these do not generate triangles) %The number of false pairs is the main diagonal of A2 %Thus the maximum possible number of triangles = % = (2 edges)*(ALL PAIRS - FALSE PAIRS) = % = 2 * (K(K-1)/2 - diag(A2) = K(K-1) - 2(diag(A2) S=A+A.; %symmetrized input graph K=sum(S,2); %total degree (in + out) cyc3=diag(S3)/2; %number of 3-cycles (ie. directed triangles) K(cyc3=0)=inf; %if no 3-cycles exist, make C=0 (via K=inf) CYC3=K.*(K-1)-2*diag(A2); %number of all possible 3-cycles C=cyc3./CYC3; %clustering coefficient function C=clustering_coef_bu(G) %C=clustering_coef_bu(G); clustering coefficient C, for binary undirected graph G % %Reference: Watts and Strogatz, 1998, Nature 393:440-442 % %Mika Rubinov, UNSW, 2007 (last modified September 2008) n=length(G); C=zeros(n,1); for u=1:n V=find(G(u,:); k=length(V); if k=2; %degree must be at least 2 S=G(V,V); C(u)=sum(S(:)/(k2-k); end end function C=clustering_coef_wd(W) %C=clustering_coef_wd(W); clustering coefficient C for weighted directed graph W. % %Reference: Fagiolo, 2007, Phys Rev E 76:026107 %(also see Onnela et al. 2005, Phys Rev E 71:065103); % %Mika Rubinov, UNSW, 2007 (last modified July 2008) %See comments for clustering_coef_bd %The weighted modification is as follows: %- The numerator: adjacency matrix is replaced with weights matrix 1/3 %- The denominator: no changes from the binary version % %The above reduces to symmetric and/or binary versions of the % clustering coefficient for respective graphs. A=W=0; %adjacency matrix S=W.(1/3)+(W.).(1/3); %symmetrized weights matrix 1/3 K=sum(A+A.,2); %total degree (in + out) cyc3=diag(S3)/2; %number of 3-cycles (ie. directed triangles) K(cyc3=0)=inf; %if no 3-cycles exist, make C=0 (via K=inf) CYC3=K.*(K-1)-2*diag(A2); %number of all possible 3-cycles C=cyc3./CYC3; %clustering coefficient function C = clustering_coef_wu(W) m n =size(W); CorrMatrix = W; for i=1:m S1=0; S2=0; for k=1:m if k=i for l=1:m if (l=k) S2 = CorrMatrix(i,k)*CorrMatrix(i,l)+S2; end end end end C(i) = S1/S2; end function D=distance_bin(G) %D=distance_bin(G); distance matrix for binary undirected graph G %Mean distance (excluding the main diagonal) equals the characteristic path length % %Algebraic shortest path algorithm. % %Mika Rubinov, UNSW, 2007 (last modified September 2008). D=eye(length(G); n=1; nPATH=G; %n-path matrix L=(nPATH=0); %shortest n-path matrix while find(L,1); D=D+n.*L; n=n+1; nPATH=nPATH*G; L=(nPATH=0).*(D=0); end D(D)=inf; %disconnected nodes are assigned d=inf; D=D-eye(length(G); function D=distance_wei(G) %D=distance_wei(G); distance matrix for weighted directed graph - %the mean distance is the characteristic path length. % %The input matrix must be a mapping from weight to distance (eg. higher %correlations may be interpreted as short distances - hence an inverse %mapping is appropriate in that case). % %Dijkstras Algorithm. % %Mika Rubinov, UNSW, 2007 (last modified July 2008). n=length(G); E=find(G); G(E)=1./G(E); %invert weights: large - short D=zeros(n); D(eye(n)=inf; %distance matrix for u=1:n S=true(1,n); %distance permanence (true is temporary) 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 W=find(G1(v,:); %neighbours of shortest nodes for w=W; D(u,w)=min(D(u,w),D(u,v)+G1(v,w); %the smallest of old (if exist) and current path lengths end end minD=min(D(u,S); if isempty(minD)|isinf(minD), break, end; %isempty: all nodes reached; isinf: some nodes cannot be reached V=find(D(u,:)=minD); end end function E=efficiency(G,local) %Global and local efficiency for binary undirected graph G. % %Eglob=efficiency(G); outputs the inverse distance matrix: the mean of this %matrix (excluding main diagonal) is equivalent to the global efficiency. % %Eloc=efficiency(G,1); outputs individual nodal local efficiency. %For directed networks, local efficiency works with the out-degree. % %Reference: Latora and Marchiori, 2001, Phys Rev Lett 87:198701. % %Algebraic shortest path algorithm. % %Mika Rubinov, UNSW, 2008 (last modified September 2008). if nargin=2; %local efficiency N=length(G); %number of nodes E=zeros(N,1); %local efficiency for u=1:N V=find(G(u,:); %neighbors k=length(V); %degree if k=2; %degree must be at least two e=distance_i