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
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)
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")
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")
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)
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.
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
Annotate Values Above Bars (Ggplot Faceted)
Determine Level of Nesting in R
Devtools::Install_Github() - Ignore Ssl Cert Verification Failure
How to Produce a Heatmap with Ggplot2
Rcpp Warning: "Directory Not Found for Option '-L/Usr/Local/Cellar/Gfortran/4.8.2/Gfortran'"
Text-Mining with the Tm-Package - Word Stemming
How to Read Huge CSV File into R by Row Condition
Configuration Failed Because Libcurl Was Not Found
"Adding Missing Grouping Variables" Message in Dplyr in R
How to Remove Rows of a Matrix by Row Name, Rather Than Numerical Index
How to Access Global/Outer Scope Variable from R Apply Function
How to Update a Shiny Fileinput Object
Display HTML File in Shiny App