Re: RandomGraph
- To: mathgroup at smc.vnet.net
- Subject: [mg86212] Re: RandomGraph
- From: mcmcclur at unca.edu
- Date: Thu, 6 Mar 2008 02:57:34 -0500 (EST)
- References: <fqlmrq$jh4$1@smc.vnet.net>
On Mar 5, 3:50 am, Gaudium <nesea... at gmail.com> wrote:
> How can I construct a directed random graph with exactly 12 vertices
> and 31 edges, where the indegrees of the vertices are {1, 2, 2, 1, 4,
> 3, 2, 3, 5, 5, 2, 1} and outdegrees of the vertices are {2, 1, 1, 2,
> 1, 1, 5, 5, 2, 7, 3, 1} respectively?
We'll represent each edge as a rule: v1 -> v2.
We then generate a list of all possible v1s and
v2s, duplicating entries adjacent to multiple
edges. Finally, we pair up the v1 set with a
random permutation of the v2 set. Here's the
result.
inDegrees={1,2,2,1,4,3,2,3,5,5,2,1};
outDegrees={2,1,1,2,1,1,5,5,2,7,3,1};
ins = Flatten[MapIndexed[Table[#2, {#1}] &,
inDegrees]];
outs = Flatten[MapIndexed[Table[#2, {#1}] &,
outDegrees]];
G = Inner[Rule, outs, RandomSample[ins], List];
GraphPlot[G, VertexLabeling -> True,
DirectedEdges -> True]
The above graph will frequently have self-loops.
We can avoid the self-loops, if desired, by
generating the random sample of in vertices
more carefully. Here's one approach that works
most of the time given your degree sequences.
ins = Flatten[MapIndexed[Table[#2, {#1}] &,
inDegrees]];
outs = Flatten[MapIndexed[Table[#2, {#1}] &,
outDegrees]];
ins2 = {};
addIn[n_] := Module[{in},
in = RandomChoice[Select[ins, # != outs[[n]] &]];
ins2 = Append[ins2, in];
ins = Delete[ins, First[Position[ins, in]]];];
addIn /@ Range[Length[outs]];
G = Inner[Rule, outs, ins2, List];
GraphPlot[G, VertexLabeling -> True,
DirectedEdges -> True]
This works by moving points one at a time from
ins to ins2, always making sure that the new point
in ins2 doesn't match the corresponding point in
outs. This can ultimately fail near the end,
though, but there is a warning and you can just
try again.
Mark