1 view (last 30 days)

I have the following code for generating a small (~1e3) graph that I can control the degree of (code 1). This has n (number of nodes), min, max and avg degree as the inputs.

clc;clear;

n=5000;

% dl=10; %dl=degree limit

mind=5;

maxd=100;

avgd=10;

totd=avgd*n;

td=.5*n*(n-1);

a=zeros(n,n);

degct=zeros(1,n);

nd=2:n;

% generating adj

for i=1:n

t=[];

tn=mind-degct(i);

if length(nd)<tn

t=randperm(n-1,tn);

a(i,t)=1;

a(t,i)=1;

degct=sum(a);

break;

end

if tn>0

t=randperm(length(nd),tn);

a(i,nd(t))=1;

a(nd(t),i)=1;

degct=sum(a);

end

ind=find(degct==mind);

nd=setdiff(nd,ind);

if (isempty(nd))

break;

end

end

%%

% a=a+a';

a1=triu(a);

rd=totd-sum(degct);

at=-1*ones(n,n);

at=tril(at);

a1=a1+at;

indt=find(a1==0);

ind=randperm(length(indt),rd);

a1(indt(ind))=1;

a1=triu(a1);

a1=a1+a1';

a=a1;

%%

for i=1:n-1

a(i,i+1)=1;

a(i+1,i)=1;

end

for i=1:n

a(i,i)=0;

end

%%

if issymmetric(a)

disp('a is symmetric')

else

disp('symmetricity error')

end

%%

filemat='file1.mat';

save(filemat,'a');

%%

sa=[];

sa=sum(a);

min(sa)

max(sa)

But then I have figured out a way to generate random graphs using a logical array that takes less time and memory to compute (code 2). This has only nodes and connectivity as the inputs.

function [a,ed] = Random_graph_genar_function_v4(nodes, connectivity)

nPasses=10;

a=sparse(false);

for i=1:nPasses

a=a | logical(sprandsym(nodes,connectivity/nPasses));

end

a(1:nodes+1:end)=0; %zero the diagonal

G=graph(a);

ed=table2array(G.Edges).';

end

The final code need not have connectivity, but it must have n, min, max, and avg degree as the inputs.

I would like to integrate the two. I see that degree(graph) can return the degree and I can discard the nodes that do not have the desired degree. But, I am unsure about how to ensure that the graphs that I construct have the degree between (min, max). Thanks in advance.

Also, it need not be a function, if having a function induces function call lags. I am not sure if calling the function and retrieving the values can introduce the time lag or not.

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!
## 5 Comments

## Direct link to this comment

https://www.mathworks.com/matlabcentral/answers/620593-how-to-construct-a-large-graph-1e5-that-has-max-min-and-avg-degree-using-the-logical-sparse-adj#comment_1074618

⋮## Direct link to this comment

https://www.mathworks.com/matlabcentral/answers/620593-how-to-construct-a-large-graph-1e5-that-has-max-min-and-avg-degree-using-the-logical-sparse-adj#comment_1074618

## Direct link to this comment

https://www.mathworks.com/matlabcentral/answers/620593-how-to-construct-a-large-graph-1e5-that-has-max-min-and-avg-degree-using-the-logical-sparse-adj#comment_1074633

⋮## Direct link to this comment

https://www.mathworks.com/matlabcentral/answers/620593-how-to-construct-a-large-graph-1e5-that-has-max-min-and-avg-degree-using-the-logical-sparse-adj#comment_1074633

## Direct link to this comment

https://www.mathworks.com/matlabcentral/answers/620593-how-to-construct-a-large-graph-1e5-that-has-max-min-and-avg-degree-using-the-logical-sparse-adj#comment_1077298

⋮## Direct link to this comment

https://www.mathworks.com/matlabcentral/answers/620593-how-to-construct-a-large-graph-1e5-that-has-max-min-and-avg-degree-using-the-logical-sparse-adj#comment_1077298

## Direct link to this comment

https://www.mathworks.com/matlabcentral/answers/620593-how-to-construct-a-large-graph-1e5-that-has-max-min-and-avg-degree-using-the-logical-sparse-adj#comment_1077448

⋮## Direct link to this comment

https://www.mathworks.com/matlabcentral/answers/620593-how-to-construct-a-large-graph-1e5-that-has-max-min-and-avg-degree-using-the-logical-sparse-adj#comment_1077448

## Direct link to this comment

https://www.mathworks.com/matlabcentral/answers/620593-how-to-construct-a-large-graph-1e5-that-has-max-min-and-avg-degree-using-the-logical-sparse-adj#comment_1077488

⋮## Direct link to this comment

https://www.mathworks.com/matlabcentral/answers/620593-how-to-construct-a-large-graph-1e5-that-has-max-min-and-avg-degree-using-the-logical-sparse-adj#comment_1077488

Sign in to comment.