How to generate random graph of n vertices with random connections in matlab

Hi I am interested in creating random undirected graph with n vertices and with random connections. This generated graph has to display its adjacency connections in a nxn matrix.I have tried this code but it is not working for my requirement.

n=input('No. of vertices')
     c=input('Random connections')
     MM=0;   %arbitrary starting value
      all_nums=1:n;

        while MM ~=n*c

            M = sparse([],[],[],n,n,n*c);
            ctin = zeros(1,n);

            for ii=1:n
                noconnect=ctin>=c;
                noconnect(ii)=true;

                rem_nums = all_nums(~noconnect); % remaining numbers
                rp=randperm(n-sum(noconnect));
                rp = rem_nums(rp); % remaining numbers, hussled

                if numel(rp)<c
                    break
                else
                    r=rp(1:c);
                end
                M(ii,r)=1;
                ctin(r)=ctin(r)+1;
            end
            MM=sum(ctin);
        end
    end
       A= adjacency(M)

Answer 1

[Luis De Medeiros]

You can create an adjacency matrix with random 1's and 0's by doing the following:

G = round(rand(n));
G = triu(G) + triu(G,1)';
G = G - diag(diag(G));

[SIVAKUMAR V]

Random adjacency matrix does not works for my problem. Since the number of 1's in the row has been increasing as the size of input n increases. In real graph scenario only limited number of adjacency will be forming.

[Walter Roberson]

Insufficient information about the required properties. Is every vertex to be connected? What is the minimum vertex degree? What is the maximum vertex degree? Is it necessary to specifically create a graph with no disconnected cycles? Is it necessary to specifically create a graph that has no cut-edge? Is it necessary to specifically create a graph that has no cut-vertex? Are the random connections to be uniformly distributed or some other distribution (for example if the difference in vertex number correlates to the distance between the vertices then should "closer" vertices be favoured over "further" vertices?)

[SIVAKUMAR V]

I need a random undirected graph to be created with specified n vertices and E number links.

[Walter Roberson]

Please expand on what you mean by "E number links". Do you mean a total of E edges across the entire graph? Would a valid random graph be one in which all E edges were connected to the first vertex and the other vertices were either not connected or were connected to the first vertex?

[SIVAKUMAR V]

Yes E represents number of links across the graph. My expectation is need to generate a sensor network graph in matlab.

Answer 2

[Walter Roberson]

adj = spalloc(n, n, E);
idx = randperm(n * n, E);
adj(idx) = 1;
adj = min( adj + adj.', 1);

[SIVAKUMAR V]

How to display this in matrix format

[Walter Roberson]

Displaying it in matrix format is not advised for large matrices. The code here presumes that your number of sensors might be in the millions, and displaying such a matrix is not practical (and might fill up memory to create a displayable form.)

If your n is fairly small, you could use

full(adj)

and consider using spy()

[SIVAKUMAR V]

My identity should be always zeros. But in this code some identity is 1.

[SIVAKUMAR V]

The identity matrix should be always zeros like shown below adj =

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

[Walter Roberson]

idx = randperm(n * n, E+n);
idx(ismember(idx, 1:n+1:n*n)) = [];
idx = idx(1:E);

[SIVAKUMAR V]

It works for an identity zeros. But every columns in matrix should have at least one 1's. While running for large nodes (i.e n=100). fews columns doesn't have one 1's.

[SIVAKUMAR V]

% code for checking atleast one 1's in every column
n= input('no. of Nodes')
E= input('no. of Links')
adj = spalloc(n, n, E);
idx = randperm(n * n, E+n);
idx(ismember(idx, 1:n+1:n*n)) = [];
idx = idx(1:E);
adj(idx) = 1;
adj = min( adj + adj.', 1);
adj
matrix = full(adj)
Deg=sum(matrix)

[Walter Roberson]

Requiring that every column should have at least one 1's is a minimum vertex degree of 1, but you have already indicated that is not required when you answered in terms of just the total number of edges E in response to my questions at http://www.mathworks.com/matlabcentral/answers/297615-how-to-generate-random-graph-of-n-vertices-with-random-connections-in-matlab#comment_382476

We are not able to solve problems with contradictory requirements.

[Shilpi Mishra]

How to form adjacency matrix for undirected graph for 'n' nodes that just requires minimum vertex degree of 1?

[Walter Roberson]

n = 7;

nv = 1:n;
temp = randi(n-1, 1, n);
mask = temp >= nv;
temp(mask) = temp(mask) + 1;
adj = sparse(nv, temp, 1, n, n);
size(adj)

ans = 1×2

7 7

adj = max(adj, adj.');

full(adj)

ans = 7×7

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

G = graph(adj);
plot(G)

[idris cinemre]

Is it possible to generate random RAN graph like attached fig. red dots indicate the RUs’ locations; black dots the routers/switches, green dot the CU location. RUs are only connected to a router, routers can be connected to each other and CU.

[Walter Roberson]

First generate an appropriate connected graph for the Routers and switches only.

Then generate a bunch of other points, and calculate their nearest neighbour among the routers, and connect them to that neighbour.

Answer 3

[Steven Lord]

Take a look at the sprand and sprandsym functions.