generating a random graph under a particular case using MATLAB

I want to generate a random graph using MATLAB with the following properties:

1. the diameter (longest shortest path) of the graph is 2.
2. having 21 vertices. i.e. odd number of vertices
3. 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',{})

Answer 1

[Harsha Priya Daggubati]

Hi,

Can you elaborate on what is not turning out as expected for you?

[Harsha Priya Daggubati]

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]

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.

Answer 2

[golan pundak]

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.

[golan pundak]

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).