Geek Answers Handbook

Is there a most efficient way to encode a program for Avg Clustering Coeff

Calculation of the average graph clustering coefficient I get the correct result, but it takes a huge time when the size of the graph increases, it takes some alternative method, so it takes less time to complete. Is there a way to simplify the code?

    %// A is adjacency matrix N X N, 
    %// d is degree ,

    N=100;
    d=10;
    rand('state',0)
    A = zeros(N,N);
    kv=d*(d-1)/2; 

%% Creating A matrix %%%

for i = 1:(d*N/2)
    j = floor(N*rand)+1;
    k = floor(N*rand)+1;
    while (j==k)||(A(j,k)==1)
        j = floor(N*rand)+1;
        k = floor(N*rand)+1;
    end
    A(j,k)=1;
    A(k,j)=1;
end 

%%   Calculation of clustering Coeff %%

    for i=1:N   
        J=find(A(i,:));  
        et=0;
        for ii=1:(size(J,2))-1
            for jj=ii+1:size(J,2)            
                et=et+A(J(ii),J(jj));
            end
        end
        Cv(i)=et/kv;
    end
    Avg_clustering_coeff=sum(Cv)/n;

The output I got.

Avg_clustering_coeff = 0.1107

+4
source share
2 answers

This part Calculation of clustering Coeffcan be vectorized using nchoosekto remove the innermost two nested loops, for example:

CvOut = zeros(1,N);
for k=1:N
    J=find(A(k,:));
    if numel(J)>1
        idx = nchoosek(J,2);
        CvOut(k) = sum(A(sub2ind([N N],idx(:,1),idx(:,2))));
    end
end
CvOut=CvOut/kv;

, !

+2

, , , .

, .

probnum  = cumsum(1:d);
probnum  = mean(probnum(end-1:end)); %theorical number of elements created by your second loop (for each row).
probfind = d*N/(N^2); %probability of finding a non zero value.
coeff    = probnum*probfind/kv;

Avg_clustering_coeff N.

, N N.

+1

More articles:


All Articles