10

I would like to find all the connected components of a graph where the components have more than one element.

using the clusters gives the membership to different clusters and using cliques does not give connected components.

This is a follow up from

multiple intersection of lists in R

My main goal was to find all the groups of lists which have elements in common with each other.

Thanks in advance!

Community
  • 1
  • 1
Dinesh
  • 2,194
  • 3
  • 30
  • 52
  • do you need `clusters`? – user20650 May 23 '15 at 00:50
  • @user20650 yes. clusters with more than one element. sorry I meant clusters instead of connectedComp. Edited the question – Dinesh May 23 '15 at 00:50
  • The `?clusters` function returns cluster membership and size - should be easy enough to subset it to only include clusters with more than one node – user20650 May 23 '15 at 00:55
  • @user20650 Is there any efficient way to do this instead of manually going through the results of `clusters`? – Dinesh May 23 '15 at 01:06
  • 2
    There is probably a function to extract this... but you can just use the results from `clusters`. One way: `cl <- clusters(g); lapply(seq_along(cl$csize)[cl$csize > 1], function(x) V(g)$name[cl$membership %in% x])` – user20650 May 23 '15 at 01:10
  • @user20650 I guess you do not need the `$name` and why not you post the answer? Also we need to convert `vertex` type to numeric – Dinesh May 23 '15 at 01:18

1 Answers1

16

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)

enter image description here

# 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"
user20650
  • 24,654
  • 5
  • 56
  • 91
  • 3
    Just for fun, here's another approach once you have the clusters: `grps <- with(cl, duplicated(membership)|duplicated(membership, fromLast=TRUE))` followed by `unname(split(V(g)$name[grps], cl$membership[grps]))` – Jota May 23 '15 at 03:37