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

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 =
GraphComputationGraphJoin[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?

# TL;DR

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

RandomInteger[{houseNumber + 1, 2 houseNumber}, newRoadNumber]
}


# 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[{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 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;
g2 = CompleteGraph;

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.