Get Connected Components Using Igraph in R

get connected components using igraph in R

You can use the results from components to subset your nodes according to the component size.

library(igraph)

# example graph
set.seed(1)
g <- erdos.renyi.game(20, 1/20)
V(g)$name <- letters[1:20]
par(mar=rep(0,4))
plot(g)

# get components
cl <- components(g)
cl
# $membership
# [1]  1  2  3  4  5  4  5  5  6  7  8  9 10  3  5 11  5  3 12  5
# 
# $csize
# [1] 1 1 3 2 6 1 1 1 1 1 1 1
# 
# $no
# [1] 12

# loop through to extract common vertices
lapply(seq_along(cl$csize)[cl$csize > 1], function(x) 
                                         V(g)$name[cl$membership %in% x])
# [[1]]
# [1] "c" "n" "r"
# 
# [[2]]
# [1] "d" "f"
# 
# [[3]]
# [1] "e" "g" "h" "o" "q" "t"

Getting the biggest connected component in R igraph

Well, detailed explanation of output value of any function in the R package could be found in its documentation. In this case igraph::clusters returns a named list where in csize sizes of clusters are stored while membership contains the cluster id to which each vertex belongs to.

g <- igraph::sample_gnp(20, 1/20)

components <- igraph::clusters(g, mode="weak")
biggest_cluster_id <- which.max(components$csize)

# ids
vert_ids <- V(g)[components$membership == biggest_cluster_id]

# subgraph
igraph::induced_subgraph(g, vert_ids)

How to connect components of a graph in igraph

Try the code below

graph2 <- with(
  stack(membership(cl)),
  add.edges(
    graph1,
    c(combn(sapply(split(ind, values), sample, size = 1), 2)),
    weight = runif(choose(cl$no, 2))
  )
)

where a full connections among all components is given as below

---

You can check the weights of edges of graph2

> E(graph2)
+ 27/27 edges from 31a7614 (vertex names):
 [1] ID_00104--ID_06663 ID_00104--ID_06791 ID_00104--ID_09099 ID_00136--ID_00169
 [5] ID_00136--ID_00910 ID_00169--ID_00910 ID_00178--ID_00790 ID_00180--ID_01013
 [9] ID_00180--ID_01130 ID_00180--ID_01260 ID_00180--ID_00394 ID_00180--ID_00860
[13] ID_00180--ID_00959 ID_00180--ID_01222 ID_00180--ID_00288 ID_00180--ID_00324
[17] ID_00180--ID_00663 ID_00180--ID_00846 ID_00180--ID_01047 ID_00180--ID_06781
[21] ID_00180--ID_06786 ID_00136--ID_06663 ID_00178--ID_06663 ID_06663--ID_01013
[25] ID_00136--ID_00178 ID_00136--ID_01013 ID_00178--ID_01013

> E(graph2)$weight
 [1] 0.6541726 0.9190969 0.9258216 0.8604061 0.7463768 0.7671958 0.8303797
 [8] 0.6615776 0.7075209 0.9081935 0.6571188 0.6876640 0.6858639 0.8745136
[15] 0.8366465 0.6183618 0.6841637 0.9147287 0.8762976 0.7327071 0.7731164
[22] 0.3098355 0.5842953 0.7397926 0.7337629 0.7643245 0.8331742

---

If you want to see edge list, you can use as_data_frame, e.g.,

> as_data_frame(graph2)
       from       to   new_ssp    weight
1  ID_00104 ID_06663 0.6541726 0.6541726
2  ID_00104 ID_06791 0.9190969 0.9190969
3  ID_00104 ID_09099 0.9258216 0.9258216
4  ID_00136 ID_00169 0.8604061 0.8604061
5  ID_00136 ID_00910 0.7463768 0.7463768
6  ID_00169 ID_00910 0.7671958 0.7671958
7  ID_00178 ID_00790 0.8303797 0.8303797
8  ID_00180 ID_01013 0.6615776 0.6615776
9  ID_00180 ID_01130 0.7075209 0.7075209
10 ID_00180 ID_01260 0.9081935 0.9081935
11 ID_00180 ID_00394 0.6571188 0.6571188
12 ID_00180 ID_00860 0.6876640 0.6876640
13 ID_00180 ID_00959 0.6858639 0.6858639
14 ID_00180 ID_01222 0.8745136 0.8745136
15 ID_00180 ID_00288 0.8366465 0.8366465
16 ID_00180 ID_00324 0.6183618 0.6183618
17 ID_00180 ID_00663 0.6841637 0.6841637
18 ID_00180 ID_00846 0.9147287 0.9147287
19 ID_00180 ID_01047 0.8762976 0.8762976
20 ID_00180 ID_06781 0.7327071 0.7327071
21 ID_00180 ID_06786 0.7731164 0.7731164
22 ID_06791 ID_00910        NA 0.5680686
23 ID_00178 ID_06791        NA 0.6278790
24 ID_06791 ID_00288        NA 0.8059711
25 ID_00178 ID_00910        NA 0.2578959
26 ID_00910 ID_00288        NA 0.6189977
27 ID_00178 ID_00288        NA 0.6594792

igraph get ids of connected components

You can use order to sort and find out the memberships of the top 3 largest clusters and use %in% to check if vertices are within one of them:

which(c$membership %in% order(c$csize, decreasing = TRUE)[1:3])

---

• order(c$csize, decreasing = TRUE) gives the index(which corresponds to the cluster id) that will sort the size in descending order;
• c$membership contains the cluster id for all vertices;
• use %in% to check if the cluster id are within the top three;

Combine community detection with connected components grouping igraph R

You can just transfer this into your original graph g.
In your example, I think that you just want the vertices in the
other connected component to be another community, it suffices to assign all nodes in the second component to group 3.

V(g)$membership = 3
V(g)[V(g1)$name]$membership = m$membership
V(g)$membership
[1] 1 1 1 2 2 2 3 3 2

But in a more general example, there might be multiple components and those components might break up into multiple communities.
To cover that, you can loop through all components, compute the communities and then transfer those back to the original graph.

V(g)$membership = 0
for(comp in unique(dg$membership)) {
    g1 <- induced_subgraph(g, which(dg$membership == comp))
    m<-cluster_spinglass(g1)
    V(g)[V(g1)$name]$membership = m$membership + max(V(g)$membership)
}
V(g)$membership
[1] 1 1 1 2 2 2 3 3 2

Difference between clusters() and components() - R igraph

clusters is the older name of the function. It was at one point renamed to components, which is the standard term in graph theory. The old name was kept for compatibility.

How do I apply a function to each connected components within a graph/network?

You can use the decompose.graph function in igraph to obtain a list of the connected components, then use lapply to run your function (alpha.centrality or bonpow) on each of the components. After having run decompose.graph, you may want to deallocate your original graph to re-claim some memory.

Visualize strongly connected components in R

Take a look at the mark.groups argument of plot.igraph. Something like the following will do the trick:

# Create some toy data
set.seed(1)
library(igraph)
graph <- erdos.renyi.game(20, 1/20)

# Do the clustering
SCC <- clusters(graph, mode="strong")  

# Add colours and use the mark.group argument
V(graph)$color <- rainbow(SCC$no)[SCC$membership]
plot(graph, mark.groups = split(1:vcount(graph), SCC$membership))

---

Related Topics