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.

score 6 · Accepted Answer · answered Mar 27 '15 at 17:50

6

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

answered Mar 27 '15 at 17:50

agstudy

119,832
17
199
261

Answered my question and also introduced me to a very useful package – Jesse Anderson Mar 30 '15 at 18:44
1

Is there a Python version of this solution? – zh1 Jan 07 '20 at 20:50

score 3 · Answer 2 · edited May 23 '17 at 11:43

Adapting my answer to a similar question from a couple of years ago, you can use the RBGL package to identify the "connected components" that you are after:

library(RBGL)
m <- which(friendMatrix==1, arr.ind=TRUE)
g <- ftM2graphNEL(m)
cc <- connectedComp(g)
names(cc) <- LETTERS[seq_along(cc)]
ld <- lapply(seq_along(cc), 
             function(i) data.frame(row = cc[[i]], group = names(cc)[i]))
do.call(rbind, ld)
#   row group
# 1   1     A
# 2   2     A
# 3   3     A
# 4   4     B
# 5   5     B

For an alternative, igraph-based solution, see here.

score 3 · Answer 3 · answered Mar 27 '15 at 17:49

3

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)

enter image description here

answered Mar 27 '15 at 17:49

lukeA

53,097
5
97
100

score 2 · Answer 4 · answered Mar 27 '15 at 17:43

The following will enable you to visualize the network of relationships, still working on how to extract the groups.

require(networkD3)
require(reshape2)

melted <- melt(friendMatrix)
relationships <- subset(melted, value == 1)
relationships
#    Var1 Var2 value
# 1     1    1     1
# 2     2    1     1
# 6     1    2     1
# 7     2    2     1
# 8     3    2     1
# 12    2    3     1
# 13    3    3     1
# 19    4    4     1
# 20    5    4     1
# 24    4    5     1
# 25    5    5     1

simpleNetwork(relationships)

Network

Converting a binary matrix into groups

4 Answers4