How to Split an Igraph into Connected Subgraphs

How to split an igraph into connected subgraphs?

You could calculate the connected components of your graph by using:

clusters(g)
# $membership
# [1] 1 1 1 1 1 1 2 2 3 1
#
# $csize
# [1] 7 2 1
#
# $no
# [1] 3

Or you could create a separate graph for each component of your graph by using:

dg <- decompose.graph(g) # returns a list of three graphs
plot(dg[[1]]) # plot e.g. the 1st one

Sample Image

How to split an igraph into select connected subgraphs?

Another way would be to use breadth-first search:

g <- set.vertex.attribute(g,'name',index=V(g),as.character(1:vcount(g)))
#select nodes of interest:
nodes.of.interest <- c(2,9)
#find subgraphs that contain selected nodes
sel.nodes <- bfs(g ,root = nodes.of.interest ,unreachable = FALSE)$order
#remove additional nodes:
g.sub <- induced.subgraph(g , vids = sel.nodes[!is.na(sel.nodes)])
plot(g.sub)

Sample Image

Splitting a large network into many subgraphs using igraph

Something like this?

library(igraph)

net <- erdos.renyi.game(n= 100, p = .05) # generate random graph
class_id <- sample(1:5, 100, replace = T) # generate random groups

# create list of group memberships
class_id_list <- lapply(unique(class_id), function(i,j){
which(j %in% i)},
j = class_id)

# extract subnets based on group memberships
split.net <- lapply(class_id_list, function(net, v){
induced_subgraph(net, vids = v)
},
net = net)

Break up graph into smallest sub-components of 2-nodes or greater

You say you want the "smallest subcomponents of 2 nodes of greater", and that your example has the "smallest possible subcomponents". But what you actually meant is the largest possible subcomponents such that the removal of any single node would create no further sub-components, right? Otherwise you could just separate the graph into a collection of all of the 2-graphs.

I believe, then, that your problem can be described as finding all "biconnected components" (aka maximal biconnected subgraphs of a graph): https://en.wikipedia.org/wiki/Biconnected_component

As you said in the comments, igraph has the function biconnected_components(g), which will solve your problem. :)

igraph split graph into clusters

It looks like for all communities you can use the crossing function to get which edges cross communities (see the docs for the communities object)

library(igraph)

out <- data.frame(To = sample(1:10, 20, replace = T), From =sample(c(1,3,5,7,9), 20, replace = T))

out <- graph_from_edgelist(as.matrix(out), directed = F)
co <- cluster_optimal(out, weights = rpois(20, 2))
coGrph <- delete_edges(out, E(out)[crossing(co, out)])

par(mfrow=c(1,2))
plot(co, out, main="Cluster Optimal Communities")
plot(coGrph, main="Communities split")

Sample Image

Session Info

R version 3.3.0 (2016-05-03)
Platform: x86_64-apple-darwin13.4.0 (64-bit)
Running under: OS X 10.12.5 (unknown)

locale:
[1] en_US.UTF-8/en_US.UTF-8/en_US.UTF-8/C/en_US.UTF-8/en_US.UTF-8

attached base packages:
[1] stats graphics grDevices utils datasets methods base

other attached packages:
[1] igraph_1.0.1

loaded via a namespace (and not attached):
[1] magrittr_1.5 tools_3.3.0

How to plot the igraph subgraphs with saving the nodes' positions and ids?

Try the code below

library(igraph)
set.seed(1)
n <- 10
A <- matrix(sample(0:1, n * n, rep = TRUE), n, n)
diag(A) <- 0
g <- graph_from_adjacency_matrix(A)

id1 <- sort(as.integer(sample(V(g), size = n %/% 2, replace = FALSE)))
id2 <- sort(as.integer(sample(V(g), size = n %/% 2, replace = FALSE)))

g1 <- induced_subgraph(g, vids = id1)
g2 <- induced_subgraph(g, vids = id2)

par(mfrow = c(1,3))

layout <- layout.fruchterman.reingold(g)

layout2 <- layout[id2, ]

plot(g, layout = layout, main = "G")
plot(g1, layout = layout[id1, ], main = "G1")
plot(g2, layout = layout[id2, ], main = "G2")

Sample Image

R: Split a graph into several graphs

Since you do not provide data, I will use a simplified version of your graph to illustrate.

## Example graph
library(igraph)
g <- graph_from_literal(1-2-3-4-1, 2-5-4,
2-6, 6-7-10-8-6, 6-9-10)
CL = cluster_louvain(g)
plot(CL, g)

Communities

In order to graph the individual communities, you can use induced_subgraph to get the subgraphs and then use the like any other graph, including plotting them.

## Get graphs for each community
C1 = induced_subgraph(g, which(membership(CL) == 1))
C2 = induced_subgraph(g, which(membership(CL) == 2))

plot(C1)
plot(C2)

Note: I combined the graphs by hand. They were printed separately.

Communities

How to combine a large list of igraphs into one igraph - R

OK, i found a solution that works for me (quite fast and doesn't crash my computer).

> #first convert the list of igrpahs to list of data.frames
> subgraph_list_df <- lapply(subgraph_list, as_data_frame)
> # then combine all the data.frames in the list into one data.frame
> subgraph_df <- do.call(rbind, subgraph_list_df)
> #then make a graph out of the one combined data.frame
> subgraph <- graph_from_data_frame(subgraph_df , directed = FALSE)

for my purposes I know that the subgraphs are isolated (there are no shared edges between them). But if they are connected, should just do a unique(subgraph_df) to get rid of duplicate edges before converting to graph.

R - max subgraphs in graph

I think what you are looking for are not cliques, but connected components.

In your graph, the cliques (complete subgraphs) are of size 2 or less, so the function max_cliques will not return you anything if you set the minimal size to 3.

On the other hand, you can use the function clusters to find the largest connected components of your graph.

cl <- clusters(g)
me <- which(cl$csize >= 3)
res <- split(names(cl$membership), cl$membership)[me]
res
$`1`
[1] "1" "2" "3" "4" "5"

$`2`
[1] "6" "8" "7"


Related Topics



Leave a reply



Submit