Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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!

share|improve this question
    
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 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 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 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 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 at 14:51

2 Answers 2

up vote 3 down vote accepted

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}

enter image description here

Above algo:

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

{2.828562, Null}

enter image description here

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;

enter image description here

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]

enter image description here

share|improve this answer
    
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 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 at 22:55
    
Bigger problem if #vertices > #edges+1... –  Daniel Lichtblau Jan 16 at 0:42
    
@PlatoManiac Why the graphs are biased? –  sam84 Jan 16 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 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!

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.