如何在MATLAB中创建n个顶点且有c个固定邻居的随机图形？

Question

如何在MATLAB中创建n个顶点且有c个固定邻居的随机图形？

3

我在MATLAB中编写了一段代码，可以生成一个有n个顶点的随机图，每个顶点有c个固定的邻居，没有自环（请注意，边是有向的，因此“a连接到b”并不意味着“b连接到a”）。

然而，这段代码效率非常低，特别是当我需要处理像n = 10000和c = 1000这样的数量级时。我想知道是否有人能够大幅度优化它，或者提出任何有建设性的建议？

function [M]=matsrand(n,c)


MM=0;   %arbitrary starting value
while MM ~=n*c

    M = sparse(zeros(n));       
    ctin = zeros(1,n);  


    for i=1:n
        rp = randperm(n);   %generate vector of the randomly permuted order of n vertices
        rp(rp==i)=[];       %get rid of itself to avoid self connection

        noconnect=find(ctin(:)>=c); %generate list that i is not allowed to connect to
        where=ismember(rp,noconnect);   %returns 1 to the subset noconnect in rp
        noconnectind=find(where);

        rp(noconnectind(:))=[];         %remove the neurons i is not allowed to connect to

        if length(rp)<c
            break
        else
            r=rp(1:c);
        end
        M(i,r)=1;
        ctin(r)=ctin(r)+1;

    end
    MM=sum(ctin);
end

- user1585060

使用分析器查找您正在进行大量计算的位置，并确定是否可以减少计算量。我认为这将在“查找”调用中发生... - Gunther Struyf

你还要一遍又一遍地重复内部循环，直到出现幸运组合。你确定没有办法通过在某个地方添加一些检查来避免 length(rp)<c 吗？ - Gunther Struyf

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Gunther Struyf · Accepted Answer

这会稍微加快一些速度：

function [M]=matsrand(n,c)

    MM=0;   %arbitrary starting value
    all_nums=1:n;

    while MM ~=n*c

        M = sparse([],[],[],n,n,n*c);
        ctin = zeros(1,n);

        for ii=1:n
            noconnect=ctin>=c;
            noconnect(ii)=true;

            rem_nums = all_nums(~noconnect); % remaining numbers
            rp=randperm(n-sum(noconnect));
            rp = rem_nums(rp); % remaining numbers, hussled

            if numel(rp)<c
                break
            else
                r=rp(1:c);
            end
            M(ii,r)=1;
            ctin(r)=ctin(r)+1;
        end
        MM=sum(ctin);
    end
end

如果内存不是问题，我认为你可以用普通的zeros(n,n)替换稀疏矩阵。

主要问题仍然是你必须碰到那个幸运的组合。