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:
SeedRandom[124]
g1 = RandomGraph[SpatialGraphDistribution[30, 0.3, 2],
VertexStyle -> Green];
SeedRandom[150]
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[
IndexGraph[
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]]]
Question
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"}]
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
NearestNeighborGraphroutine while also obtaining a desired degree distribution for the newly introduced edges (betweeng1,g2)? In other words, how can we sample the nearest neighbor edges added betweeng1andg2according to a degree distribution?
