How can I join two graphs with a specific number of new edges, connected randomly between the graphs?

Question

I would like to create one large graph with two communities that have high internal connectivity and very weak (though tunable) connectivity between them. I am attempting to create two fully connected graphs and then join them together with a specific number of new edges, which can be connected at random to vertices in each graph.

So far, I'm just able to create the two graphs

NN = 10;
SNsub1 = RandomGraph[{NN/2, Binomial[NN/2, 2]}];
SNsub2 = RandomGraph[{NN/2, Binomial[NN/2, 2]}];

and then fully join them to each other (all vertices in one get connected to all vertices in the other):

SNtest = 
 GraphComputation`GraphJoin[SNsub1, SNsub2, VertexLabels -> "Name", 
  ImagePadding -> 10, GraphLayout -> "MultipartiteEmbedding"]

Is there a way to do a `partial random join' between them?

Alternatively, is there some other way to achieve my real goal: a graph with two communities in which I can reliably tune the ratio of the intracommunity and intercommunity connectivities?

Answer 1

TL;DR

SeedRandom["MMA"]
houseNumber = 5;
roadNumber = Binomial[houseNumber, 2] - 2;(*Complete Graph is -0*)
houses = RandomGraph[{houseNumber, roadNumber}, 2];
city = GraphDisjointUnion @@ houses

newRoadNumber = 3;
newRoads = UndirectedEdge @@@ Transpose@{
  RandomInteger[{1, houseNumber}, newRoadNumber], 
  RandomInteger[{houseNumber + 1, 2 houseNumber}, newRoadNumber]
}
newCity = EdgeAdd[city, newRoads]

The long version

To begin we make two communities with random connections of a given number of houses houseNumber and roads roadNumber with RandomGraph and bring them together with GraphDisjointUnion.

houses = RandomGraph[{houseNumber, roadNumber}, 2];
city = GraphDisjointUnion @@ houses

Then we randomly pick a number of houses from each community equal to the number of new roads we want to add newRoadNumber, and, in some sense, "plan the road" with UndirectedEdge (with a two-way street*).

newRoads = UndirectedEdge @@@ Transpose@{
  RandomInteger[{1, houseNumber}, newRoadNumber], 
  RandomInteger[{houseNumber + 1, 2 houseNumber}, newRoadNumber]
  (*This numbering is chosen due to how the union relabels the vertices*)
}

Then the city actually makes the roads with

newCity = EdgeAdd[city, newRoads]

And we can even easily go backwards and see our starting communities (and any new ones that have formed!) with CommunityGraphPlot

CommunityGraphPlot@newCity

Answer 2

I am attempting to create two fully connected graphs and then join them together with a specific number of new edges, which can be connected at random to vertices in each graph.

You can use my IGraph/M package to create a random bipartite graph with $m$ edges between the two partitions.

To achieve precisely what you requested, you can do:

Needs["IGraphM`"]

g1 = CompleteGraph[5];
g2 = CompleteGraph[7];

GraphUnion[
 GraphDisjointUnion[g1, g2],
 IGBipartiteGameGNM[VertexCount[g1], VertexCount[g2], 10]
]

Alternatively, is there some other way to achieve my real goal: a graph with two communities in which I can reliably tune the ratio of the intracommunity and intercommunity connectivities?

IGraph/M contains several graph generators which fit this description. The most straightforward one is the stochastic block model.

For example, to create a graph with two partitions of size 100 and 50, where the intra-partition connection probabilities are 0.1 and 0.15 respectively, and the inter-partition connection probability is 0.01, you can do:

IGStochasticBlockModelGame[{
   {0.1, 0.01},
   {0.01, 0.15}
  }, {100, 50}]

I like to enter this in matrix format:

IGPreferenceGame is very similar, but the partition of each vertex is assigned randomly, based on a weight vector.

IGPreferenceGame[100, {2, 1} (* partition assignment weights *), 
  {
   {0.1, 0.01},
   {0.01, 0.15}
  }]

There are also directed versions, IGAsymmetricPreferenceGame for asymmetric connectivity between partitions, as well as several other more complicated random graph generators which are capable of creating graphs with a community structure. Check the documentation to learn more.