Gibt es den effizientesten Weg, Programm für Avg Clustering Coeff zu programmieren

Question

Berechnung des durchschnittlichen Clustering-Koeffizienten eines Diagramms Ich bekomme korrekte Ergebnis, aber es dauert sehr viel Zeit, wenn die Grafikdimension erhöht sich einige alternative, so dass es weniger dauert Zeit zur Ausführung. Gibt es eine Möglichkeit, den Code zu vereinfachen?

%// 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; 

Ausgabe ich bekam.

Avg_clustering_coeff = 0,1107

Answer 1

Das Calculation of clustering Coeff Teil verwenden vektorisiert werden mit nchoosek die innersten zwei verschachtelten Schleifen zu entfernen, wie so -

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; 

Hoffentlich dies t steigern würde Er Leistung ziemlich!

Answer 2

Um Ihren Code zu beschleunigen können Sie meinen Kommentar lesen, aber Sie werden nicht drastisch die Rechenzeit zu reduzieren, weil die Zeitkomplexität nicht ändert.

Aber wenn Sie kein absolutes Ergebnis erhalten müssen, können Sie die Wahrscheinlichkeit verwenden.

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; 

Diese probabilistischen Koeff gleich für große N. zu Avg_clustering_coeff sein wird

könnte So können Sie die normale Methode für kleine N und diese Methode für große N.