MATLAB: Create random graph with limited degree

graph degreegraph theory

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?

Best Answer

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)

Related Solutions

MATLAB: Find all the possibles paths between 2 nodes in undirected graph

Test script

% Generate random undirect graph
% https://www.mathworks.com/matlabcentral/answers/563732
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);
% Test
plot(G);
st = randperm(n,2); % pick a random pair of nodes
p = AllPath(A, st(1), st(2)); ; % function defined in mfile below 
fprintf('--- test ---\n');
for k=1:size(p,1)
    fprintf('path #%d: %s\n', k, mat2str(p{k}));
end

Result for this graph, s=1, and t=10:

path #1: [1 6 10]
path #2: [1 9 3 4 5 8 10]
path #3: [1 9 3 8 10]
path #4: [1 9 8 10]

The result is still managable for n<=30, I get about few thousand paths listed with such random generated graph. Hard to know how the number of path scaled up with N if the degree of the graphe is bounded. My intuition is the number of paths more or less the number of partitions of N, according to Maranujan, it's ~ exp(sqrt(N)).

Put this on the mfile AllPath.m or at end of the test script above

%%
function p = AllPath(A, s, t)
% Find all paths from node #s to node #t
% INPUTS:
%   A is (n x n) symmetric ajadcent matrix
%   s, t are node number, in (1:n)
% OUTPUT
%   p is M x 1 cell array, each contains array of
%   nodes of the path, (it starts with s ends with t)
%   nodes are visited at most once.
if s == t
    p =  {s};
    return
end
p = {};
As = A(:,s)';
As(s) = 0;
neig = find(As);
if isempty(neig)
    return
end
A(:,s) = [];
A(s,:) = [];
neig = neig-(neig>=s);
t = t-(t>=s); 
for n=neig
    p = [p; AllPath(A,n,t)]; %#ok
end
p = cellfun(@(a) [s, a+(a>=s)], p, 'unif', 0);
end %AllPath

MATLAB: How to determine number of edges

Since every node seems to go to every node (even including itself), wouldn't it just be simply N*N/2 = 8*8/2 = 32?

Best Answer

Related Solutions

MATLAB: Find all the possibles paths between 2 nodes in undirected graph

MATLAB: How to determine number of edges

Related Question