Преобразование двоичной матрицы в группы

Question

Это на первый взгляд простая проблема, но я не могу придумать ответ. Вот самый простой случай:

Рассмотрим следующую матрицу:

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)

Который выглядит так

     [,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

Я хотел бы использовать эту матрицу для определения групп друзей, где 1 обозначает дружбу. Группы формируются на основе любых связей внутри группы, а не только связей первой степени (то есть 1 - друг 2, а 2 - друг 3, но не 1, но все они находятся в одной группе). Если строка связана только с самим собой, то это ее собственная группа. Я хотел бы создать data.frame, указывающий членство (используя номер строки в качестве идентификатора) в этих группах (номер подходит в качестве идентификатора, я просто использовал буквы, чтобы избежать путаницы). Для этого примера это будет следующим:

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

Я рассмотрел некоторые алгоритмы кластеризации, но здесь это кажется излишним, поскольку группы четко определены и очевидны.

Answer 1

С помощью igraph создать график и создать кластеры, группируя связанные компоненты полученного графика:

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

Вот еще один вариант:

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

Answer 3

Приспосабливая мой ответ к аналогичному вопросу пару лет назад, вы можете использовать пакет RBGL для определения "связанных компонентов", которые вам нужны:

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

Альтернативное решение на основе igraph см. Здесь.

Answer 4

Следующее позволит вам визуализировать сеть отношений, все еще работая над тем, как извлечь группы.

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)