Creating a Random Connected Subgraph

Question

I made this random graph/network in R:

set.seed(123)
library(igraph)

# Create random graph
graph <- erdos.renyi.game(21, 0.3, type=c("gnp", "gnm"), directed = FALSE, loops = FALSE)

Then, I tried to create a random connected subgraph:

# Get the edges of the random subgraph
random_edges <- sample(E(graph), 10)

# Create subgraph from the random edges
subgraph <- subgraph.edges(graph, random_edges)


par(mfrow = c(1,2))

# Plot the subgraph
plot(subgraph, main = "random subgraph")
plot(graph, main = "original graph")

My Question: When I look at the random subgraph, I see that "node 4" is connected to "node 10" - but in the original graph, "node 4" and "node 10" are not connected to each other.

Can someone please show me how to fix this?

Thanks!

Answer 1

I think a workaround is to add a name attribute to vertices before conducting induced.subgraph. Otherwise, the vertex "label" (to be shown in the plot of subgraph) is indexed differently, rather than keeping the same vid in the original graph.

---

For example, you can do

graph %>%
  set.vertex.attribute(name = "name", value = V(.)) %>%
  induced.subgraph(unique(c(ends(., random_edges))))

then you will obtain a subgraph like below

IGRAPH da87a26 UN-- 10 16 -- Erdos-Renyi (gnp) graph
+ attr: name (g/c), type (g/c), loops (g/l), p (g/n), name (v/n)
+ edges from da87a26 (vertex names):
 [1]  5--10  1--14  3--14  1--15 14--15  3--16 14--16 14--17  1--18  5--18
[11] 14--18 15--18 17--18  3--20 10--20 16--20

Answer 2

If you would like to have a subgraph using subgraph.edges, you should have the ids:

The edge ids of the edges that will be kept in the result graph.

You could get the IDs of the vertices using V like this:

set.seed(123)
library(igraph)

# Create random graph
graph <- erdos.renyi.game(21, 0.3, type=c("gnp", "gnm"), directed = FALSE, loops = FALSE)

# Get the edges of the random subgraph
# random_edges <- sample(E(graph), 10)
random_vertices <- sample(V(graph), 10)

# Create subgraph from the random edges
subgraph <- subgraph.edges(graph, random_vertices)

par(mfrow = c(1,2))

# Plot the subgraph
plot(subgraph, main = "random subgraph")
plot(graph, main = "original graph")

^{Created on 2023-03-11 with reprex v2.0.2}

Answer 3

You need to be very careful about what you mean by "random subgraph". The implication is that you want to produce each acceptable subgraph with equal probability. It is still an important question what kinds of "subgraphs" you consider acceptable.

Solving such problems is generally speaking mathematically hard. A different method would be needed for each type of constraint you put on your subgraphs. For this reason, it is unlikely that you will find ready-to-use methods in existing software libraries.

Of course you can always use rejection sampling, i.e. keep generating subgraphs in terms of randomly chosen edges until you find a connected one, but this will be extremely inefficient unless you choose a fairly large number of edges, probably something on the order of n log n where n is the vertex count.

---

For some practical use cases one can relax the requirement of uniform sampling (i.e. that each subgraph is produced with equal probability). But then be very careful with what conclusions you draw from your numerical experiment.

A fairly common way of obtaining random connected subgraphs, without the guarantee of uniformity, is to do a random walk from a random starting point, and record the edges or vertices you traverse (depending on whether you want induced subgraphs). See the random_walk() and random_edge_walk() functions in igraph.