Create random graph with limited degree

16 views (last 30 days)
Sara on 12 Jul 2020
Commented: Sara on 13 Jul 2020
I want to create random and an undirected graph where the maximum degree of each node in the graph = 4, we can have in the graph nodes with the degree 2,3 or even 4 but none of them has a degree greater than 4, in other words, the degree of each node is between 1 and 4.
anyone can help?

Bruno Luong on 13 Jul 2020
n = 10; % number of nodes
maxDeg = 4;
M=rand(n);
M=0.5*(M+M');
S1=sort(M,1,'descend');
S2=sort(M,2,'descend');
T=max(S1(maxDeg,:),S2(:,maxDeg));
A=M>=T;
G=graph(A)
plot(G)

1 Comment

Sara on 13 Jul 2020
Thank you verry much

Christine Tobler on 13 Jul 2020
You could start by just making an undirected graph, and then go through each node and compute its degree. If the degree is larger than 4, remove some of the edges connecting to that node at random.
Do you need it to be "uniformly" random, and if yes in which way?

1 Comment

Sara on 13 Jul 2020
I will try that thank you verry much