How to create random graph of n vertices with c fixed neighbours in MATLAB?

Question

Vic 2012-8-8

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/45564-how-to-create-random-graph-of-n-vertices-with-c-fixed-neighbours-in-matlab

I have written a code in MATLAB that allows me to generate a random graph of n vertices, each with c fixed neighbours without self connections (note the edges are directed, thus a connected to b does not imply b connected to a). However, it is terribly inefficient, especially when I need to it work on magnitudes such as n = 10000 and c = 1000. I was wondering if anyone could optimize it big time, or suggest anything constructive?

Thanks!

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

3 个评论
显示 1更早的评论隐藏 1更早的评论

Vic 2012-8-8

编辑：Vic 2012-8-8

在 MATLAB Online 中打开

n=c is impossible for the vertices cannot self connect (that was what I meant by 'without loops' - sorry for being imprecise). Anything with c<n would work. A quick example would be n=6,c=2 and the output may be:

       0     1     0     0     1     0
       0     0     1     0     0     1
       0     1     0     0     1     0
       1     0     0     0     0     1
       0     0     1     1     0     0
       1     0     0     1     0     0