Converting a binary matrix into groups

Question

This is a seemingly simple problem, but I can't come up with an answer. Here is the simplest case:

Consider the following matrix:

friendMatrix  <- matrix(c(1,1,0,0,0,     
                          1,1,1,0,0,
                          0,1,1,0,0,
                          0,0,0,1,1,
                          0,0,0,1,1),nrow=5)

Which looks like this

     [,1] [,2] [,3] [,4] [,5]
[1,]    1    1    0    0    0 
[2,]    1    1    1    0    0
[3,]    0    1    1    0    0
[4,]    0    0    0    1    1
[5,]    0    0    0    1    1

What I'd like to do is use this matrix to identify groups of friends, where 1 indicates friendship. Groups are formed based on any connections within the group, not just first degree ones (that is, 1 is a friend of 2, and 2 is a friend of 3 but not 1, but they are all in the same group). If a row is only associated with itself, then it's its own group. I'd like to create a data.frame indicating membership (using row number as ID) in these groups (a number is fine as ID, I just used letters to avoid confusion). For this example, that would be the following:

row  group
 1    A
 2    A
 3    A
 4    B
 5    B

I've considered some clustering algorithms, but that seems like overkill here, since the groups are well defined and obvious.

Answer 1

Using igraph to create a graph and creating clusters by grouping the connected components of the resulted graph:

library(igraph)
g1 <- graph.adjacency( friendMatrix )
cl <- clusters(g1)$mem
## Display the clusters in a data.frame as OP excpeted
data.frame(row=seq_along(cl),group=LETTERS[cl])

   row group
1   1     A
2   2     A
3   3     A
4   4     B
5   5     B

Answer 2

Here's another option:

library(igraph)
g <- graph.adjacency(friendMatrix, "undirected")
(group <- clusters(g)$membership)
# [1] 1 1 1 2 2
V(g)$color <- group + 1
plot(g)