CODEWITHSUNDEEP
rgraphigraph
Eunice Choi
Eunice Choi

Reputation: 29

R igraph make “subgraph” from igraph object from list of vertices, infer edges between selected vertices if there are connected nodes in original

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!!!

Upvotes: 2

Views: 736

Answers (4)

clp
clp

Reputation: 1528

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

Upvotes: 1

clp
clp

Reputation: 1528

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)

Upvotes: 1

clp
clp

Reputation: 1528

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.

Upvotes: 1

Ben Nutzer
Ben Nutzer

Reputation: 1163

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

Upvotes: 3

Related Questions