Abordagem e exemplo de agrupamento de gráficos em "R"

10

Estou procurando agrupar / mesclar nós em um gráfico usando o agrupamento de gráficos em 'r'.

Aqui está uma variação impressionante do meu problema.

  • Existem dois "clusters"
  • Existe uma "ponte" conectando os clusters

Aqui está uma rede candidata:
insira a descrição da imagem aqui

Quando olho para a distância da conexão, a "contagem de hop", se quiser, posso obter a seguinte matriz:

 mymatrix <- rbind(
     c(1,1,2,3,3,3,2,1,1,1),
     c(1,1,1,2,2,2,1,1,1,1),
     c(2,1,1,1,1,1,1,1,2,2),
     c(3,2,1,1,1,1,1,2,3,3),
     c(3,2,1,1,1,1,1,2,3,3),
     c(3,2,1,1,1,1,1,2,2,2),
     c(2,1,1,1,1,1,1,1,2,2),
     c(1,1,1,2,2,2,1,1,1,1),
     c(1,1,2,3,3,2,2,1,1,1),
     c(1,1,2,3,3,2,2,1,1,1))

Pensamentos aqui:

  • Por sorte ou devido à simplicidade do brinquedo, a matriz possui patches óbvios. Esse não será o caso na matriz (muito grande). Se eu escolhesse aleatoriamente o relacionamento entre ponto e linha, não seria tão limpo.
  • Talvez eu tenha entendido errado - por isso, se eu tiver um erro de digitação, avise-me.
  • A contagem de saltos aqui é o menor número de saltos para conectar o ponto na linha i com o ponto na coluna j. Um auto-salto ainda é um salto, então a diagonal é tudo.

Portanto, nessa matriz, maior distância (lúpulo) tem um número maior. Se eu quisesse uma matriz mostrando "conectividade" em vez de distância, poderia fazer um ponto inverso, em que cada célula da matriz é substituída por seu inverso multiplicativo.

Questões:

Para me ajudar a encontrar meu próprio caminho:

  • Quais são os termos para reduzir o número de nós em um gráfico combinando-os? É agrupamento, fusão, munging - quais são as palavras que devo usar?
  • Quais são as técnicas comprovadas? Existe um livro sobre o assunto? Você pode apontar para documentos ou sites?
  • Agora tentei olhar aqui primeiro - é um ótimo local para o "primeiro cheque". Não encontrei o que estava procurando. Se eu errei (não é improvável), você pode me indicar uma ou duas perguntas respondidas sobre o tópico aqui no CV?

Para me levar para onde estou indo:

  • Existe um pacote 'R' que agrupará corretamente os nós na rede?
  • Você poderia me indicar um exemplo de código para fazer isso?
  • Existe um pacote 'R' que apresentará graficamente a rede reduzida resultante?
  • Você poderia me indicar um exemplo de código para fazer isso?

Desde já, obrigado.

EngrStudent
fonte
2
Esteja ciente de que solicitar pacotes ou código (R) está fora de tópico aqui. Você pode tornar a parte "encontrar" mais proeminente e a parte "obter" menos.
gung - Restabelece Monica
3
Tentarei responder em algum momento quando tiver uma chance do @gung. Mas para uma resposta rápida, aqui está a detecção da comunidade aplicada ao gráfico de exemplo do EngrStudent usando o igraphpacote R.
Andy W
11
IMHO, há apenas um cluster neste gráfico. Existem, no entanto, três panelinhas sobrepostas . Não sei por que seu plano é destruir a camarilha do meio - a menos que você possa formalizar isso, será difícil encontrar um algoritmo.
QuIT - Anony-Mousse
2
Quanto vale a pena, mcl ( micans.org/mcl ) encontra os dois grupos (eu realmente não concordo com a avaliação de Anony-Mousse, e eu não acho a abordagem de modelagem de cliques para agrupamento de gráficos particularmente proveitosa). Isso ocorre com seu único parâmetro (controle de granularidade) definido como padrão. Este algoritmo (mcl - publiquei) é amplamente utilizado em bioinformática e o código fonte (altamente escalável) está disponível. A interface com o R é feita facilmente usando interfaces de texto.
micans 27/02
2
Pedir código e pacotes sempre esteve fora de tópico aqui. Pedir ajuda com o código existente (ou seja, você tem um exemplo reproduzível ) está no tópico sobre Estouro de Pilha . Se você não sabia disso, é hora de aprender. A idéia de que os usuários que respondem às perguntas frequentes sobre SO não têm experiência estatística é estranha para mim, mas muitas pessoas parecem assumir isso; de qualquer forma, não é verdade. Que o seu Q foi respondido por uma postagem do SO deve dizer algo aqui. OTOH, dizendo 'que tipo de análise é essa, alguém pode me indicar recursos' é definitivamente um tópico aqui.
gung - Restabelece Monica

Respostas:

9

