是否有最有效的方法来编写平均聚类系数的程序

Question

计算图的平均聚类系数 我得到了正确的结果，但是当图形维度增加需要一些替代方法以减少执行时间时，它会花费大量时间。有什么办法可以简化代码吗？？

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

我得到的输出。

Avg_clustering_coeff = 0.1107

Answer 1

要加快您的代码速度，您可以阅读我的评论，但您不会大幅减少计算时间，因为时间复杂度不会改变。

但是如果你不需要得到一个绝对的结果你可以使用概率。

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;

对于大 N，此概率系数将等于 Avg_clustering_coeff。

所以小N可以用普通方法，大N可以用这个方法

Answer 2

可以使用 nchoosek 对 Calculation of clustering Coeff 部分进行矢量化，以删除最里面的两个嵌套循环，就像这样 -

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;

希望这会大大提高性能！

是否有最有效的方法来编写平均聚类系数的程序

Is there most efficient way to code program for Avg Clustering Coeff

performance

matlab

matrix

cluster-analysis

matlab-guide