Enfoque y ejemplo de agrupación de gráficos en "R"

Estoy buscando agrupar / fusionar nodos en un gráfico usando la agrupación de gráficos en 'r'.

Aquí hay una variación asombrosamente juguetona de mi problema.

• Hay dos "grupos"
• Hay un "puente" que conecta los grupos

Aquí hay una red de candidatos:

Cuando miro la distancia de conexión, el "conteo", si lo desea, entonces puedo obtener la siguiente 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))

Pensamientos aquí:

• Por suerte o debido a la simplicidad del juguete, la matriz tiene parches obvios, este no será el caso en la matriz (muy grande). Si aleatorizara la relación entre punto y fila, entonces no sería tan limpio.
• Puede que me haya equivocado, así que si tengo un error tipográfico, avíseme.
• El conteo de saltos aquí es el número más corto de saltos para conectar el punto en la fila i con el punto en la columna j. Un salto automático sigue siendo un salto, por lo que la diagonal es todo.

Entonces, en esta matriz, la mayor distancia (lúpulo) tiene un número mayor. Si quisiera una matriz que mostrara "conectividad" en lugar de distancia, podría hacer un punto inverso, donde cada celda de la matriz se reemplaza con su inverso multiplicativo.

Preguntas:

Para ayudarme a encontrar mi propio camino:

• ¿Cuáles son los términos para reducir el número de nodos en un gráfico combinándolos? ¿Es agrupación, fusión, munging, cuáles son las palabras que debo usar?
• ¿Cuáles son las técnicas probadas? ¿Hay un libro de texto sobre el tema? ¿Puedes señalar documentos o sitios web?
• Ahora traté de mirar aquí primero, es un gran lugar de "primer chequeo". No encontré lo que estaba buscando. Si me lo perdí (no es poco probable), ¿puede señalarme una o dos preguntas respondidas sobre el tema aquí en CV?

Para llevarme a donde voy:

• ¿Existe un paquete 'R' que agrupe adecuadamente los nodos en la red?
• ¿Podría indicarme un código de ejemplo para hacer esto?
• ¿Existe un paquete 'R' que presente gráficamente la red reducida resultante?
• ¿Podría indicarme un código de ejemplo para hacer esto?

Gracias por adelantado.

Su ejemplo particular sugiere encontrar comunidades dentro de la red que tengan más conexiones entre nodos en la comunidad y relativamente pocos bordes entre nodos en diferentes comunidades. Esto es distinto de encontrar comunidades aisladas , en las que hay subgrafías que están completamente desconectadas.

Aquí hay un ejemplo de detección comunitaria en R usando el igraphpaquete y un algoritmo descrito en Clauset et al. (2004) . Para usar este algoritmo, convierto su "conteo de saltos" en una matriz de adyacencia binaria sin bucles propios. El algoritmo necesita una matriz no dirigida, que sea consistente con su diagrama escrito a mano y los datos que proporcionó (los bordes son simétricos).

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)

No puedo comentar sobre la conveniencia de colapsar dichos nodos para un análisis posterior, pero esa detección de la comunidad es definitivamente útil para explorar la red. También hay muchos otros algoritmos de detección de la comunidad (así como otras bibliotecas para el análisis de red en R). Este es solo un ejemplo que produce el resultado deseado para este problema de juguete.

Si aún no está conectado a un repositorio para su nodo y datos de conexión, puede consultar el paquete Rneo4j. Pero esto implica el uso de neo4j (una base de datos de gráficos, no un RDBMS) para almacenar sus datos. No soy un experto aquí, pero creo que este enfoque podría ser especialmente efectivo si a) como sugiere Anony-Mousse, no puedes formalizar esto, o b) el número de nodos y conexiones es especialmente grande, o c) teniendo preguntas adicionales con respecto a su red.

Para futuros lectores,

Aquí hay un conjunto de funciones de los paquetes igraph y el último es de 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)

Puede encontrar la documentación aquí http://igraph.org/r/doc/ y aquí https://cran.r-project.org/web/packages/MCL/MCL.pdf

Encuentro Walktrap particularmente útil