5
$\begingroup$

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?

$\endgroup$

2 Answers 2

4
$\begingroup$

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

enter image description here

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]

enter image description here

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

CommunityGraphPlot@newCity

enter image description here

$\endgroup$
4
$\begingroup$

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:

enter image description here

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.