Seu exemplo em particular sugere encontrar comunidades na rede que tenham mais conexões entre nós na comunidade e relativamente poucas arestas entre nós em comunidades diferentes. Isso é diferente de encontrar comunidades isoladas , nas quais existem subgráficos completamente desconectados.

Aqui está um exemplo de detecção da comunidade em R usando o igraphpacote e um algoritmo descrito em Clauset et al. (2004) . Para usar esse algoritmo, transformo sua "contagem de saltos" em uma matriz de adjacência binária sem auto-loops. O algoritmo precisa de uma matriz não direcionada, que seja consistente com o diagrama escrito à mão e com os dados que você forneceu (as bordas são simétricas).

library(igraph)
mymatrix <- rbind(
     c(1,1,2,3,3,3,2,1,1,1),
     c(1,1,1,2,2,2,1,1,1,1),
     c(2,1,1,1,1,1,1,1,2,2),
     c(3,2,1,1,1,1,1,2,3,3),
     c(3,2,1,1,1,1,1,2,3,3),
     c(3,2,1,1,1,1,1,2,2,2),
     c(2,1,1,1,1,1,1,1,2,2),
     c(1,1,1,2,2,2,1,1,1,1),
     c(1,1,2,3,3,2,2,1,1,1),
     c(1,1,2,3,3,2,2,1,1,1))

#turn this into an adjacency matrix
adjMat <- mymatrix == 1
diag(adjMat) <- 0 #no self loops

g  <- graph.adjacency(adjMat)
plot(g)

#only works for undirected graphs, which this example is fine since symetric
fc <- fastgreedy.community(as.undirected(g))

#make colors for different communities
V(g)$color <- ifelse(membership(fc)==1,"red","blue")
plot(g)

insira a descrição da imagem aqui

Não posso comentar sobre a adequação do colapso desses nós para análises adicionais, mas essa detecção da comunidade é definitivamente útil para explorar a rede. Existem muitos outros algoritmos de detecção de comunidade (assim como outras bibliotecas para análise de rede em R). Este é apenas um exemplo que produz a saída desejada para esse problema de brinquedo.

Andy W
fonte
11
Também dados os comentários anteriores sobre o uso de um banco de dados de gráficos, você não precisa ter o gráfico representado como uma matriz de adjacência. Uma tabela para os nós e uma linha para cada borda é um formato mais típico / eficiente, e você pode transformá-lo em igraphrede.
21815 Andy W3 de
1

Se você ainda não estiver conectado a um repositório para o seu nó e dados de conexão, poderá consultar o pacote Rneo4j. Mas isso implica o uso do neo4j (um banco de dados gráfico, não um RDBMS) para armazenar seus dados. Não sou especialista aqui, mas acho que essa abordagem pode ser especialmente eficaz se: a) como sugerido por Anony-Mousse, você não puder formalizar isso, ou b) o número de nós e conexões for especialmente grande, ou c) você acabe com perguntas adicionais sobre sua rede.

user3123116
fonte
Eu não sabia que isso existia. Arrumado! Este é um exemplo decente do material? nicolewhite.github.io/RNeo4j/examples
EngrStudent
Como ir dos dados no neo4j para o agrupamento de gráficos? Mcl ou igraph trabalhariam com isso?
#
2
Depois de extrair os dados do neo4j para o R, você pode usar qualquer outro pacote R (por exemplo, AndyW sugere o igraph) nos dados. Como alternativa - o pacote Rneo4j inclui comandos para recuperar dados e também permite executar a linguagem de consulta Cypher (análoga à SQL, mas criada de forma personalizada para o neo4j graph db). No Cypher, você pode fazer consultas sofisticadas e executar alguns algoritmos predefinidos (caminhos mais curtos, todos os caminhos, todos os caminhos simples, Dijkstra etc.). Estou no meu limite aqui em caracteres e conteúdo - se você quiser seguir esse caminho (desculpe!), O site neo4j pode ser sua próxima parada.
precisa saber é o seguinte
1

Para futuros leitores,

Aqui está um conjunto de funções dos pacotes igraph e o último é do MCL:

print("LABEL PROPAGATION")
w<-cluster_label_prop(g)

print("Leading Eigen")
w<-cluster_leading_eigen(g)

print("SpinGlass")
w<-cluster_spinglass(g, stop.temp = 0.05)

print("walktrap")
w<-cluster_walktrap(g, steps=4)

print("MCL")
adj<-get.adjacency(g)
w<-mcl(adj,addLoops=TRUE)

Você pode encontrar a documentação aqui http://igraph.org/r/doc/ e aqui https://cran.r-project.org/web/packages/MCL/MCL.pdf

Acho a caminhada particularmente útil

Omar Jaafor
fonte
Embora isso possa estar relacionado à pergunta, não parece ser uma resposta.
Michael R. Chernick 22/03
2
Eu respondi as duas perguntas: Existe um pacote 'R' que irá agrupar corretamente os nós na rede? Você poderia me indicar um exemplo de código para fazer isso? Mas sim, ele não responde a todo o conjunto de perguntas.
Omar Jaafor