CODEWITHSUNDEEP
r
Jesse Anderson
Jesse Anderson

Reputation: 4603

Converting a binary matrix into groups

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.

Upvotes: 4

Views: 828

Answers (4)

Josh O&#39;Brien
Josh O&#39;Brien

Reputation: 162401

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.

Upvotes: 3

agstudy
agstudy

Reputation: 121598

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

Upvotes: 6

lukeA
lukeA

Reputation: 54247

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

Upvotes: 3

JasonAizkalns
JasonAizkalns

Reputation: 20473

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

Upvotes: 2

Related Questions