How to create a random graph that is connected?
15 views (last 30 days)
Show older comments
Tirthankar Chakraborty on 28 Mar 2023
Answered: Christine Tobler on 28 Mar 2023
I am using the following code for generating a random graph with 'n' nodes and 'E' edges.
n = 50;
E = 100;
adj = spalloc(n, n, E);
idx = randperm(n * n, E);
adj(idx) = 1;
adj = min( adj + adj.', 1);
G = graph(adj,'omitselfloops');
The problem is that sometimes I end up with disconnected nodes or a graph with more than one connected component.
How can I make sure that my random graph (without repeated edges and self loops) is connected?
Christine Tobler on 28 Mar 2023
If an undirected graph is connected, it must contain at least one path that visits each node at least once.
You could construct an initial matrix where the second off-diagonal (adj(1, 2), adj(2, 3), ..., adj(n-1, n)) is always nonzero, and fill in the rest of the matrix randomly with E-n other edges. After that, you would choose a random permutation of the nodes (ind = randperm(n); adj = adj(ind, ind);), which should reach any possible random and completely connected graph with the same probability.
Find more on Graph and Network Algorithms in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!Start Hunting!