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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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$
2
  • $\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$
    – user52181
    Aug 29, 2019 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, 2019 at 14:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.