2
$\begingroup$

Suppose we have 2 random graphs, each spatially embedded in a square plane, and vertices connected according to a distance criterion (or different degrees of nearest neighbour). I am trying to figure out if there's a way to create a 3D embedded graph by embedding our 2 graphs exactly on top of each other (their square embedding has same area), and wire the two stacks together by randomly creating edges between nodes of the two stacked graphs, based on nearest neighbours/distance criterion again.

Let us create our two 2D random graphs that we want to stack together to create a 3D graph:

SeedRandom[124]
g1 = RandomGraph[SpatialGraphDistribution[30, 0.3, 2], 
  VertexStyle -> Green]

enter image description here

SeedRandom[150]
g2 = RandomGraph[SpatialGraphDistribution[30, 0.3, 2], 
  VertexStyle -> Red]

enter image description here

Question:

  • How can we stack g1 and g2 on top of each other, separated by a given distance, and add random edges in this new 3rd dimension between the nodes (i.e. connecting nearby red-green nodes)?

Using SpatialGraphDistribution with d (dimension) set to $3$ does not produce the wanted setup as it distributes the nodes uniformly in the unit cube, instead of 2 separated parallel planes. But maybe if we can manually stack g1 and g2, then we can use NearestNeighborGraph to wire them together, but I haven't been able to get far with that yet.


Different attempts:

To ensure the layered (or in plane) stacking of the graphs in 3D, one can try and start from a 3d GridGraph:

grid3 = GridGraph[{5, 5, 5}, VertexLabels -> "Name"]
coords3 = GraphEmbedding[grid3, "SpringElectricalEmbedding", 3];

enter image description here

and one could try to rewire the edges randomly (with a given probability $p$) but according to a 1st,2nd... nearest neighbour criterion, but such specific rewiring scheme does not seem to exist built-in or in other libraries as far as I know. For instance, using IGraphM, one can rewire the 3D grid, but it rewires edges completely randomly without any constraints, e.g. after $10$ rewirings grid3 becomes:

IGRewire[grid3, 10, VertexCoordinates -> coords3]

enter image description here

But this approach does not seem promising, as not only we cannot (?) constrain the rewiring, the stacked layers are perfect lattices as opposed to random graphs.

$\endgroup$
5
$\begingroup$

Here's the one example of rewiring using NearestNeighborGraph:

SeedRandom[124]
g1 = RandomGraph[SpatialGraphDistribution[30, 0.3, 2], 
   VertexStyle -> Green];

I reindexed a graph to distinguish vertices.

SeedRandom[150]
g2 = IndexGraph[
   RandomGraph[SpatialGraphDistribution[30, 0.3, 2], 
    VertexStyle -> Red], 31];

vcoord1 = {##, 0} & @@@ GraphEmbedding[g1];   
vcoord2 = {##, .4} & @@@ GraphEmbedding[g2];

Wiring g1 and g2 based on given radius:

dist[{_, _, x_}, {_, _, x_}] := 100
dist[x_, y_] := EuclideanDistance[x, y]

wire = EdgeList[
   IndexGraph[
    NearestNeighborGraph[Join[vcoord1, vcoord2], {1, 1}, 
     DistanceFunction -> dist, DirectedEdges -> False]]];

Construct a new graph:

Graph3D[Range[60], Join[EdgeList[g1], EdgeList[g2], wire], 
 VertexCoordinates -> Join[vcoord1, vcoord2], 
 VertexStyle -> 
  Join[Thread[Range[30] -> Green], Thread[Range[31, 60] -> Red]]]

enter image description here

Stacking 3rd graph:

SeedRandom[180];
g3 = IndexGraph[
   RandomGraph[SpatialGraphDistribution[30, 0.3, 2], 
    VertexStyle -> Blue], 61];
vcoord3 = {##, .8} & @@@ GraphEmbedding[g3];
wire2 = EdgeList[
   IndexGraph[
    NearestNeighborGraph[Join[vcoord2, vcoord3], {1, 1}, 
     DistanceFunction -> dist, DirectedEdges -> False], 31]];

Graph3D[Range[90], 
 Join[EdgeList[g1], EdgeList[g2], EdgeList[g3], wire, wire2], 
 VertexCoordinates -> Join[vcoord1, vcoord2, vcoord3], 
 VertexStyle -> 
  Join[Thread[Range[30] -> Green], Thread[Range[31, 60] -> Red], 
   Thread[Range[61, 90] -> Blue]]]

enter image description here

|improve this answer|||||
$\endgroup$
  • $\begingroup$ Many thanks halmir! If I may ask 1-2 follow-up questions: i) 100 in dist is there just so that it's a large enough number to avoid redrawing edges among the nodes of either graphs g1 or g2? ii)Could you kindly explain how you came up with those parameters, 0.4 and 1 in NearestNeighborGraph? The embedding may not always be on unit square, so it might be useful to know how to re-adjust those params. iii) Is there a way to assign those nearest neighbors (in wire) with a probability $p?$ i.e. if $p=1$ we'd include all nearest neighbors, and $p<1$ a select of them will be created. $\endgroup$ – user929304 Aug 29 '19 at 13:21
  • $\begingroup$ @user929304 i) yes, for this example. It depends on coordinate bounds. ii) also depends on coordinates of graph. you could choose whatever you like. iii) maybe you could add RandomSample to select edges among wire? like RandomSample[wire, Ceiling[Length[wire] .8]] $\endgroup$ – halmir Aug 29 '19 at 14:49
  • $\begingroup$ Dear halmir, i hope it’s ok to ask a followup question after such a long time. If we were to wire the newly constructed graph (as shown in your solution), to a 3rd graph in a similar fashion, how would we proceed? That is, g1 is wired to g2 first (denoting it g12wired), then g3 is wired to g2 of g12wired, so g2 is being sadwiched. I’ve tried to define the coords of g3 as ‘ vcoord3 = {##, .8} & @@@ GraphEmbedding[g3];’ but fail to redefine ‘wire’ for stacking of 3 graphs now instead of 2. If time allows, any hints would be very helpful, thanks very much in advance and happy new year! $\endgroup$ – user929304 Jan 6 at 16:46
  • $\begingroup$ Many thanks for the update! In case you are interested, I've posted another related question, on how to sample the added edges according to a target distribution. e.g. in the above, the underyling deg. dist. of wire is Histogram[VertexDegree[wire], {1}, "Probability", AxesLabel -> {"degree", "probability"}] has a peak at 1 and decays to zero until deg=5. So the question is, how could we sample or define wire such that the so-defined deg. dist. is uniform or Poissonian for example. As always your input would be most appreciated. $\endgroup$ – user929304 Feb 29 at 15:40
  • $\begingroup$ Hi again halmir, I was wondering if you saw a way for how to incorporate kglr's idea in our wiring approach here. That is, to merge the two in order to create the stacking according to nearest-neighbor and with a resulting degree distribution close to the target distribution we consider. $\endgroup$ – user929304 Mar 10 at 15:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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