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:
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.
r
clustering
data-visualization
numerics
EngrStudent
fonte
fonte
igraph
pacote R.Respostas:
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
igraph
pacote 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).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.
fonte
igraph
rede.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.
fonte
Para futuros leitores,
Aqui está um conjunto de funções dos pacotes igraph e o último é do MCL:
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
fonte