Context and example:

Suppose we have 2 graphs $g_1,g_2$ that we connect together by introducing edges between each node of $g_1$ and its corresponding nearest neighbors within the second graph $g_2.$ This process does not perturb the edgelists of the original graphs (i.e., the edges that defined e.g. $g_1$ are not removed or rewired). The nearest neighbor is defined here according to the Euclidean distance between the nodes. In a previous post, halmir provided a very neat solution to this problem by using the NearestNeighborGraph function in order to introduce the new edges, here's an example:

The two graphs before connecting them with one another:

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

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

The vertex coordinates of the embedding and our distance function:

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

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

And the newly introduced edges between g1,g2:

wire = EdgeList[
    NearestNeighborGraph[Join[vcoord1, vcoord2], 2, 
     DistanceFunction -> dist, DirectedEdges -> False]]];

The 2 argument in the above means: each node is connected to 2 nearest neighbors.

And visualised with the g1 nodes colored red and g2 colored green:

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


What I am trying to figure out is, how to sample/define wire in the above, that is the edges introduced between the two graphs, such that a target degree distribution is obtained? In other words, if we were to treat the newly introduced edges as a graph by itself, then it has a corresponding degree distribution, e.g. in the above example that is given by the following distribution:

Histogram[VertexDegree[wire], {1}, "Probability", 
 AxesLabel -> {"degree", "probability"}]

enter image description here

We could randomly sample edges from the list wire with a probability p:

wiresampled = RandomSample[wire, Ceiling[Length@wire*p]];

but this doesn't allow us to sample a desired degree distribution/sequence from wire, which might for example be uniform (all degrees constant) or Poisson distributed.

On the one hand, using functions such as IGRewire from the IGraph/M package is not obvious either, as the rewiring would ignore the nearest neighbor requirement. Moreover, as far as I know, the reverse graph generation functions such as IGRealizeDegreeSequence do not allow for nearest-neighbor specifications. On the other hand, the built-in DegreeGraphDistribution cannot be used with the function NearestNeighborGraph, or at least I don't see how the two can be married in the above scheme.

  • In short then, is there a way we could use the NearestNeighborGraph routine while also obtaining a desired degree distribution for the newly introduced edges (between g1,g2)? In other words, how can we sample the nearest neighbor edges added between g1 and g2 according to a degree distribution?

1 Answer 1

bipartiteWire[ga_Graph, gb_Graph, d1_, d2_] := 
  Module[{am = Array[\[FormalA], VertexCount /@ {ga, gb}], 
       dm = Join @@ DistanceMatrix @@ (GraphEmbedding /@ {ga, gb})}, 
   NMinimize[{dm.(Join @@ am), 
      And @@ Join[Thread[Total[am] == d2], 
        Thread[Total[am, {2}] == d1], 
        Thread[0 <= Join @@ am <= 1],
        {Element[Join@@am, Integers]}]}, 
     Join @@ am][[2]] // 
   Cases[HoldPattern[\[FormalA][i_, j_] -> 1] :> UndirectedEdge[i, VertexCount[ga] + j]]]


Constant degree sequences:

vd1 = ConstantArray[2, VertexCount[g1]];
vd2 = ConstantArray[2, VertexCount[g2]];

wire2 = bipartiteWire[g1, g2, vd1, vd2];

Tally[VertexDegree @ wire2]

{{2, 60}}

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

enter image description here

Tally[VertexDegree @
  bipartiteWire[g1, g2, ConstantArray[3, VertexCount[g1]], 
   ConstantArray[3, VertexCount[g2]]]]

{{3, 60}}

Examples with a random degree sequences:

rvd1 = RandomInteger[{1, 5}, VertexCount[g1]];
SortBy[First] @ Tally @ rvd1

{{1, 7}, {2, 5}, {3, 4}, {4, 6}, {5, 8}}

rvd2 = RandomSample[rvd1];

SortBy[First] @ Tally[VertexDegree @ bipartiteWire[g1, g2, rvd1, rvd2]]

{{1, 14}, {2, 10}, {3, 8}, {4, 12}, {5, 16}}

rvd1 = RandomInteger[{1, 5}, VertexCount[g1]];
SortBy[First] @ Tally @ rvd1

{{1, 6}, {2, 8}, {3, 6}, {4, 3}, {5, 7}}

rvd2 = RandomSample @RandomChoice[IntegerPartitions[Total@rvd1, {30}, Range[5]]];
SortBy[First] @ Tally @ rvd2

{{1, 1}, {2, 13}, {3, 7}, {4, 6}, {5, 3}}

SortBy[First] @ Tally[VertexDegree @ bipartiteWire[g1, g2, rvd1, rvd2]]

{{1, 7}, {2, 21}, {3, 13}, {4, 9}, {5, 10}}

  • 1
    $\begingroup$ @user929304, this is a straightforward constrained minimization formulation forcing vertex degrees to match the input degree sequences and minimizing the total distance between connected vertices. The error message may be due previously defined a. See if changing ` a` to \[FormalA fixes the issue. $\endgroup$
    – kglr
    Commented Mar 3, 2020 at 5:34
  • 1
    $\begingroup$ @user929304, don't know how \[DoubleStruckCapitalZ] got into your code, but it should be replaced with Integers. $\endgroup$
    – kglr
    Commented Mar 3, 2020 at 10:48
  • 1
    $\begingroup$ Same it's really puzzling, I have literally copied your code for the module after which I define g1 and g2 exactly like in my post, then vd1, vd2 are assigned as you have and finally I evaluate wire2 = bipartiteWire[g1, g2, vd1, vd2]; Tally[VertexDegree@wire2] which leads to the said error. Could you please kindly re-test the posted code on your end again? $\endgroup$
    – user52181
    Commented Mar 3, 2020 at 11:50
  • 1
    $\begingroup$ @user929304, please try the new version. The original code works without issue in version 11.3.0 (Windows 10). Looks like there has been some update to NMinimize in version 12.0 so i got the same error as you did in version 12.0 (Wolfram Cloud). The updated version works in version 12.0 and version 11.3. $\endgroup$
    – kglr
    Commented Mar 3, 2020 at 12:16
  • 1
    $\begingroup$ Indeed that has resolved the problem, well spotted and thank you very much! I can now test the approach for bigger graphs and different degree dists, I'll get back to you asap regarding the results! $\endgroup$
    – user52181
    Commented Mar 3, 2020 at 13:02

Your Answer

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