# Fast randomization of a graph, while keeping the graph connected

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!

-
What is the input Q? An adjacency matrix? Also, is there any reason not to simply generate random graphs with n vertices and l edges? You could then discard the ones that are not connected, until you have r such graphs. Or would that not be sufficiently efficient? – Daniel Lichtblau Jan 15 '14 at 16:34
What do you mean by "randomizing a graph"? This is not very clear. Do you want to just generate random graphs with a given number of vertices and edges and make sure they're connected? – Szabolcs Jan 15 '14 at 22:38
@DanielLichtblau: Yes, Q is an adjacency matrix. To generate and discard is not very efficient, especially for large sparse networks. – sam84 Jan 16 '14 at 9:19
@Szabolcs: The most simple randomization is to generate graphs with fixed N, L and connected. But I can also add constraint. For example, generate a random graph, with fixed N, L, connected and with a given degree sequence {k1,k2,..,kN}. The function DegreeGraphDistribution that should do this, is terribly slow for large graph. – sam84 Jan 16 '14 at 9:22
@sam84 My point is that both this and the incidence matrix question you posted are not very clearly phrased. Please try to describe very precisely what you are asking. Your comment did't really answer my question: what exactly are you asking for here? Graph sampling with constraints is far from a trivial problem and in most cases there won't be a simple and fast solution. – Szabolcs Jan 16 '14 at 14:51

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]


-
Are you certain that this method will generate a given graph with the same probability as a (filtered) RandomGraph? Won't the distribution be biased? – Szabolcs Jan 15 '14 at 22:43
@Szabolcs It will be surely biased at its current state. But improvement can be made I guess...Whats your say? – PlatoManiac Jan 15 '14 at 22:55
Bigger problem if #vertices > #edges+1... – Daniel Lichtblau Jan 16 '14 at 0:42
@PlatoManiac Why the graphs are biased? – sam84 Jan 16 '14 at 9:35
@sam84 "biased" = not all graphs are generated with equal probability by this algorithm. But your question was not clear enough to tell us what distribution you were looking for and what kind of bias you can live with. – Szabolcs Jan 16 '14 at 14:53

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!

-
+1 for starting with a tree. – Silvia May 25 '15 at 15:58