How to generate a RANDOM SIMPLE GRAPH using MATLAB ?

I want to to have an adjancecny matrix of a simple graph (i.e. no self loops and no multiple edges between vertices).

Code should take number of vertices and number of edges as input and generate an adjancecny matrix for a graph where

edges are chosen randomly.

Answer 1

[Paras Gupta]

Hi,

The following code illustrates how you can create a function to generate an adjacency matrix for a random simple graph with 'n' vertices and 'e' edges without any self-loops or multi-edges.

n = 7;
e = 15;
adjMatrix = randomSimpleGraph(n, e);
disp(adjMatrix)

     0     1     1     0     1     1     1
     1     0     0     0     0     1     0
     1     0     0     1     1     1     1
     0     0     1     0     1     0     1
     1     0     1     1     0     1     1
     1     1     1     0     1     0     1
     1     0     1     1     1     1     0

function adjMatrix = randomSimpleGraph(n, e)

    % A square matrix (nxn) with all elements (=1) except diagonal elements (=0)
    A = ones(n) - eye(n);
    
    % Create a graph from the above adjacency matrix
    temp = graph(A~=0);
    
    % Select a random permutation of 'e' edges from the total edges of the above matrix 
    edges = randperm(numedges(temp), e);
    
    % Create a graph from the random permutation of edges
    G = graph(temp.Edges(edges, :));
    
    % Get the adjacency matrix
    A = adjacency(G);
    
    % Convert the matrix from sparse to full storage
    adjMatrix = full(A);

end

You can refer to the documentation for ones, eye, graph, randperm, adjacency, and full for more details on the respective functions used in the above code.

Hope this helps!