Mathematica 9 is now available
Services & Resources / Wolfram Forums / MathGroup Archive
-----

MathGroup Archive 2008

[Date Index] [Thread Index] [Author Index]

Search the Archive

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


  • Prev by Date: Re: RandomGraph
  • Next by Date: Re: Re: Mathematica 6 obtains imaginary eigenvalues for a Hermitian
  • Previous by thread: Re: RandomGraph
  • Next by thread: Mathematica