Fast randomization of a graph, while keeping the graph connected

Question

I'm looking for a very efficient method for randomizing graph of a given size (N nodes, L links), but keeping them connected.

Assume you have the adjacency matrix A of a given connected graph. You want to generate R (usually a big number) random adjacency matrices Aran1,Aran2,...AranR, with the same N, L, AND connected.

I did the following code, I'm looking for a more efficient one.

randomization[Q_] := 
  Module[{Aran = {0, 0}},
    While[
      Length[Select[Total[Aran], # == 0 &]]> 0, 
      Aran = Partition[Nest[RandomSample, Flatten[Q], 10], Dimensions[Q][[2]]]
    ]
];

Thanks!

Answer 1

As Daniel pointed out you should not have much problem tricking the default RandomGraph with a While type loop. However the problem you may face is when the number of vertices and edges are close compared to their absolute value. For large number of vertex and fixed edges of same order the above method fails. Also the timing will be pretty unpredictable for a given vertex-count and edge-count. For such case you can use the following algorithm.

select[sub_Graph] := Module[{found, ed, sel, val},
   found = {};
   ed = EdgeList[sub];
   While[Length@found == 0, 
    If[TreeGraphQ[sub] === True, sel = 0; 
     val = RandomChoice@VertexList[sub]; Break[]];
    sel = RandomChoice[ed];
    If[EdgeConnectivity[EdgeDelete[sub, sel]] === 0, 
     ed = DeleteCases[ed, sel], AppendTo[found, sel]; 
     val = RandomChoice@Flatten@(List @@@ found)]
    ];
   {val, If[sel === 0, sub, EdgeDelete[sub, sel]]}
   ];
combine[g1_Graph, g2_Graph] := Module[{edge, graphs},
   {edge, graphs} = Transpose[select /@ {g1, g2}];
   EdgeAdd[GraphUnion @@ graphs, UndirectedEdge @@ (edge)]];
nRandomGraph[{vertex_Integer, edge_Integer}] /; edge >= vertex - 1 := 
  Module[{comps, list, g},
   g = RandomGraph[{vertex, edge}];
   If[GraphQ[g] === True,
    comps = ConnectedComponents[g];
    list = Subgraph[g, #] & /@ comps;
    Fold[combine[#1, #2] &, First@list, Rest@list]
    ]
   ];

Testing the above function to generate $100$ graphs with fixed edge and vertex count.

While loop:

n = 100;
list = {};
While[Length@list =!= n,g = RandomGraph[{57, 66}]; 
   If[ConnectedGraphQ[g] == True,AppendTo[list, g]]]; // AbsoluteTiming

{18.411692, Null}

Above algo:

mList = Table[nRandomGraph[{57, 66}], {n}]; // AbsoluteTiming

{2.828562, Null}

A bigger example where the While method kept on running for ever...

nRandomGraph[{557, 900}]; // AbsoluteTiming

{17.551914, Null}

Now lets look at the vertex degree distribution of both lists of generated graphs.

pdfs = Module[{data = VertexDegree [#]},
    smD = SmoothKernelDistribution[data]; PDF[smD, x]] &;
smdis = pdfs /@ mList;
smdisW = pdfs /@ list;

In the above we are plotting those distribution together along with their respective mean in rainbow colors. The solid lines are for graphs that the above algorithm generates. The lines with opacity are using While and RandomGraph functionality of Mathematica. Hope this gets you going!

Bias:

You can see the bias of above algorithm compared to Mathematica default RandomGraph. We draw the default pdf in dark red line. For the above algorithm $5000$ graph sample was taken and the distribution was estimated. This pdf is the thick line.

uniDis[n_, m_] := GraphPropertyDistribution[VertexDegree[g, v],
g \[Distributed] UniformGraphDistribution[n, m]];
pdfs = Module[{data = VertexDegree[#], smD}, 
    smD = SmoothKernelDistribution[data]; PDF[smD, x]] &;
smdis = pdfs /@ mList;
Plot[Evaluate@{PDF[uniDis[57, 66], x], Mean@smdis}, {x, 0,10}, PlotRange -> All, 
 PlotStyle -> {{Thick, Darker@Red}, {Thickness@.01,Directive[Red, Opacity[.4]]}}
 ,Filling -> {1 -> {2}},FillingStyle -> LightOrange, Axes -> None, Frame -> True]

Answer 2

Here is an algorithm that should be easy to implement and rather fast (linear time).

Generate a random tree as follows:

Start : no edges. All nodes are said to be non-tree nodes. Select a node at random and make it a tree-node.

While there are non-tree nodes left : Select a tree-node and a non-tree node, each at random, add the corresponding edge and make the non-tree node a tree-node

Once you have a tree you are guaranteed connectivity. Then you can start adding random edges (pairs of randomly selected nodes) as you wish (you may even add the edges of a RandomGraph. (mind the duplicate edges unless you want a multigraph).

Any connected graph can be generated this way. Coding may be tedious but should be straightforward!