I am using igraph from R. I know we can make a subgraph with selected vertices but if those nodes aren’t directly connected, there won’t be an edge in the new subgraph. Is there a way to make a subgraph which creates an edge between two nodes if there are other nodes (that are not a part of the vertex list) indirectly connecting those two nodes? For example, if I have a graph which has the following edges: E-F F-G And my vertex list contains E and G, how can I create a new subgraph that creates that edge E-G? Thank you!!!
4 Answers
One way to find neighbors that are two steps away is to multiply the adjacency matrix with itself (see comments here for example).
First create the graph described in the question:
library(igraph)
g <- graph_from_literal(E--F, F--G)
Then take the adjacency matrix (m) and multiply it with itself.
m <- get.adjacency(g, sparse = F)
m2 <- m %*% m
Built new graph from resulting adjacency matrix and remove all vertices that have a degree of 0 (no second-degree neighbor):
g2 <- graph_from_adjacency_matrix(m2, diag = F, mode = "undirected")
induced_subgraph(g2, degree(g2) > 0)
#> IGRAPH 089bf67 UN-- 2 1 --
#> + attr: name (v/c)
#> + edge from 089bf67 (vertex names):
#> [1] E--G
Created on 2022-08-26 with reprex v2.0.2
Building upon the suggestions in the comments, I arrive at:
require(igraph)
set.seed(1)
g <- erdos.renyi.game(2^6, 1/32)
V(g)$name <- seq(vcount(g))
filter <- c(7,22, 1, 4, 6)
amg <- g[] # adjacency matrix g
clg <- clusters(g)$membership # strongly connected components
amtc <- clg[row(amg)] == clg[col(amg)] # adjacency matrix of transitive closure
dim(amtc) <- dim(amg)
gtc <- simplify(graph.adjacency(amtc, mode="undirected")) # transitive closure of g
V(gtc)$name <- V(g)$name
isg <- induced_subgraph(gtc, filter)
plot(isg)
However this solution is not feasible if g is large and the subgraph significantly smaller.
If subgraph << original graph then:
require(igraph)
set.seed(1)
g <- erdos.renyi.game(2^6, 1/32)
V(g)$name <- seq(vcount(g))
filter <- c(1, 4, 6, 7, 22, 25)
stopifnot(!is.directed(g)) # assume undirected graph
mscc <- components(g)$membership[filter] # membership strongly connected components
amfi <- outer(X=mscc, mscc, FUN = "==")*1 # cross product = 1, when equal
fitc <- simplify(graph.adjacency(amfi, mode="undirected")) # transitive closure of filter in g
plot(fitc)
Building on Szabolcs, note that connect(g, vcount(g)) computes the transitive closure of g. However not suitable for larger graphs (vcount > 8192).
require(igraph)
g <- make_graph(~ E-G, G-F)
fi <- c("E", "F")
system.time(tcg <- connect(g, vcount(g)) )
sg <- subgraph(tcg, V(tcg)[fi])
sg
Related