Aproximación y ejemplo de gráfico de clustering en "R"

Question

Estoy buscando grupo/combinación de nodos en un grafo usando el gráfico de la agrupación en clústeres en 'r'.

Aquí es un sensacional juguete variación de mi problema.

• Hay dos "clusters"
• Hay un "puente" que conecta los clústeres

Aquí es un candidato a la red:

Cuando miro a la distancia de conexión, el "hopcount", si lo desea, puede 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 de la matriz, tiene, obviamente, parches, esto no va a ser el caso en el (muy grande) de la matriz. Si me aleatorizado, de la relación entre el punto de fila y, a continuación, no sería tan limpio.
• Yo podría haber conseguido un mal - así que si tengo un error tipográfico, hágamelo saber.
• Hop-contar aquí es el menor número de saltos para conectar el punto en la fila i con el punto en la columna j. Un auto-hop es todavía un salto, por lo que la diagonal es de todos.

Así que en esta matriz de distancia mayor (saltos) tiene un número mayor. Si quería una matriz que muestra "conectividad" en lugar de la distancia, entonces yo podría hacer un punto inverso, donde cada celda de la matriz se sustituye con su inverso multiplicativo.

Preguntas:

Para que me ayude a encontrar mi propio camino:

• ¿Cuáles son los términos para reducir el número de nodos en un grafo mediante la combinación de ellos? Es la agrupación, la fusión, fotográficos - ¿cuáles son las palabras que debo utilizar?
• ¿Cuáles son las técnicas probadas? Hay un libro de texto sobre el tema? ¿Puedes señalar los documentos o sitios web?
• Ahora traté de buscar primero aquí - es una gran "primer cheque" irregular. No encontré lo que estaba buscando. Si me he perdido (no es raro) puede que me apunte a una respuesta a una pregunta o dos sobre el tema aquí en CV?

Me llego a donde voy:

• Hay una 'R' paquete correctamente clúster de los nodos en la red?
• ¿Me podrías recomendar ejemplo de código para hacer esto?
• Hay una 'R' paquete que gráficamente presente la resultante de red reducido?
• ¿Me podrías recomendar ejemplo de código para hacer esto?

Gracias de antemano.

Answer 1

Su ejemplo sugiere encontrar comunidades dentro de la red que tienen más conexiones entre los nodos de la comunidad y de relativamente pocas aristas entre los nodos en diferentes comunidades. Esto es diferente de la búsqueda de comunidades aisladas, en las que hay subdiagramas que están totalmente desconectados.

Aquí es un ejemplo de la detección de la comunidad en R usando el igraph paquete y un algoritmo descrito en Clauset et al. (2004). Para utilizar este algoritmo puedo activar su "saltos" en un binario de la matriz de adyacencia con el no yo bucles. El algoritmo necesita un grafo de la matriz, lo cual es consistente con su escrito a mano el diagrama y los datos por usted facilitados (los bordes son 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)

No puedo comentar sobre la idoneidad del colapso de tales nodos para su posterior análisis, pero tales detección de la comunidad es sin duda muy útil para explorar la red. Hay un montón de otros de la comunidad de algoritmos de detección (así como otras bibliotecas para el análisis de red en R). Este es sólo un ejemplo que sucede para producir la salida deseada para este juguete problema.

Answer 2

Si usted no se ya casados con un repositorio para los datos de su nodo y conexión, podría ser el paquete de Rneo4j. Pero esto implica el uso de la neo4j (una gráfico de datos, no un RDBMS) para almacenar los datos. No soy un experto aquí, pero creo que este enfoque puede ser especialmente eficaz si un) según lo sugerido por ro-Mousse, usted no puede formalizar esto, b) el número de nodos y conexiones es especialmente grande o c) viento tener preguntas adicionales con respecto a su red.