generating a random graph under a particular case using MATLAB
2 views (last 30 days)
Show older comments
I want to generate a random graph using MATLAB with the following properties:
- the diameter (longest shortest path) of the graph is 2.
- having 21 vertices. i.e. odd number of vertices
- the degree of all vertices is 5 except at one vertex with degree 6.
Now my challenge is only the diameter in the following matlab code. The diameter of the graph must be 2. When we remove "max(max(distances(G)))==2" from while loop, the code will generate a quasi-regular graph with diameter 3. I was wondering if someone could help me? Thanks in advance!
function A = RandomRegularGraph(n, d)
clc;clear;close
n = 21; % Number of vertices
d = 5; %degree at all vertices, except at one vertex
matIter = 10;
%a list of open half-edges
U = repmat(1:n,1,d);
U(end+1)=U(end);
%the graphs adajency matrix
A=sparse(n,n);
%create empty graph
G=graph(A);
edgesTested=0;
repetition=1;
%continue until a proper graph is formed
while ~isempty(U) && max(max(distances(G)))==2 && repetition < matIter % max(max(distances(G)))==2 means diameter of a graph is 2
edgesTested = edgesTested + 1;
%chose at random 2 half edges
i1 = ceil(rand*length(U));
i2 = ceil(rand*length(U));
v1 = U(i1);
v2 = U(i2);
%check that there are no loops nor parallel edges
if (v1 == v2) || (A(v1,v2) == 1)
%restart process if needed
if (edgesTested == n*d)
repetition=repetition+1;
edgesTested = 0;
U = repmat(1:n,1,d);
U(end+1)=U(end);
A = sparse(n,n);
end
else
%add edge to graph
A(v1, v2)=1;
A(v2, v1)=1;
%remove used half-edges
U([i1,i2])=[];
end
%plot graph
G=graph(A);
end
%unlabeled graph plot
plot(G,'-','NodeLabel',{})
0 Comments
Answers (2)
Harsha Priya Daggubati
on 6 Apr 2020
Hi,
Can you elaborate on what is not turning out as expected for you?
2 Comments
Harsha Priya Daggubati
on 7 Apr 2020
Is this the entire code, I assume distances(G), gives the vector that consists of distances between adjacent vertices. But I cannot see G being intialised anywhere.
Harsha Priya Daggubati
on 8 Apr 2020
It would be easy to investigate if you can provide the 'distances' function you are using and explain the algorithm you are using to generate a graph with a specific diameter, given number of vertices and degree of each vertex.
golan pundak
on 9 Apr 2020
Hi,
If I understand correctly you are expecting the sampled graphs to have dimameter 2 with high probability (>0.1% lets say).
But this is not the case. Assuming 21 vertices with degree 5:
The chance of any given pair of vertices to have distance 1 is: 5/20 = 0.25
The chance of any given pair of vertices to have distance 2 is: (1 - 5/20) * (1 - nchoosek(14, 5) / nchoosek(19, 5)) = 0.75 * (1 - 0.17) = 0.62
So with chance 1 - 0.62 - 0.25 = 0.13 two given vertices have distance 3 or more.
From linearity of expectation we expect that there would be nchoosek(21, 2)*0.13 = 27.3 such pairs
So the chance of getting exactly 0 such pairs is very small (to formally prove it we need to compute variance, but you get the point).
So this is hopeless.
If you want to get a diameter 2 graph you need to sample from a much smaller class of graphs.
1 Comment
golan pundak
on 10 Apr 2020
Edited: golan pundak
on 10 Apr 2020
My previous comment explains why this method will fail to produce the graph you want. The vertex with degree 6 doesn't change this picture.
You can indeed construct such a graph, but you'll need a different kind of sampling (that takes the diameter into account).
See Also
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!